WEKO3
AND
Item
{"_buckets": {"deposit": "770ad9901b2c401daf6bd6b318c8d322"}, "_deposit": {"id": "5828", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "5828"}, "status": "published"}, "_oai": {"id": "oai:repository.dl.itc.utokyo.ac.jp:00005828"}, "item_7_alternative_title_1": {"attribute_name": "\u305d\u306e\u4ed6\u306e\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_alternative_title": "\u975e\u5bfe\u79f0\u306a\u901a\u4fe1\u8def\u3068\u60c5\u5831\u6e90\u306e\u52b9\u7387\u7684\u306apolar\u7b26\u53f7\u5316\u304a\u3088\u3073LDPC\u7b26\u53f7\u5316"}]}, "item_7_biblio_info_7": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "20130325", "bibliographicIssueDateType": "Issued"}, "bibliographic_titles": [{}]}]}, "item_7_date_granted_25": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u5e74\u6708\u65e5", "attribute_value_mlt": [{"subitem_dategranted": "20130325"}]}, "item_7_degree_grantor_23": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u6a5f\u95a2", "attribute_value_mlt": [{"subitem_degreegrantor": [{"subitem_degreegrantor_name": "University of Tokyo (\u6771\u4eac\u5927\u5b66)"}]}]}, "item_7_degree_name_20": {"attribute_name": "\u5b66\u4f4d\u540d", "attribute_value_mlt": [{"subitem_degreename": "\u535a\u58eb(\u79d1\u5b66)"}]}, "item_7_description_5": {"attribute_name": "\u6284\u9332", "attribute_value_mlt": [{"subitem_description": "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, realworld 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\u2019s nonlinear mapping, which reduces generation of nonuniform codewords into that of uniform codewords with an extended alphabet. However, coding schemes constructed by Gallager\u2019s 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\u2019s 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 maximumlikelihood (ML) decoding. However, the ML decoding is computationally intractable and it is not shown that their scheme can attain good performance under polynomialtime 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 fixedtovariable 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 ratedistortion 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 variabletofixed 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 fixedtovariable 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.", "subitem_description_type": "Abstract"}]}, "item_7_dissertation_number_26": {"attribute_name": "\u5b66\u4f4d\u6388\u4e0e\u756a\u53f7", "attribute_value_mlt": [{"subitem_dissertationnumber": "\u7532\u7b2c29525\u53f7"}]}, "item_7_full_name_3": {"attribute_name": "\u8457\u8005\u5225\u540d", "attribute_value_mlt": [{"nameIdentifiers": [{"nameIdentifier": "12006", "nameIdentifierScheme": "WEKO"}], "names": [{"name": "\u672c\u591a, \u6df3\u4e5f"}]}]}, "item_7_identifier_registration": {"attribute_name": "ID\u767b\u9332", "attribute_value_mlt": [{"subitem_identifier_reg_text": "10.15083/00005819", "subitem_identifier_reg_type": "JaLC"}]}, "item_7_select_21": {"attribute_name": "\u5b66\u4f4d", "attribute_value_mlt": [{"subitem_select_item": "doctoral"}]}, "item_7_text_22": {"attribute_name": "\u5b66\u4f4d\u5206\u91ce", "attribute_value_mlt": [{"subitem_text_value": "Science (Kagaku)(\u79d1\u5b66)"}]}, "item_7_text_24": {"attribute_name": "\u7814\u7a76\u79d1\u30fb\u5c02\u653b", "attribute_value_mlt": [{"subitem_text_value": "Department of Complexity Science and Engineering, Graduate School of Frontier Sciences (\u65b0\u9818\u57df\u5275\u6210\u79d1\u5b66\u7814\u7a76\u79d1\u8907\u96d1\u7406\u5de5\u5b66\u5c02\u653b)"}]}, "item_7_text_27": {"attribute_name": "\u5b66\u4f4d\u8a18\u756a\u53f7", "attribute_value_mlt": [{"subitem_text_value": "\u535a\u5275\u57df\u7b2c870\u53f7"}]}, "item_7_text_36": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"subitem_text_value": "Thesis"}]}, "item_7_text_4": {"attribute_name": "\u8457\u8005\u6240\u5c5e", "attribute_value_mlt": [{"subitem_text_value": "\u6771\u4eac\u5927\u5b66\u5927\u5b66\u9662\u65b0\u9818\u57df\u5275\u6210\u79d1\u5b66\u7814\u7a76\u79d1\u8907\u96d1\u7406\u5de5\u5b66\u5c02\u653b"}]}, "item_creator": {"attribute_name": "\u8457\u8005", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Honda, Junya"}], "nameIdentifiers": [{"nameIdentifier": "12005", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "\u30d5\u30a1\u30a4\u30eb\u60c5\u5831", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "20170601"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "K04103.pdf", "filesize": [{"value": "1.1 MB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 1100000.0, "url": {"label": "K04103.pdf", "url": "https://repository.dl.itc.utokyo.ac.jp/record/5828/files/K04103.pdf"}, "version_id": "e425c02ba39a4fbab243b0bc1f093d36"}]}, "item_keyword": {"attribute_name": "\u30ad\u30fc\u30ef\u30fc\u30c9", "attribute_value_mlt": [{"subitem_subject": "LDPC codes", "subitem_subject_scheme": "Other"}, {"subitem_subject": "polar codes", "subitem_subject_scheme": "Other"}, {"subitem_subject": "channel coding", "subitem_subject_scheme": "Other"}, {"subitem_subject": "lossy source coding", "subitem_subject_scheme": "Other"}, {"subitem_subject": "arithmetic coding", "subitem_subject_scheme": "Other"}, {"subitem_subject": "homophonic coding", "subitem_subject_scheme": "Other"}, {"subitem_subject": "belief propagation", "subitem_subject_scheme": "Other"}, {"subitem_subject": "linear programming decoding", "subitem_subject_scheme": "Other"}, {"subitem_subject": "nonbinary codes", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "\u8a00\u8a9e", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"resourcetype": "thesis", "resourceuri": "http://purl.org/coar/resource_type/c_46ec"}]}, "item_title": "Efficient Polar and LDPC Coding for Asymmetric Channels and Sources", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "Efficient Polar and LDPC Coding for Asymmetric Channels and Sources"}]}, "item_type_id": "7", "owner": "1", "path": ["9/233/280", "110/328/329"], "permalink_uri": "https://doi.org/10.15083/00005819", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "attribute_name_i18n": "\u516c\u958b\u65e5", "attribute_value": "20150115"}, "publish_date": "20150115", "publish_status": "0", "recid": "5828", "relation": {}, "relation_version_is_last": true, "title": ["Efficient Polar and LDPC Coding for Asymmetric Channels and Sources"], "weko_shared_id": null}
Efficient Polar and LDPC Coding for Asymmetric Channels and Sources
https://doi.org/10.15083/00005819
12fe61f32b994ce997dfaf1f4b5e34c9
Name / File  License  Actions  

K04103.pdf (1.1 MB)


item type  学位論文 / Thesis or Dissertation(1)  

公開日  20150115  
タイトル  
タイトル  Efficient Polar and LDPC Coding for Asymmetric Channels and Sources  
言語  
言語  eng  
キーワード  
主題Scheme  Other  
主題  LDPC codes  
キーワード  
主題Scheme  Other  
主題  polar codes  
キーワード  
主題Scheme  Other  
主題  channel coding  
キーワード  
主題Scheme  Other  
主題  lossy source coding  
キーワード  
主題Scheme  Other  
主題  arithmetic coding  
キーワード  
主題Scheme  Other  
主題  homophonic coding  
キーワード  
主題Scheme  Other  
主題  belief propagation  
キーワード  
主題Scheme  Other  
主題  linear programming decoding  
キーワード  
主題Scheme  Other  
主題  nonbinary codes  
資源タイプ  
資源  http://purl.org/coar/resource_type/c_46ec  
タイプ  thesis  
ID登録  
ID登録  10.15083/00005819  
ID登録タイプ  JaLC  
その他のタイトル  
その他のタイトル  非対称な通信路と情報源の効率的なpolar符号化およびLDPC符号化  
著者 
Honda, Junya
× Honda, Junya 

著者別名  
姓名  
姓名  本多, 淳也  
著者所属  
東京大学大学院新領域創成科学研究科複雑理工学専攻  
Abstract  
内容記述タイプ  Abstract  
内容記述  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, realworld 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 maximumlikelihood (ML) decoding. However, the ML decoding is computationally intractable and it is not shown that their scheme can attain good performance under polynomialtime 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 fixedtovariable 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 ratedistortion 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 variabletofixed 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 fixedtovariable 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.  
書誌情報  発行日 20130325  
学位名  
学位名  博士(科学)  
学位  
値  doctoral  
学位分野  
Science (Kagaku)(科学)  
学位授与機関  
学位授与機関名  
学位授与機関名  University of Tokyo (東京大学)  
研究科・専攻  
Department of Complexity Science and Engineering, Graduate School of Frontier Sciences (新領域創成科学研究科複雑理工学専攻)  
学位授与年月日  
学位授与年月日  20130325  
学位授与番号  
学位授与番号  甲第29525号  
学位記番号  
博創域第870号 