澁谷 智治

Rank Modulation符号は,フラッシュメモリを構成する各セルの電荷量の大小関係のみを用いて情報を表現する記録符号である.また,Compressed Encoding,はpush up操作を行うことによってメモリの状態遷移を実現するRnak Modulation符号化の一種である.本研究では,Compressed Encodingにおいて記憶容量増大とブロック消去の発生頻度低減を実現する1手法として知られる,遷移グラフの支配集合に基づく符号構成について検討した.この結果,支配集合を構成する新たなアルゴリズムを提案し,さらに,このアルゴリズムが極小支配集合を生成するための十分条件について明らかにしている.また,メモリを構成するセル数が5のときの,極小支配集合を具体的に構成している.

Spatially coupled (SC) low-density parity-check (LDPC) codes are denned by bipartite graphs that are obtained by assembling prototype graphs. The combination and connection of prototype graphs are designated by specifying some parameters, and Kudekar et al. showed that BP threshold of the ensemble of SC LDPC codes agrees with MAP threshold of the ensemble of regular LDPC codes when those parameters are grown up so that the code length tends to infinity. When we design SC LDPC codes with practical code length, however, it is not clear how to set those parameters to enhance the performance of SC LDPC codes. In this paper, we provide the result of numerical experiments that suggest the dependence of error performance of SC LDPC codes over BEC on their design parameters.

sum-product復号法をはじめとするLDPC符号の反復復号法は,符号長nに対してO(n)程度の低計算量で高い誤り訂正能力を発揮する.一方,LDPC符号の符号化に関しては,ごく最近までO(n^2)の計算量を要するアルゴリズムしか知られておらず,符号化と復号の計算量のアンバランスを解決することが大きな課題となっていた.本稿では,LDPC符号の符号化計算量の削減に関する従来の研究を概観するとともに,本稿の著者によって提案された,任意のLDPC符号に対してO(n)の計算量の符号化を実現する手法を紹介する.

Efficient algorithms to solve a system of linear equations have been extensively and deeply investigated in a large number of researches. Among them, the block-triangularization is one of the well-know approaches effective for linear systems defined by matrices with particular characteristics, especially by sparse matrices. In this paper, we propose an encoding algorithm that can be applied to arbitrary linear codes over any finite field and executed with complexity O (w(H)) where w(H) denotes the number of non-zero elements of the parity check matrix H under consideration. By giving our attention to the fact that encoding of a linear code is equivalent to solving a system of linear equations, we propose an encoding algorithm based on the block-triangularization of the part of parity check matrices combining rearrangement of subblocks of them. As the result, any linear codes defined by sparse parity check matrices, such as LDPC codes, can be encoded by the proposed algorithm with complexity O(n) where n denotes the code length.

Recently, Haley and Grant introduced the concept of reversible codes - a class of linear codes encodable by the iterative message-passing algorithm based on the Jacobi method over F_2. They also developed a concrete procedure to construct parity check matrices of reversible codes by utilizing some properties of circulant matrices which is described in terms of polynomials over F_2. In this paper, we investigate the size of circulant matrices considered in the Haley's procedure and clarify the necessary and sufficient condition on the size for which reversible codes based on circulant matrices exist. This condition tells us that no reversible codes based on circulant matrices exist other than those constructed by the Haley's procedure.

Recently, Haley and Grant introduced the concept of reversible codes - a class of linear codes encodable by the iterative message-passing algorithm based on the Jacobi method over F_2. They also developed a concrete procedure to construct parity check matrices of reversible codes by utilizing some properties of circulant matrices which is described in terms of polynomials over F_2. In this paper, we investigate the size of circulant matrices considered in the Haley's procedure and clarify the necessary and sufficient condition on the size for which reversible codes based on circulant matrices exist. This condition tells us that no reversible codes based on circulant matrices exist other than those constructed by the Haley's procedure.

Recently, Mooij et al. proposed sufficient conditions for convergence of the sum-product algorithm, which was stated as the upper bound for the spectral radius of a matrix defined by a probability distribution under consideration. In this paper, we adapt Mooij's sufficient conditions to the decoding problem, and derive a sufficient condition for convergence of the sum-product decoding.

Recently, Mooij et al. proposed sufficient conditions for convergence of the sum-product algorithm, which was stated as the upper bound for the spectral radius of a matrix defined by a probability distribution under consideration. In this paper, we adapt Mooij's sufficient conditions to the decoding problem, and derive a sufficient condition for convergence of the sum-product decoding.

Multi-Poissonアンサンブルを用いて,非正則LDPC符号アンサンブルの2元入力出力対象通信路における条件付きエントロピーの下界を求められることがMontanariによって示されている.この下界は,2元消失通信路の場合,EXIT functionの解析から得られた条件付きエントロピーと一致している.このMontanariの方法を多元に拡張して条件付きエントロピーを求めることを検討する.

Multi-edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles have better performance than other known ensembles. Orlitsky et al. derived the condition for irregular LDPC code ensembles with minimum distance linearly increasing in code length. Nakasendo et al. derived the condition that code ensembles have exponentially decreasing small linear weight codewords for two-edge type LDPC code ensembles which is simple example of multi-edge type LDPC code ensembles. In this letter, we derive the condition for multi-edge type LDPC code ensembles with exponentially decreasing small linear weight codewords.

ある符号のsupport weight distributionは、指定した次元とsupport weightを持つユニークな部分空間の数Extrinsic information function (EXIT)関数は、support weight distributionを用いて正確に記述することができる。本稿では、正則LDPC符号アンサンブルにおける2次の平均support weight distributionを求める方法を与えている。

Jin et al. introduce irregular repeat-accumulate (IRA) codes. IRA codes have a linear-time encoding algorithm. The authors have introduced detailedly represented irregular low-density parity-check code ensembles specified with joint degree distributions between variable nodes and check nodes. In this paper, by using density evolution method [6], we design IRA codes specified with joint degree distributions. Resulting codes have higher thresholds and lower error floors than standard IRA codes.

Since the joint distribution considered in the CCCP decoding presented in the previous work is different from the a posteriori probability considered in the usual sum-product decoding, there is the possibility that the direct comparison of error performance of those decoding algorithms might be unfair. In this paper, we clear up this suspicion by showing that an objective function that is equivalent to the one minimized in the conventional CCCP decoding can be derived from the a posteriori probability distribution treated in the sum-product algorithm. Moreover, we present more efficient implementation of the CCCP decoding.

sum-productアルゴリズムは, 周辺分布を高速かつ精度良く近似する反復アルゴリズムであるが, 収束の保証がないことに起因する近似精度の劣化が指摘されていた.一方, 近年開発されたCCCPと呼ばれるアルゴリズムは, 周辺分布を近似計算する収束保証付きの反復アルゴリズムであり, sum-productアルゴリズムの代替アルゴリズムとなり得る.本稿では, sum-productアルゴリズムとCCCPの関係について概観し, 更にCCCPに基づく復号アルゴリズムに関する最近の研究成果について紹介する.

Belief Propagation(BP)復号は、線形符号を表すタナーグラフにサイクルが無ければビット毎の最大事後確率復号になる。サイクルがあるタナーグラフを持つ線形符号にBP復号を適用する場合には、特に長さ4のサイクルが存在すると復号性能が劣化する事が知られている。 Yedidiaらはパンクチャビットを加えパリティ検査方程式を書き換える事によって、低密度ではないパリティ検査行列から一一般化パリティ検査行列と呼ばれる低密度なパリティ検査行列を得る変換を提案した。本研究では、Yedidiaらの変換の特殊な場合であるの長さ4のサイクルを取り除くパリティ検査行列の変換に注目し、消失通信路で発生した消失を復元する場合には、この変換によって得られた行列を用いて復元に失敗する消失パターンの集合は、元の行列を用いて復元に失敗する消失パターンの集合に含まれる事を示す。また、ハミング符号を例に、この変換をほどこすことによって復元できる消失パターンが増える符号が存在することを示す。

Richardsonらは、Density Evolution(DE)と呼ばれる符号長無限大の復号性能のアンサンブル平均を求める手法を提案した。またアンサンブルに含まれるほとんど全ての符号の復号性能がアンサンブル平均に一致するconcentrationと呼ばれる性質が成り立つこととそのアンサンブル平均がDEによって求まる復号性能に収束することを示した。本論文では、Kasaiらの提案した、従来の非正則LDPC符号アンサンブルをより詳細に規定したアンサンブルとそのDEについてもconcentrationが成り立つことを示している。

BurshteinとMillerは,非負係数多項式の係数の指数部に関する漸近的な評価を用いることによって,二部グラフから定義される従来の低密度パリティチェック符号のアンサンブルについて,平均重み分布の指数部の漸近的な評価を与えた.本論文では,この方法を用いて,従来のアンサンブルの一般化である詳細に規定された低密度パリティチェック符号のアンサンブルについて,平均重み分布の指数部を漸近的に評価している.また,そのアンサンブルと従来のアンサンブルとの平均重み分布の指数部の関係を数値的に明らかにし,さらに与えられた従来のアンサンブルより大きい典型的最小距離を持つアンサンブルの例を具体的に与えている.

sum-productアルゴリズムに基づくLDPC符号の復号アルゴリズムは少ない計算量で優れた性能を示すことが知られている.一方,CCCPに基づく従来の復号アルゴリズムはsum-product復号アルゴリズムを上回る性能を示すことが期待される反面,計算量が極めて多い.本報告では,sum-product復号アルゴリズムに匹敵する計算量で実行可能な,CCCPに基づく新しい復号アルゴリズムを提案する.また,符号長の短いLDPC符号に対し,提案アルゴリズムがsum-product復号アルゴリズムよりも良い性能を示す数値実験例を与える.

著者らによって、低密度パリティ検査符号に関する従来のアンサンブルC(η,λ,ρ)をより詳細に表現したアンサンブルC_1(η,π)が提案され、そのアンサンブルに関する密度発展法が開発されている。しかし、その導出にはる命題の成立を仮定しており、その命題の成立は実験によって支持されているにすぎなかった。本報告では、まずより単純な命題の成立を仮定することにより、C_1(η,π)に関する従来の密度発展法が得られる事を示す。さらに、C_2(η,π)⊂C_1(η,π)なるアンサンブルC_2(η,π)を提案し、いかなる命題を仮定することなく、C_2(η,π)に関する密度発展法が得られることを示す。

本稿では、regular low-density parity-check(LDPC)符号の最小距離に対する、Tannerの下界の精度について検証する。まず、Steiner systemとして知られる組み合わせデザインに基づいて二つのクラスのregular LDPC符号を構成し、これらの符号に対してTannerの下界を定式化する。次に、これらの符号のクラスの一方がEG-LDPCを含むことを明らかにし、EG-LDPC符号に対するTannerの下界が、BCH限界に基づく最小距離の下界と一致することを明らかにしている。

1991年に一般化ハミング重み(GHW)の概念がWeiによって導入されて以来, GHWに関する多くの研究成果が報告されている.q元Reed-Muller(RM)符号に関しては, q=2の場合のGHWの計算方法がWeiによって与えられ, HeijnenとPellikaanによってこの計算方法が一般のqに対して拡張された.最近, 筆者らは任意の[n, k]線形符号に対して適用可能なGHWの下界を提案した.また, 与えられた符号Cに対して容易に計算可能なある定数g(C)を導入し, Cがt-th rank MDS(Maximum Distance Separable)となる, 即ちt次のGHW d_t(C)に関してd_t(C)=n-k+tが成り立つためのtの十分条件がg(C)+1≤t≤kで与えられることを示した.更に, m変数u次のq元RM符号に関してはu, m, qを用いてg(C)を定式化した.小文では, 2元RM符号Cについて, tがg(C)+1≤t≤kを満たすことがCがt-th rank MDSとなるための必要十分条件となることを示している.

Turbo-Codeは, シャノン限界に近いビット誤り率 (BER) を達成する誤り制御方式として注目されている. しかしながら, 反復復号による大きな復号遅延が問題となっている. そこで本稿では, 反復復号の構成復号器で用いられるBCJRアルゴリズムを近似的に実現する並列処理可能なアルゴリズムを提案し, これにより演算による遅延を減少できることを示している. さらに, 提案アルゴリズムを用いた場合のTurbo-Codeが (1) SN比に対するBER特性, (2) 反復回数に対するBERの収束特性のいずれにおいても, BCJRアルゴリズムを用いた場合とほぼ同程度の性能を達成することを計算機シミュレーションにより確認している.

In this paper, the tightness of lower bounds for generalized Hamming weights proposed in is investigated in the case of some algebraic geometric codes. It is shown that g^*&le;g where g^* denotes the parameter which was introduced in to give the lower bound of generalized Hamming weights and g denotes the genus of the curve C_<ab>. This implies that the range for which our lower bound agrees with the true weight is not narrower than the conventional one.

従来の代数幾何符号の一般化として, アフィン代数多様体上の線形符号が三浦により提案されている. 更に, この符号の構成に単項式順序とそれによって定まるGrobner基底を導入すると, そのFeng-Rao設計距離により符号の最小距離の非自明な下界が得られる. 小文では, 三浦の構成法によるアフィン代数多様体上の線形符号について, その一般化ハミング重みの下界を与える. まず, 単項式順序とそれによって定まるGrobner基底を用いて, 部分符号を定める検査行列の系列に係わる一種の従属関係を明らかし, これを用いて一般化ハミング重みの下界式を導出する. また, このとき定まる定数g^*に対し, μ(>g^*)次の一般化ハミング重みが, 符号の検査点数をγとするときμ+γで与えられ, 真の一般化ハミング重みに一致することを示す. 更にFeng-Raoによって導入されたwell-behaving pairと呼ばれる概念を用いることにより, μ>g^*における一般化ハミング重みの下界が更に改善されることを示す.

BCH符号,Goppa符号,交代式符号などのように,有限体GF(q^m)上の符号Cの部分体部分符号として構成されるGF(q)上の符号C|_<GF(q)>の中に優れた性能を持つ符号の存在することが知られている.また,検査点数が比較的小さい場合,代数幾何符号の一クラスであり高性能な符号を多く含むことが知られている曲線C_<ab>上の留数Goppa符号よりも,拡大BCH符号が優れていることが示されている.一方,BCH符号はReed-Solomon(RS)符号の部分体部分符号であること,またRS符号は種数0の曲線上の代数幾何符号として構成されることが知られている.従って,より一般の代数幾何符号の部分体部分符号に関する考察は重要な意義を持つと考えられる.任意の曲線上の留数Goppa符号の部分体部分符号の次元に関する限界式は[3]で与えられている.しかしながら,この限界式は,もとの符号の検査点数が大きくなると必ずしも厳密なものとは言えない.また,実用に際しては符号構成の容易さも重要となる.そこで本稿では,曲線をC_<ab>に制限することにより,部分体部分符号の次元に関する限界式の改善を行う.

通信路符号化において、情報源の性質が既知の場合、その性質を利用することによって、より高度な誤り制御を行うことができると考えられる。小文では日本語を模した文脈自由文法で表される言語を想定し、その文構造を符号化することにより誤り制御を行う手法を提案する。また単語を符号化する際の効率の良い符号語割り当て法について提案する。