Universal Slepian-Wolf Source Codes Using Low-Density Parity-Check Matrices

摘要

低密度パリティ検査（LDPC）符号は符号長に伴う線形時間で最尤復号に迫る性能を達成するため、通信路符号化において注目されている。他方、Slepian-Wolf情報源符号化において、LDPC行列を用いた符号が村松らによって提案されている。しかしながら、彼らの提案した符号では最尤復号器が用いられているため、ユニバサル符号ではない。すなわち、彼らの符号では情報源の確率分布をあらかじめ知っている必要がある。他方、LDPC行列を用いたユニバーサルなSlepian-Wolf符号が存在すれば、たとえ情報源の確率分布を知らなかったとしても、符号器の符号化率を達成可能領域に含むすべての情報源において、復号誤り率を符号長に伴って任意に小さくすることができる。本稿では、定常無記憶情報源において、LDPC行列を用いたユニバーサルなSlepian-Wolf符号が存在することを示す。%Low-density parity-check (LDPC) codes become very popular in channel coding, since they can achieve the performance close maximum-likelihood (ML) decoding with linear complexity of the block length. Muramatsu et al. proposed a code using LDPC matrices for Slepian-Wolf source coding. However, since they employed ML decoding, their code is not universal, that is their decoder needs to know the probability distribution of the source. On the other hand, if there exists a universal code using LDPC matrices, we can arbitrary decrease the error probability for all sources whose achievable rate region contains the rate pair of encoders even if the probability distribution of sources is unknown. To this end, we show the existence of a universal Slepian-Wolf source code using LDPC matrices in the case where the source is stationary memoryless.