情報源分極に基づく2元情報源の符号化のための基礎的考察

摘要

Recently, a source coding scheme based on source polarization was proposed. In the scheme binary data X~N = (X_0,X_1,...,X_(N-1))is transformed to a binary sequence U~N = (U_0,U_1,...,U_(N-1))by using a certain matrix G_N, where N = 2~n for some integer n≧ 1.If X~N is generated i.i.d. subject to a probability distribution P, only 2~(N(H(P)+δ)) bits of U~N are sufficient to recover X~N with vanishing decoding error probability as n → ∞. However, the choice of such positions of U~N is unknown. In this study, we assume that X~N contains at most 2~l-1 ones. We explicitly give positions of U~N that enable to decode X~N without error. It is shown that such positions have a simple structure.%近年,情報源分極に基づく情報源符号化方式が提案された.この方式では2元データX~N =(X_0,X_1,...,X_(N-1))はある生成行列G_Nを用いて2元系列U~N =(U_0,U_1,...,U_(N-1))に変換される.ここである整数n≧1に対して N= 2~nである.X~Nが確率分布Pに従ってi.i.d.に生成されるとき,微小な復号誤りのもとでX~Nを復号するにはnが十分大きい時にはU~Nのうち2~(N(H(P)+δ))個で十分である.しかしU~Nのそのような位置の選択はよくわかっていない.本稿では,X~Nは高々2~l-1個の1を含むという仮定のもとで,誤りなくX~Nを復号可能なU~Nの位置を与え,その位置が簡単な構成であることを示す.