2022-05-24T16:35:54Zhttps://repository.dl.itc.u-tokyo.ac.jp/oaioai:repository.dl.itc.u-tokyo.ac.jp:000058282021-03-01T19:33:42Z非対称な通信路と情報源の効率的なpolar符号化およびLDPC符号化Efficient Polar and LDPC Coding for Asymmetric Channels and SourcesHonda, Junya12005LDPC codespolar codeschannel codinglossy source codingarithmetic codinghomophonic codingbelief propagationlinear programming decodingnonbinary codesUniversity of Tokyo (東京大学)博士(科学)Channel coding and source coding are the most fundamental problems in information theory. Shannon formulated these problems and derived their theoretical limits on the efficiency of the codes. Since the original codes proposed by him require exponential complexity to achieve the limits, the main topic of information theory has been to construct a practical coding scheme approaching the limits. // Among the above coding problems, we consider channel coding and lossy source coding. Previous works on these problems mainly focused their attention on symmetric settings, that is, channel coding for symmetric channels or lossy source coding for uniform sources and symmetric distortion measures, which make the code construction and analysis much easier. However, real-world settings are not always symmetric and therefore practical coding schemes for the asymmetric settings are also important as well. In coding problems for asymmetric settings, the optimal symbol distribution of codewords is not uniform in general. In most literatures for these settings, coding schemes are constructed based on Gallager’s nonlinear mapping, which reduces generation of nonuniform codewords into that of uniform codewords with an extended alphabet. However, coding schemes constructed by Gallager’s method are often inefficient in practice whereas they can achieve the the Shannon bound theoretically. It is mainly because the complexity of a code increases rapidly with the alphabet size in most coding schemes whereas infinitely increasing alphabet size is required to achieve the Shannon bound by Gallager’s method in general. // To achieve the Shannon bound with realistic complexity, we investigate coding schemes which do not require any extended alphabet to generate nonuniform codewords in this thesis. The key to the nonuniform codewords is in lossless compression, which transforms a source sequence into a uniform sequence. This nature of the lossless compression implies that we can obtain a nonuniform codeword from a uniform sequence by the inverse operation of lossless compression. // First we apply the idea of using lossless compression to polar codes. Polar codes are recently proposed for symmetric channels by Arikan and attracting much attention because of their achievability of the channel capacity with polynomial complexity. In the polar codes, a sequence of i.i.d. channel inputs is transformed by an invertible linear operation into another sequence. The input sequence polarizes by this transformation, that is, each variable of the transformed sequence becomes almost deterministic or almost random given the preceding variables. Then, reliable transmission can be realized by assigning a message to the almost deterministic variables of the transformed sequence. // The idea of using lossless compression for asymmetric channels can be easily applied to polar codes. It is because the probability distributions of the channel inputs also polarize into almost deterministic or almost random ones as well as the reliabilities of the variables given channel outputs after the transformation for polar codes. The inverse operation of the lossless compression can be easily realized by simply assigning a uniform message to the almost random variables and determining the other variables to be the most likely ones. Also for lossy source coding with nonuniform sources and/or asymmetric distortion measures, optimal polar codes can be constructed easily by exchanging the encoding and the decoding of those for channel coding. // Next we consider low density parity check (LDPC) codes for asymmetric settings. An LDPC code is a linear code using a sparse matrix, and it is one of the most promising codes for its good performance with practical decoding algorithms although the theoretical analysis is difficult compared to polar codes. In the framework of LDPC codes, Miyake and Muramatsu proposed coding schemes based on fixed length lossless compression for the asymmetric settings. They proved that their scheme can achieve the Shannon bound under the maximum-likelihood (ML) decoding. However, the ML decoding is computationally intractable and it is not shown that their scheme can attain good performance under polynomial-time decoding algorithms. It is because most known practical algorithms such as belief propagation often fail in the decoding of fixed length lossless compression. // In this thesis, we propose a new variable length coding scheme using LDPC codes. We first investigate a fixed-to-variable length lossy coding scheme for nonuniform sources and/or asymmetric distortion measures. We use arithmetic coding for the lossless compressor and show that our scheme can achieve the rate-distortion function. Note that the exact computation of the probability assigned for the arithmetic code is also intractable practically. However, in our scheme we can achieve near optimal performance by approximating the assigned probability with moderate accuracy. This fact contrasts with the fixed length coding where any codeword other than the ML codeword leads to a large distortion. // We next investigate variable length channel coding scheme using LDPC codes. Generally it is known that a good channel code can be constructed by exchanging the encoder with the decoder of a good lossy code. Then it is natural to consider a variable-to-fixed length channel code obtained from the lossy code described above. However, this technique cannot be used in this case because the arithmetic code does not work as a code when the encoder and the decoder are exchanged. Then we propose a fixed-to-variable length channel coding scheme using a homophonic code. Homophonic codes are the codes used for transforming a random sequence reversibly to another random sequence with a different distribution. We prove that the channel capacity can be achieved by generating nonuniform LDPC codewords using a good homophonic code. // Finally we consider practical algorithms for LDPC codes. In the proposed schemes for the asymmetric settings, two types of computation are required for the encoding and the decoding. The first type of computation is the search of the ML codeword, and we propose two algorithms for this problem based on a linear programming relaxation technique and a reinforced belief propagation combined with a matroid optimization. We show by simulation that they attain good performance for channel coding and lossy source coding, respectively. The second type of computation is sequential computation of marginal probabilities of symbols over nonuniform LDPC codewords for an arithmetic code or a homophonic code. We propose an algorithm using a belief propagation which makes the complexity of the arithmetic coding or the homophonic coding nearly linear time.thesis2013-03-252013-03-25application/pdf甲第29525号https://repository.dl.itc.u-tokyo.ac.jp/record/5828/files/K-04103.pdfeng