(57)【要約】【課題】各信号を整数の系列に変換し、１組のビットプレーンを編成し、１組の相関信号を圧縮することを、信号変換および量子化によって行うことができる。【解決手段】各ビットプレーンに対し逆累算器を適用し、シフトされたビットのビットプレーンを生成して所定の置換を行い、ビットプレーンを生成する。さらに、各ビットプレーンを、１組ビットのブロックに分割する。レート適応型基本符号に従って各ブロックに対しシンドロームビットを生成する。その後、シンドロームビットを復元し、元の相関信号を回復する。対応する信号の各ビットプレーンに対し、ビット確率推定値を生成する。シンドロームビットおよびビット確率推定値を使用してビットプレーンを復元する。ビット確率推定値から、ビットプレーンのすべてに対応する整数の系列を復元し、逆量子化および逆変換を使用して整数の系列から元の信号を回復する。
2008511239.tif 000002
【特許請求の範囲】
【請求項１】
１組の相関信号を圧縮する方法であって、
各信号を整数の系列に変換することと、
各整数の系列を１組のビットプレーンとして編成することと、
各ビットプレーンに対し、シフトされたビットのビットプレーンを生成するために逆累算器を適用することと、
所定の置換に従って置換されたビットのビットプレーンを生成するために、シフトされたビットの各ビットプレーンを置換することと、
置換されたビットの各ビットプレーンを１組のビットのブロックに分割することと、
基本符号に従ってビットの各ブロックに対し、すべてが前記１組の相関信号の圧縮であるシンドロームビットを生成することと
を含む１組の相関信号を圧縮する方法。
【請求項２】
前記信号間の前記相関は、時間的である請求項１に記載の方法。
【請求項３】
前記信号間の前記相関は、空間的である請求項１に記載の方法。
【請求項４】
前記相関信号は、ビデオ系列の画像である請求項２に記載の方法。
【請求項５】
前記相関信号は、最初に量子化される請求項１に記載の方法。
【請求項６】
前記変換することおよび前記編成することは、
各信号を１組の係数に変換することと、
前記１組のビットプレーンを生成するために各係数の組を量子化することと
を含む請求項１に記載の方法。
【請求項７】
各画像を１組のマクロブロックに分割することと、
各マクロブロックを１組の係数に変換することと、
各係数の組を前記１組のビットプレーンに量子化することと
をさらに含む請求項４に記載の方法。
【請求項８】
前記基本符号は、積符号である請求項１に記載の方法。
【請求項９】
前記基本符号は、拡張ハミング符号である請求項１に記載の方法。
【請求項１０】
各相関信号に対して生成するシンドロームビットの数を確定することをさらに含む請求項１に記載の方法。
【請求項１１】
前記シンドロームビットの数は、該シンドロームビットの復号器からのフィードバックを使用して確定される請求項１０に記載の方法。
【請求項１２】
前記シンドロームビットの数は、利用可能な補助情報に関し前記相関信号の条件付きエントロピーの推定値を使用して確定される請求項１１に記載の方法。
【請求項１３】
前記補助情報は、前記符号器によって先に復元された信号である請求項１２に記載の方法。
【請求項１４】
前記対応する信号に対して生成される前記シンドロームビットの数は、該対応する信号における冗長性のレベルに従って適応的に変化する請求項１に記載の方法。
【請求項１５】
追加のシンドロームビットを増分的に生成することをさらに含む請求項１４に記載の方法。
【請求項１６】
前記追加のシンドロームビットを生成することは、
所定のスケジュールに従って前記基本符号を１組の長さの短い基本符号に分割することと、
前記対応するブロックを、各長さの短い基本符号に対し１つの長さの短い符号を有する１組の長さの短いブロックに分割することと、
前記長さの短いブロックに対する前記長さの短い基本符号の前記シンドロームと、先に生成されたシンドロームビットとを使用して、前記追加のシンドロームビットを生成することと
をさらに含む請求項１５に記載の方法。
【請求項１７】
前記長さの短い基本符号は、拡張ハミング符号である請求項１６に記載の方法。
【請求項１８】
前記長さの短い基本符号は、単一パリティ検査符号の積である請求項１６に記載の方法。
【請求項１９】
第１の信号は、従来の方法で圧縮される請求項１３に記載の方法。
【請求項２０】
前記ビットプレーンは、Ｇｒａｙ符号の形式である請求項１に記載の方法。
【請求項２１】
前記信号のうちの１つに対応する前記シンドロームビットを復元することは、
前記対応する信号の各ビットプレーンに対し、該ビットプレーンの各ビットに対するビット確率推定値を生成することと、
前記ビットプレーンに対応する前記シンドロームビットと前記ビット確率推定値とを使用して前記ビットプレーンを復元することと、
前記対応する信号の前記ビットプレーンのすべてに対応する前記整数の系列を復元することと、
該整数の系列から前記信号を復元することと
をさらに含む請求項１に記載の方法。
【請求項２２】
前記ビット確率推定値は、先に復元された信号によって決まる確率分布から、且つ前記対応する信号の先に復元されたビットプレーンを条件として生成される請求項２１に記載の方法。
【請求項２３】
前記確率分布は、ガウス関数である請求項２２に記載の方法。
【請求項２４】
前記確率分布は、ラプラシアン関数である請求項２２に記載の方法。
【請求項２５】
１組のトレーニング信号から前記確率分布を推定することをさらに含む請求項２２に記載の方法。
【請求項２６】
前記先に復元された信号は、従来の方法で取得される請求項２２に記載の方法。
【請求項２７】
前記ビットプレーンは、復元中に、最上位ビットから最下位ビットへの順序で処理される請求項２１に記載の方法。
【請求項２８】
前記ビットプレーンは、復元中に、最下位ビットから最上位ビットへの順序で処理される請求項２１に記載の方法。
【請求項２９】
生成されるシンドロームビットの数と所定の基本符号分割スケジュールとに応じて前記基本符号を選択することをさらに含む請求項１に記載の方法。
【請求項３０】
前記ビットプレーンを復元することは、
復元するシンドロームビットの数と所定の基本符号分割スケジュールとに応じて前記基本符号を選択することと、
前記ビットプレーンに対する最終的なビット確率推定値を生成するために、交互に、所定数の反復に対し、前記ビット確率推定値を使用して累積符号を復号し、且つ該ビット確率推定値および復元される前記シンドロームビットを使用して前記選択された基本符号を復号することと、
前記ビットプレーンを復元するために、前記最終的なビット確率推定値を閾値処理することと
をさらに含む請求項２１に記載の方法。
【請求項３１】
前記最終的な閾値処理されたビット確率推定値が剰余類符号語に対応するか否かを判断することと、
真である場合、前記最終的な閾値処理されたビット確率推定値を前記ビットプレーンとして受け入れることと、
偽である場合、前記最終的な閾値処理されたビット確率推定値を拒絶することと
をさらに含む請求項３０に記載の方法。
【請求項３２】
前記拒絶することは、前記シンドロームビットの前記生成中に該シンドロームビットの数を増大させることをさらに含む請求項３１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には信号を圧縮する分野に関し、特に、誤り訂正通信路符号を使用する相関信号の圧縮に関する。
【背景技術】
【０００２】
データ格納および信号通信の分野における基本的な問題は、入力信号を圧縮し、その後歪みなしに、または最小限の歪みで圧縮信号を再現する実際的な方法の開発である。本明細書で説明する信号は、デジタルデータの形式であってもよいということが理解されるべきである。
【０００３】
信号を圧縮し再現する方法は、一般に、音声、画像またはビデオファイルとともに発生する大量のデータを格納または転送するシステムにおいて非常に重要な部分である。
【０００４】
多くの重要な場合、圧縮する必要のある信号は、相関性があるが、それら信号の生成は、何らかの方法で分散されている。たとえば、信号は、何らかの理由で、互いに通信しないセンサによって取得される。これは、単一の符号器を使用して信号を符号化することができないことを意味する。たとえば、符号化される信号は、異なるカメラによって取得されたシーンの画像であり、それらカメラのすべてから単一の中央プロセッサに、カメラが互いに直接通信することなく、画像の符号化されたバージョンを送信することが望まれる。
【０００５】
D. SlepianおよびJ.K. Wolfは、彼らの論文において、しばしば「分散情報源符号化（distributed source coding）」と呼ぶこの種の状況について述べている。これについては、D. SlepianおよびJ.K. Wolf著「Noiseless Coding of Correlated Information Sources」、IEEE Transactions on Information Theory, vol.19, pp.471-480, 1973を参照願いたい。彼らは、略式に「符号器が通信しないようにすることによりいかなる圧縮能力も失わない」と述べることができる驚くべき結果を証明した。言い換えれば、相関信号の２つの符号器が通信しない場合に達成することができる圧縮は、２つの符号器が互いに通信する場合に達成することができる圧縮と正確に同じである。
【０００６】
図１は、従来技術によるSlepian-Wolf符号化システム１００のブロック図を示す。分散信号源１１０の相関した出力信号Ｘ１０１およびＹ１０２は、互いに通信しない２つの符号器１２１〜１２２に別々に送出される。第１の符号器１２１は、圧縮された信号ストリームＸ１３１を生成し、第２の符号器１２２は、圧縮された信号ストリームＹ１３２を生成する。それら圧縮された信号１３１〜１３２は、復号器１４０に送出され、復号器１４０は、信号ＸおよびＹ１４１を復元するように試みる。
【０００７】
互いに通信しない符号器による相関信号の符号化を、「Slepian-Wolf圧縮」と呼ぶ。SlepianおよびWolfは、研究において、情報理論によって設定される圧縮限界に焦点を当てた。彼らは、Slepian-Wolf圧縮符号器および復号器を実施する実際的な方法については何も述べていない。
【０００８】
Wynerは、恐らく、符号器に誤り訂正通信路符号の「シンドローム」を送信させることにより、Slepian-Wolf圧縮を理論的に実施することができるという見解を最初に示した人である。これについては、A.D. Wyner著「Recent Results in the Shannon Theory」、IEEE Transactions on Information Theory, vol.20, pp.2-10, 1974を参照願いたい。しかしながら、彼は、符号化し、且つ復号する実際的な方法に対する建設的な詳細については何も提供しなかった。
【０００９】
１９７４年と２０世紀の終わりとの間において、実際的なSlepian-Wolf圧縮方式を考案することに関し実質的な進歩は何もなかった。たとえば、Sergio Verduは、５０年に及ぶ情報理論の自身の１９９８年の論評において、「応用の可能性があるにも関わらず、Slepian-Wolf符号化の概念的な重要性は、実際のデータ圧縮において反映されなかった（S. Verdu著『Fifty years of Shannon Theory』、IEEE Transactions on Information Theory, vol.44, pp.2057-2078, 1998）。建設的なSlepian-Wolf方式に対し、（Wynerによって）明らかにされた誤り訂正通信路符号との関連を超える進歩は、ほとんどなかった」と指摘した。
【００１０】
SlepianおよびWolfは、分散された相関信号を、後に完全に回復することができるような方法で圧縮する理論に焦点を当てた。彼らの理論は、A. WynerおよびJ. Zivによる分散相関情報源の非可逆圧縮にまで広がった。これについては、A.D. WynerおよびJ. Ziv著「The rate-distortion function for source coding with side information at the decoder」、IEEE Transactions on Information Theory, vol.22, pp.1-10, 1976を参照願いたい。しかしながら、SlepianおよびWolfと同じように、WynerおよびZivもまた、証明した境界に達するいかなる建設的な方法についても述べていない。
【００１１】
「非可逆圧縮」では、圧縮信号の復元は、元の信号に完全には一致しない。代りに、復元された信号は、元の信号と一定の歪みレベルでしか一致しない。非可逆圧縮は、信号を完全に復元することを目指していないため、可逆圧縮より高い圧縮レートを達成することができる。非可逆Slepian-Wolf圧縮を「Wyner-Ziv圧縮」と呼ぶ。
【００１２】
誤り訂正通信路符号からのシンドロームを使用することに基づく、Slepian-WolfおよびWyner-Ziv圧縮に対する何らかの建設的な方法について、最近の数年間の間にいくつか述べられている。
【００１３】
エントロピー
Slepian-Wolf圧縮システムに対する性能測度は、圧縮される信号またはデータのエントロピーに基づく。「エントロピー」の概念は、情報理論を紹介しているシャノン（Shannon）の最初の論文まで遡る。これについては、C.E. Shannon著「A Mathematical Theory of Communication」、Bell Sys. Tech. Journal, Vol.27, pp.379-423, 1948を参照願いたい。その題材は、情報理論に関する教科書に詳細に扱われている。たとえば、T.M. CoverおよびJ.A. Thomas著「Elements of Information Theory」、1990の第２章を参照願いたい。
【００１４】
Ｘが、いくつかのアルファベットＡＸから選択された、確率分布ｐＸ（ｘ）＝Ｐｒ｛Ｘ＝ｘ｝を有する離散確率変数である場合、確率変数ＸのエントロピーＨ（Ｘ）は、下式（１）によって定義される。
【００１５】
【数１】
2008511239.tif 000003
【００１６】
シャノンは、自身の１９４８年の論文における自身の有名な符号化定理において、データＸによって放出されるＮ個のシンボルの長い系列を、レートがＨ（Ｘ）ビット／シンボル以上であるビットストリームに圧縮することができ、その後、損失なしに回復することができるということを証明した。このように、信号のエントロピーは、その圧縮可能性の基本的な測度である。
【００１７】
図２は、従来の符号化システム２００を示す。符号器２１０は、情報源Ｘ２２０からのＮ個のシンボルを含む信号Ｘ２０１を、ＮＨ（Ｘ）ビット以上の圧縮されたビットストリームＸ２０２まで圧縮する。そのビットストリームＸ２０２は、その後、復号器２３０によって、復元された信号Ｘ２０３を生成するために使用される。
【００１８】
ここで、正確に２つの相関する情報源ＸおよびＹがあり、情報源ＸおよびＹによって生成された信号が相関する確率変数ＸおよびＹであるとする。確率変数は、同時確率分布ｐＸＹ（ｘ，ｙ）＝Ｐｒ（Ｘ＝ｘ，Ｙ＝ｙ）に従って選択されるものとする。以下の定義が有用である。
【００１９】
周辺確率分布ｐＸ（ｘ）およびｐＹ（ｙ）は、下式によって定義される。
【００２０】
【数２】
2008511239.tif 000004
【００２１】
条件付き確率分布ｐＸ（ｘ｜ｙ）は、下式によって定義される。
【００２２】
【数３】
2008511239.tif 000005
【００２３】
確率変数（Ｘ，Ｙ）の対の同時エントロピーは、下式（２）であると定義される。
【００２４】
【数４】
2008511239.tif 000006
【００２５】
また、条件付きエントロピーＨ（Ｘ｜Ｙ）は、下式（３）であると定義される。
【００２６】
【数５】
2008511239.tif 000007
【００２７】
同時エントロピーＨ（Ｘ，Ｙ）および条件付きエントロピーＨ（Ｘ｜Ｙ）は、式Ｈ（Ｘ，Ｙ）＝Ｈ（Ｙ）＋Ｈ（Ｘ｜Ｙ）によって関連付けられる。
【００２８】
シャノンの情報源符号化定理によれば、図３に示すもの等の符号化システム３００は、Ｎが大きい限り、成功裡に、相関する情報源ＸおよびＹ３２０からの信号（Ｘ，Ｙ）３０１のＮ個の対を、ＮＨ（Ｘ，Ｙ）ビット以上の圧縮されたビットストリーム３０２まで圧縮し（３１０）、その後復元された信号ＸおよびＹを回復する（３３０）ことができる。図３に示す圧縮システムの符号器３１０は、両情報源ＸおよびＹの出力にアクセスすることができ、すなわち情報源は、分散していない。
【００２９】
SlepianおよびWolfは、２つの符号器がシンボルＸおよびＹに別々にアクセスすることができ、互いに通信することができない、図１に示すもの等の符号化システムは、Ｎが大きいものとし、情報源Ｘにアクセスすることができる符号器が少なくともＮＨ（Ｘ｜Ｙ）ビットを送出し、情報源Ｙにアクセスすることができる符号器が少なくともＮＨ（Ｙ｜Ｘ）ビットを送出し、送出されたビットの総数が少なくともＮＨ（Ｘ，Ｙ）である限り、元の信号（Ｘ，Ｙ）のＮ個の対を依然として回復することができることを示した。
【００３０】
図４は、Slepian-Wolf定理を要約しており、垂直軸は、情報源Ｙによって送出されるビットを示し、水平軸は、情報源Ｘによって送出されるビットを示す。輪郭４０１は、復号器における復元が成功するために２つの符号器が送出しなければならないビットの最小数を示す。輪郭は、復元が可能な領域４１１と、復元が不可能な領域４１２とにグラフを分割する。
【００３１】
シンドロームベースの圧縮方法の他の適用
分散情報源からの相関信号を圧縮する上述した適用のほかに、シンドロームベースの圧縮方法の他の適用がある。特に、シンドロームベースの圧縮方法は、圧縮の計算負荷の大部分を符号器から復号器に移し、このため、非常に単純な送信機および受信機で符号化したい場合に適当である。これについては、引用により本明細書に援用されるVetro他による関連特許出願を参照願いたい。たとえば、送信装置がデジタルカメラを備えた携帯電話またはセンサである場合、それらは、送信している時にほとんど電力を消費しないことが重要であり、単純な符号器が望まれる。
【００３２】
したがって、シンドロームベースの符号化方法は、比較的単純な符号器を有するビデオ圧縮方法で使用されることが提案された。これについては、たとえば、PuriおよびRamchandran著「PRISM: A New Robust Video Coding Architecture Based on Distributed Compression Principles」、Proc. 40th Allerton Conference on Communication, Control and Computing, October 2002およびA. Aaron他著「Towards practical Wyner-Ziv coding of video」、Proc. IEEE International Conference on Image Processing, September 2003を参照願いたい。それらの符号器の不都合については、関連特許出願に詳述されている。
【００３３】
線形ブロック誤り訂正符号
上述したように、Wynerは最初に、１９７４年、Slepian-Wolf圧縮を、線形ブロック誤り訂正符号のシンドロームを送信することによって行うことができると指摘した。以下は、かかる線形ブロック誤り訂正符号に関する関連背景情報を提供する。誤り訂正符号に関するさらなる情報は、多くの教科書に見ることができ、たとえば、本明細書で論考する題材については、S. LinおよびD.J. Costello, Jr.による教科書、「Error Control Coding, 2nd Edition」、Pearson Prentice Hall, 2004の最初の４章において、より詳細に説明されている。
【００３４】
本明細書において「符号」という場合は、特に、線形ブロック誤り訂正符号を意味する。これらの符号の後ろにある基本概念は、Ｎ＞ｋである場合に、Ｎ個のシンボルのストリングを使用して、ｋ個のシンボルのストリングを符号化するということである。誤り訂正符号の従来の適用では、破損した符号化メッセージを復号し訂正するために追加のＮ−ｋビットを使用する。
【００３５】
Ｎ個のシンボルの任意のストリングを、「ブロック」または「語」と呼ぶ場合がある。符号の制約をすべて満足するＮ個のシンボルのブロックを、「符号語」と呼ぶ。シンボルを、ｑ元アルファベットから引き出す。非常に重要な特別な場合は、ｑ＝２の時である。その場合、符号は「２進」符号である。
【００３６】
図５は、線形ブロック誤り訂正符号を使用する従来の通信路符号化装置５００を示す。情報源５１０は、ｋ個のシンボルｕ［ａ］を含む情報ブロック５０１を生成し、シンボルはｑ元アルファベットから引き出される。情報ブロックは、誤り訂正符号の符号器５２０に渡され、Ｎ個のシンボルの符号語ｘ［ｎ］５０２に変換される。
【００３７】
そして、符号語は、通信路５３０を通して送信され、通信路５３０において、符号語は、破損して信号ｙ［ｎ］５３１になる。そして、破損した信号ｙ［ｎ］が復号器５４０に渡され、通信路の雑音が比較的小さいとすると、復号器５４０は、情報ブロックｕ［ａ］５０１の復元５０９を出力する。
【００３８】
符号のパラメータ
符号Ｃを、ブロック長Ｎを有するｑｋ個のあり得る符号語のセットによって定義する。パラメータｋを、符号の「次元」と呼ぶことがある。符号は、通常、Ｎおよびｋが大きい場合に、より有効である。しかしながら、パラメータＮおよびｋのサイズが増大するに従い、通常、符号のための復号器の複雑性も同様に増大する。符号の「レート」ＲをＲ＝ｋ／Ｎによって定義する。
【００３９】
２つの符号語間のハミング距離を、２つの符号語において異なるシンボルの数として定義する。符号の距離ｄを、符号における符号語のすべての対の間の最小ハミング距離として定義する。ｄの値が大きい符号ほど、誤り訂正能力が大きい。パラメータＮ、ｋおよびｑを有する符号を、［Ｎ，ｋ］ｑ符号と呼ぶ。距離ｄもまた既知である場合、それらを［Ｎ，ｋ，ｄ］ｑ符号と呼ぶ。
【００４０】
ガロア体
線形符号を、パリティ検査行列によって表すことができる。これらの行列を定義するためには、まず、ｑ元シンボルを加算し乗算する方法が必要である。ガロア体とも呼ばれる有限体の理論は、ｑ元シンボルに対する加法および乗法を定義する方法を提供する。ガロア体の詳細な説明については、S. LinおよびD. Costelloによる先に引用した教科書の第２章を参照願いたい。
【００４１】
ガロア体では、ｑ元アルファベットからの任意の２つのシンボルが加算または乗算される場合、答えは同じアルファベットからの元である。乗法および加法の単位元があり、各元は、乗法および加法の逆元を有するが、加法単位元は乗法の逆元を有していない。
【００４２】
ガロア体をＧＦ（ｑ）と示し、ｑはアルファベットの元の数である。ガロア体を、その加法および乗法テーブルに関して定義することができる。最も単純なガロア体は、２つの元０および１を有するＧＦ（２）であり、０は加法の単位元であり、１は乗法の単位元である。ＧＦ（２）の加法規則は、０＋０＝１＋１＝０および０＋１＝１＋０＝１であり、ＧＦ（２）の乗法規則は、０×０＝０×１＝１×０＝０および１×１＝１である。
【００４３】
ガロア体を、素数または素数の整数乗である任意のｑに対して定義することができる。任意のガロア体の加法規則および乗法規則については、誤り訂正符号に関する教科書において説明されている。特に記述のない限り、本明細書で述べる和および乗算のすべてを、ＧＦ（２）の規則を使用する２進シンボルの和および乗算であると想定されるべきである。
【００４４】
符号のパリティ検査行列表現
任意の２つの符号語の和もまた符号語である場合、ブロック符号は、「線形」である。Ｎ個のシンボルを含む２つの符号語の各々の和を、個々のシンボルを一度に１つ合計することによって得られるＮ個のシンボルの符号語であると定義する。たとえば、ＧＦ（２）を使用する２つの符号語（１１１０１００）および（０１１１０１０）の和は、（１００１１１０）である。
【００４５】
線形符号を、パリティ検査行列によって表すことができる。［Ｎ，ｋ］ｑ符号を表すパリティ検査行列を、Ｍ行およびＮ列のｑ元シンボルの行列によって定義する。パリティ検査行列のＮ個の列は、符号のＮ個のシンボルに対応する。行列の線形独立行の数は、Ｎ−ｋである。
【００４６】
パリティ検査行列の各行は、制約を表す。特定の行によって表される制約に含まれるシンボルは、その行に非ゼロシンボルを有する列に対応する。パリティ検査制約により、それらのシンボルのＧＦ（ｑ）に対する重み付き和が強制的にゼロに等しくなる。たとえば、２進符号の場合、下式（４）のパリティ検査行列Ｈは、下式（５）〜（７）の３つの制約を表す。
【００４７】
【数６】
2008511239.tif 000008
【００４８】
ここで、ｘ［ｎ］は、第ｎビットの値である。これは、［Ｎ＝７，ｋ＝４，ｄ＝３］ｑ＝２ハミング符号に対するパリティ検査行列である。
【００４９】
誤り訂正符号のための符号器および復号器
線形［Ｎ，ｋ］ｑ符号のための符号器は、ｋ個のシンボルからなる情報ブロックｕ［ａ］を、Ｎ個のシンボルからなる符号語ｘ［ｎ］に変換する。線形［Ｎ，ｋ］ｑ符号のための復号器は、送信された符号語の歪んだバージョンｙ［ｎ］を再び情報ブロックｕ［ａ］に変換する。
【００５０】
送信された符号語の歪んだバージョンは、サンプルが誤り訂正符号と同じｑ元アルファベットからの値をとる、語ｙ［ｎ］である場合がある。かかる入力信号を受け入れる復号器は、「硬入力」復号器と呼ぶことが多い。かかる復号器は、通信路により符号語のｑ元シンボルが幾分か低い確率で破損して他のｑ元シンボルになる場合に有用である。かかる通信路に対する最適な硬入力復号器は、ｙ［ｎ］からの最短距離を有する符号語ｘ［ｎ］を出力する。
【００５１】
適用によっては、受け取った信号を、まず「コスト関数」に変換し、その後、そのコスト関数を復号器に入力する。コスト関数は、各シンボルの各あり得る状態に対するコストを指定するベクトルである。
【００５２】
かかる入力コスト関数を受け入れる復号器を、「軟入力」復号器と呼ぶことが多い。ブロック長が３である２進符号の場合、軟入力復号器のコスト関数例は、［（０．１，０．３），（０．２，０．４），（０．２５，０．１５）］である。このコスト関数は、第１のビットに値「０」を割り当てるコストが０．１であり、第１のビットに値「１」を割り当てるコストが０．３であり、第２のビットに値「０」を割り当てるコストが０．２である等を意味する。
【００５３】
最適な軟入力復号器は、コスト関数が与えられると最低のあり得る合計コストを有する符号語を返す。たとえば、先の段落の例の３ビット符号が２つの符号語（０００）および（１１１）を有した場合、符号語（０００）が返される。それは、符号語（０００）が０．１＋０．２＋０．２５＝０．５５のコストを有し、符号語（１１１）は０．３＋０．４＋０．１５＝０．８５のコストを有するためである。軟入力復号器におけるコストは、受信信号および通信路モデルが与えられると、各ビットに対する対数尤度の負数に等しいように取られることが多い。
【００５４】
誤り訂正符号に対し最適な硬入力復号器または軟入力復号器を構成することは、一般に、誤り訂正符号に対し符号器を構成することよりはるかに複雑な問題である。この問題は、特に、Ｎおよびｋが大きい符号の場合に複雑になる。この理由のため、実際に使用される多くの復号器は、最適ではない。非最適な硬入力復号器は、受け取った語に対して最も近い符号語を確定しようと試みるが、その試み通りになることは保証されておらず、非最適な軟入力復号器は、最低コストで符号語を特定しようと試みるが、その試み通りになることは保証されていない。
【００５５】
軟入力情報が得られる場合には、最初に軟入力のすべてに対し閾値処理してシンボル判定を行い、後にそのシンボル判定を硬入力復号器に入力することにより、硬入力復号器を依然として使用することができる。しかしながら、かかる手続きにより、通常、性能が、軟入力復号器を使用して達成することができる性能より大幅に低くなる。
【００５６】
符号の最適な性能に対する限界
情報理論は、最適な復号器のあり得る性能に対して重要な限界を与える。これらの結果のいくつかは、C.E. Shannon（シャノン）により、「A Mathematical Theory of Communication」、Bell Syst. Tech. Journal, vol 27, pp.379-423, 623-656, 1948において最初に証明された。
【００５７】
直観的な用語で表現すれば、シャノンは、いかなる雑音のある通信路もその雑音性に関連する容量Ｃを有するということ、およびその容量が符号のレートより大きい時、且つその時に限り、最適な符号の最適な復号器がすべての誤りを訂正することができるということを示した。
【００５８】
長年、実際的な誤り訂正符号化方法は最適な性能からかけ離れていたため、シャノン限界は、単に理論上重要なだけであるように見られていた。しかしながら、この十年の間、種々の符号、最も顕著にはターボ符号、低密度パリティ検査符号および直列連接累積符号が、シャノン限界に極めて近い性能を達成した。これらの符号は、すべて、反復メッセージパッシング方法を使用して復号される。直列連接累積符号は、特に、本発明に関連するため、後により詳細に論考する。
【００５９】
たとえば、加法的白色ガウス雑音（ＡＷＧＮ）の場合、シミュレーションにより、低密度パリティ検査符号および反復メッセージパッシング復号器を使用してシャノン限界の０．００４５ｄＢ内で１０−５のビット誤り率を得ることができるということが示された。これについては、S.-Y. Chung、G. Forney、T. RichardsonおよびR. Urbanke著「On the Design of Low-Density Parity-Check Codes Within .0045 dB of the Shannon Limit」、IEEE Communications Letters, vol.5, pp.58-60, February 2001を参照願いたい。
【００６０】
反直観的に、非最適な復号器を使用することは、通信路符号化問題に対するシャノン限界に非常に近づくための重要な要素であるということを理解することが重要である。この明らかな逆説の説明は、シャノン限界に近づくために、非常に大きいブロック長および次元の符号を使用しなければならないということである。かかる長い符号を、通常、最適な復号器を使用して実際に復号することはできない。
【００６１】
ファクターグラフ
符号をファクターグラフで表すことができる。これについては、F.R. Kschischang、B.J. FreyおよびH.-A. Loeliger著「Factor Graphs and the Sum-Product Algorithm」、IEEE Transactions on Information Theory, vol.47, pp.498-519, February 2001、G.D. Forney, Jr.著「Codes on Graphs: Normal Realizations」、IEEE Transactions on Information Theory, vol. 47, pp.520-549, February 2001並びにR.M. Tanner著「A Recursive Approach to Low-Complexity Codes」、IEEE Transactions on Information Theory, vol.27, pp.533-547, September, 1981を参照願いたい。
【００６２】
ファクターグラフを、種々の異なる形式から引き出すことができる。本明細書で従う形式は、Kschischang他によって述べられているようなものである。ファクターグラフは、「変数ノード」および「ファクターノード」と呼ばれる２種類のノードを含む２部グラフである。変数ノードは、ファクターノードにしか連結されず、その逆もまた同様である。本明細書では、ファクターノードを、正方形を使用して描き、変数ノードを、円を使用して描き、変数ノードとファクターノードとの間の連結を、対応する円および正方形を連結する線によって示す。ファクターノードが与える制約の種類を表すために、ファクターノード内部にシンボル、すなわち「＋」を描く場合がある。これは、本明細書で使用する従来の表記法である。
【００６３】
符号の最も単純なファクターグラフ表現は、パリティ検査行列表現に対応する表現である。かかるファクターグラフでは、パリティ検査行列のＮ個の列に対応するＮ個の変数ノードがあり、パリティ検査行列のＭ個の行に対応するＭ個のファクターノードがある。
【００６４】
図６は、上式（４）によって与えられたパリティ検査行列による２進ハミング符号に対するファクターグラフを示す。このファクターグラフ表現では、変数ノード６０１は、符号語のＮ個のシンボルに対応する。これらの変数ノードは、「送信」シンボルと呼ばれることもある。ファクターノード６０２は、パリティ検査制約に対応する。
【００６５】
符号のより一般的なファクターグラフ表現が可能である。特に、変数ノードのセットは、符号を定義する助けとなるが、符号語のＮ個のシンボルのうちの１つではない「状態変数ノード」と呼ばれるノードを含む場合もある。
【００６６】
ファクターノードは、パリティ検査制約より一般的な制約を表す場合もある。たとえば、ファクターノードは、それに連結する変数ノードの許容可能な構成が何らかの小さい符号の符号語に対応するもののみであるような制約を表すことができる。このように、大きい符号を小さい符号から再帰的に構築することができる。
【００６７】
シンドローム
任意の［Ｎ，ｋ］ブロック符号に対し、任意の語の「シンドローム」を、その語が符号語である場合に、すべて０である１組のＮ−ｋ個の線形独立シンボルとして定義する。符号のシンドロームを、パリティ検査行列を使用して定義することが多い。符号のいかなる符号語も、その符号に対するパリティ検査行列によって表されるパリティ検査制約のすべてを満足する。符号語ではない他の語は、パリティ検査制約のすべては満足しない。語ｙがＮ個の０および１の行ベクトルによって表される場合、語ｙの「シンドローム」ｓは、行ベクトルであり、下式（９）によって定義することができる。
【００６８】
【数７】
2008511239.tif 000009
【００６９】
ここで、上付きのＴは、転置行列を表す。Ｈが（Ｎ−ｋ）×Ｎパリティ検査行列であるとすると、シンドロームｓは、Ｎ−ｋ成分を有する。ｙが符号語である場合、シンドロームｓは、必然的にＮ−ｋ個の０のベクトルである。
【００７０】
たとえば、語ｙ＝（００００００１）の場合、上式（４）で与えられるハミング符号に対するパリティ検査行列を使用すると、その語のシンドロームはｓ＝（００１）である。これは、語ｙに対し、Ｈの最初の２つのパリティ検査は満足されるが、３番目は満足されないことを意味する。
【００７１】
符号のファクターグラフを、そのシンドロームビットも含むように変更することができる。単に、シンドロームビットに対応する新たな変数ノードを追加し、シンドロームノードを他のノードに、他の符号語シンボルに対するそれらの関連を適当に反映するような方法で付随させる。
【００７２】
たとえば、図７は、ハミング符号の拡張ファクターグラフ７００を示し、３つの変数ノードは、シンドロームを表す。図７において、変数ノード７０３に対する３つのシンドロームノードｓ［１］、ｓ［２］およびｓ［３］は、パリティ検査ファクターノード７０２に付随するシンドロームノード７０１によって表される。
【００７３】
なお、符号の通常のファクターグラフでは、送信シンボルを表すＮ個の変数ノードは、符号語に対応する集合的な状態にある。一方、シンドローム変数ノードを含む拡張ファクターグラフでは、送信シンボルを表すＮ個の変数ノードは、いかなる集合的な状態にあってもよく、シンドローム変数ノードがすべて０である場合にのみ符号語の状態にある。
【００７４】
より一般的には、任意の誤り訂正符号に対するシンドロームビットを、所望のシンドロームビットに対応するシンドロームノードを含むように、符号を表すファクターグラフを拡張することにより、グラフィカルに定義することができる。
【００７５】
符号の剰余類符号語を、シンドロームをすべて満足する語であるように定義する。シンドロームがすべて０である場合、剰余類符号語は、通常の符号語である。
【００７６】
シンドロームベースの情報源符号化
第１の符号器が第２の信号を考慮せずに第１の信号を単純に符号化し、第２の符号器が２つの信号の間の相関を考慮しようと試みる場合のSlepian-Wolf問題を考える。このSlepian-Wolf問題の特定の場合を、「補助情報を伴う情報源符号化」と呼ぶ。Ｙを、直接符号化される信号とする場合、これは、Ｈ（Ｘ，Ｙ）ビット／シンボルに近い総レートに対し、第１の符号器がＨ（Ｙ）ビット／シンボルに近いレートで圧縮し、第２の符号器がＨ（Ｘ｜Ｙ）ビット／シンボルに近いレートで圧縮することを意味する。
【００７７】
Wynerは、上述した自身の１９７４年の論文において、補助情報を伴う情報源符号化に関連する符号化問題を解決する方法について述べている。この概念を、以下の小さい例を用いて例示する。この例は、後に明らかになる理由で現実世界の信号の圧縮に対する現実的な方法として解釈されるべきではない。
【００７８】
情報源ＸおよびＹがともに、７つのビットからなる信号を放出したものとし、それらビットは、ランダムであり、独立同一分布し、等しく０および１である可能性があるが、決して単一ビットより大きく互いから異なることはないという意味で相関する。例として、情報源Ｘが信号Ｘ＝（００１０１００）を放出し、情報源Ｙが信号Ｙ＝（００１１１００）を放出する。これらの２つの信号は１ビットしか異ならない。かかる同時信号により、両信号を検査する従来の符号化システムは、符号化するために合計１０ビットを必要とする。すなわち、信号Ｙを符号化するための７ビットに、信号Ｘの信号Ｙとの差を符号化するための３ビットを足したものである。ＸのＹとの差を符号化するために３ビットが必要である理由は、ＸがＹと異なる可能性がある７つの位置があり、それに加えてまったく異ならない可能性もあり、合計８つの可能性があって、それを符号化するために３ビットを要するためである。上記の方法は、符号器が情報源ＸおよびＹの両方にアクセスすることができる場合に実施されることができる。
【００７９】
２つの符号器のうちの１つにしかアクセスすることができない場合、シンドロームベースの方法は、７ビットを使用して信号Ｙを直接送信することができ、信号Ｘの符号器は、［Ｎ＝７，ｋ＝４，ｄ＝３］ハミング符号に関して信号Ｘのシンドロームを送出する。たとえば、情報源Ｘが（００１０１００）を放出し、符号のパリティ検査行列が上式（４）によって与えられる場合、式（９）を使用して計算されたシンドロームは（０１０）である。このように、シンドロームベースの方法では、符号器により合計１０ビットが送出される。
【００８０】
シンドロームベースの方法における復号器は、以下のように動作する。復号器は、信号Ｙが圧縮なしに正しく送出されたことを知っており、Ｘが１ビットまでしかＹとは異ならないことを知っており、シンドロームを受け取る。このため、復号器は、そのシンドロームを満足し、Ｙとは１ビットまでしか異ならない語を探索する。［Ｎ＝７，ｋ＝４，ｄ＝３］ハミング符号という構造のため、これらの条件を満足する１つの語が常に正確に存在する。
【００８１】
実際的なシンドロームベースの符号化方法の要件
上記例は、シンドロームベースの符号化装置の背景にある基本概念を示すが、上述したシンドロームベースの符号器および復号器は、実際的な適用には使用が限られている。現実世界の適用で有用であるためには、シンドロームベースの符号化方法は、以下の要件を満足しなければならない。
【００８２】
第１に、本方法は、単純に２つの値０または１をとるビットではなく、広範囲のあり得る値を有する整数値のシンボルを符号化することができなければならない。現実の適用で現れる大部分の信号は、整数または実数値である。たとえば、ビデオストリームにおける画素の強度値は、通常、０から２５５までの整数値をとる。実数値信号は、標準的に、整数値に量子化され、通常、歪みを最小限にするために多数の量子化レベルが使用される。
【００８３】
第２に、方法は、非常に高い圧縮レートまで符号化することができなければならない。ビデオ圧縮等の多くの適用では、情報源（カメラ）によって取得された信号に大量の冗長性がある。優れた圧縮方式は、冗長性のすべてを利用することができなければならず、そのため適切な方法で、たとえば１００：１の割合まで圧縮することができなければならない。
【００８４】
第３に、方法は、レート適応型でなければならない。従来技術によるシンドローム符号化装置は、いずれもレート適応型ではない。このため、それらの符号化装置は、複雑性が異なりビットレートが変化する現実世界の信号には本質的に有用ではない。多くの状況では、情報源ストリームにおけるエントロピーの量は、瞬間毎に変化する。たとえば、ビデオストリームは、冗長性のレベルが高いため非常に圧縮性が高い、隣接するフレームが同一であるセクションと、それに続く、冗長性のレベルが低いためはるかに圧縮性が低い、高速に変化するシーンのフレームとを有している場合がある。方法は、平滑に且つ基礎にある符号を変化させることなく圧縮レートを変更することができなければならない。
【００８５】
第４に、方法は、増分的でなければならない。言い換えれば、符号器は、一定数のシンドロームビットを送出し、その後、復号器によってさらなるビットが要求される場合、先に送出された情報を復号するビットを無駄にする必要なく有用な追加のビットを送出することができなければならない。この増分的特性は、小さいフィードバック通信路が存在する適用には非常に有用であり、そのため、復号器は、復号化が成功したか否かを符号器に通知することができる。
【００８６】
第５に、方法は、可逆圧縮についてSlepian-Wolfが述べた境界および非可逆圧縮についてWyner-Zivが述べた境界に近い圧縮効率に達しなければならない。これを可能にするために、方法は、通信路符号化問題に対しシャノン限界に近づく誤り訂正符号に基づく必要がある。
【００８７】
第６に、方法は、単純な符号化方法および復号方法を使用しなければならない。特に、符号器および復号器の複雑性は、情報源シンボルの数Ｎに対し妥当な方法で、たとえば、線形に拡大縮小しなければならない。これは、多数の情報源シンボルが通常、シャノンが可能であることを約束した境界近くの性能を達成するために、合わせて圧縮される必要があるため必要である。特に、符号器を極めて単純にすることが望まれる。
【００８８】
直列連接累積符号
本発明は、いわゆる「繰返し累積符号」、すなわち「積累積符号」から導出された符号と、「拡張ハミング累積符号」と呼ばれる符号とを使用する。まとめて、この種の符号を、「直列連接累積」（ＳＣＡ）符号と呼ぶ。ＳＣＡ符号とは、ここでは、特に、符号器が、基本符号の符号器のセットと、それに続く置換と、それに続くレート１累算器符号とからなる符号を意味する。
【００８９】
繰返し累積（ＲＡ）符号は、ＳＣＡ符号の一例であり、基本符号は、繰返し符号である。これについては、D. Divsalar、H. JinおよびR.J. McEliece著「Coding Theorems for 'turbo-like' codes」、Proceedings of the 36th Allerton Conference on Communication, Control, and Computing, pp.201-210, Sept.1998を参照願いたい。
【００９０】
図８は、ＲＡ符号の符号器８００を示す。情報源Ｘ８１０は、信号Ｘ８１１を放出する。符号器は、まず、信号Ｘの各ビットを繰り返す（８２０）。そして、符号器は、結果としての繰り返されたビット８２１のセットを置換する（８３０）。置換されたビット８３１は、その後累算器８４０に送出され、送信ビット８４１のセットになる。なお、累算器をレート１符号とみなすことができる。
【００９１】
ＲＡ符号の一例として、３つの［Ｎ＝３，ｋ＝１，ｄ＝３］繰返し符号を使用する小さい［Ｎ＝９，ｋ＝３］ＲＡ符号を考える。この繰返し符号は、単純に、１ビットを（１１１）として符号化し、０ビットを（０００）として符号化する。ＲＡ符号の情報ブロックが（１０１）である場合、繰返し符号８２０は、これを（１１１０００１１１）に変換する。置換８３０は、何らかの一定規則に従って、これらのビットを置換する。ＲＡ符号は、ランダムに選択される置換を使用して設計されることが多い。この例において、置換は、（１２３４５６７８９）→（３６９２７４１５８）であるとし、これは、第１のビットが第３の位置に置換され、第２のビットが第６の位置に置換され、等を意味する。そして、ビット（１１１０００１１１）は、（１０１０１１０１１）に置換される。ＲＡ符号の最後の段階は、レート１符号である累算器である。累算器８４０は、置換されたビットの移動和、すなわちモジュロ２を維持する。このため、（１０１０１１０１１）は、累算器により語（１１００１００１０）に変換される。これは、ＲＡ符号器によって送信される符号語８４１である。なお、ＲＡ符号のレートは、それらの構成符号がすべて同一である場合、その構成繰返し符号のレートと等しい。
【００９２】
図９は、繰返し符号９０１、変数ノード９０２、ファクターノード９０３および送信ビット９０４を含む、先に考慮したＲＡ符号例のファクターグラフ９００を示す。
【００９３】
ＲＡ符号は、通常、反復メッセージパッシング方法を使用して復号される。かかる方法では、通信路からの証拠は、レート１累算器のＢａｈｌ，Ｃｏｃｋｅ，Ｊｅｌｉｎｅｋ，Ｒａｖｉｖ（ＢＣＪＲ）復号器に供給される。これについては、L.R. Bahl、J. Cocke、F. JelinekおよびJ. Raviv著「Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate」、IEEE Transactions on Information Theory, vol.20, pp.284-287, 1974を参照願いたい。ＢＣＪＲ復号器は、累算器符号の入力および構造が与えられると、置換されたビットの各々に対する１組の最適な事後確率推定値を出力する。そして、これら推定値は、繰返し符号の復号器に供給され、復号器は、置換されたビットに対する新たな１組の事後確率推定値を出力する。各繰返し符号に対する事後推定値は、入力に対して最適である。推定値は、累積符号のＢＣＪＲ復号器に再び供給される。確率推定値が、それらのもっともあり得る値に投影される時に、符号語に対応するまで、または一定数の反復に達するまで、プロセスを反復する。ＲＡ符号の下位符号の各々に対して復号器が最適であっても、ＲＡ符号に対する説明した復号方法は、最適ではないということが理解されるべきである。
【００９４】
ＲＡ符号と積累積（ＰＡ）符号との相違は、ＰＡ符号では、繰返し符号の代りに、単一パリティ検査（ＳＰＣ）符号の積符号が使用されるということである。これについては、J. Li、K.R. NarayananおよびC.N. Georghiades著「Product Accumulate Codes: A Class of Codes With Near-Capacity Performance and Low Decoding Complexity」、IEEE Transactions on Information Theory, vol.50, pp.31-46, January 2004を参照願いたい。積符号では、すべての符号語シンボルは、同時に、２つの別々の単一パリティ検査（ＳＰＣ）符号に対する符号語の一部である。ＳＰＣ符号の積符号は、特に、単純な構造を有し、すべての符号語シンボルは、２つのパリティ検査を満足する。
【００９５】
図１０は、単一パリティ検査符号の［Ｎ＝９，ｋ＝４，ｄ＝４］積符号に対する、ファクターノード１００１および変数ノード１００２を含むファクターグラフ１０００を示す。このファクターグラフの実質的に水平な方向におけるパリティ検査を、「水平」パリティ検査と呼び、実質的に垂直な方向におけるパリティ検査を、「垂直」パリティ検査と呼ぶ。
【００９６】
Ｌ個の水平パリティ検査とＭ個の垂直パリティ検査とを有するＳＰＣ符号の積符号は、（Ｌ−１）（Ｍ−１）／（ＬＭ）に等しいレートを有する。このため、ＬおよびＭが大きいように選択される場合、ＳＰＣ符号の積符号のレートは、１に近い。符号を構成する積符号のレートが高い場合、ＰＡ符号は、１に近い高レートとなる。
【００９７】
ＰＡ符号は、ＲＡ符号と同様に復号される。主な相違は、積符号に対する最適な復号器が実現可能でないため、積符号に対し適切な復号化が使用されるということである。
【００９８】
拡張ハミング累積（ＥＨＡ）符号もまた、ＲＡ符号に類似しているが、ＲＡ符号の繰返し符号の代りに、拡張ハミング符号が使用される。これについては、IEEE Communications Letters, 2004に提出された、M. IsakaおよびM. Fossorier著「High Rate Serially Concatenated Coding with Extended Hamming Codes」並びにD. DivsalarおよびS. Dolinar著「Concatenation of Hamming Codes and Accumulator Codes with High Order Modulation for High Speed Decoding」、IPN Progress Report 42-156, Jet Propulsion Laboratory, Feb. 15, 2004を参照願いたい。拡張ハミング符号は、以下のパラメータを有する。すなわち、２以上のすべての整数Ｒに対し、Ｎ＝２Ｒ、ｋ＝Ｎ−Ｒ−１およびｄ＝４である。このため、最初のいくつかの拡張ハミング符号は、パラメータ［Ｎ＝４，ｋ＝１，ｄ＝４］、［Ｎ＝８，ｋ＝４，ｄ＝４］、［Ｎ＝１６，ｋ＝１１，ｄ＝４］および［Ｎ＝３２，ｋ＝２６，ｄ＝４］を有する。
【００９９】
拡張ハミング符号は、事前確率推定値が与えられると事後確率推定値を正しく確定する実際的な復号器を有する。したがって、ＥＨＡ符号を、拡張ハミング符号のこれらの復号器と累算器のＢＣＪＲ復号器とを使用して復号することができる。ＰＡ符号に比較してＥＨＡ符号の１つの利点は、レートの等しいＰＡ符号に比較して短いブロック長で高レートに設計することができるということである。
【０１００】
繰返し累積符号における繰返し符号の代りに、他の何らかの符号を用いることにより、他のＳＣＡ符号を容易に構成することができる。
【０１０１】
図１１は、ＳＣＡ符号のファクターグラフ１１００の一般的な構造を示す。このファクターグラフの最上層で使用される「基本符号」１１０１は、ＳＣＡ符号のタイプによって決まる。基本符号は、ＲＡ符号の場合には繰返し符号であり、ＰＡ符号の場合には単一パリティ検査符号の積であり、ＥＨＡ符号の場合には拡張ハミング符号である。各基本符号に連結された変数ノード１１０２の数は、その基本符号のブロック長に等しい。ブロック１１０３は、置換であり、ブロック１１０４は、ファクターノードであり、ブロック１１０５は、送信ビットである。
【０１０２】
多段復号器
通信路符号化問題に対して、多段復号器を設計することも可能である。これについては、H. ImaiおよびS. Hirikawa著「A New Multilevel Coding Method Using Error-Correcting Codes」、IEEE Transactions in Information Theory, vol.23, pp.371-376, May 1977を参照願いたい。多段復号器を使用して、多レベルブロック変調符号を復号した。これについては、たとえば、上に引用したLinおよびCostelloによる本の第１９章を参照願いたい。
【０１０３】
従来技術によるシンドロームベースの分散圧縮方法
最近では、実際的なシンドロームベースの圧縮方法に対し、いくつかの提案がなされているが、いずれも上に列挙した要件をすべては満足しない。シンドロームベースの復号器の以下の特徴が望まれることを想起されたい。すなわち、（１）広範囲の整数値入力を圧縮しなければならない、（２）高圧縮レートが可能でなければならない、（３）レート適応型でなければならない、（４）増分的でなければならない、（５）Slepian-WolfおよびWyner-Ziv限界に近づかなければならない、（６）複雑性が低くなければならない。
【０１０４】
一手法は、トレリス（重畳）符号を使用する。これについては、S.S. PradhanおよびK. Ramchandran著、Distributed Source Coding Using Syndromes(DISCUS): Design and Construction, IEEE Transactions on Information Theory, vol 49, pp.626-643, March 2003を参照願いたい。彼らの手法は、量子化器を使用するため、広範囲で実数値入力および整数入力を処理することができる。しかしながら、彼らの符号は、非常に高い圧縮レートは、可能でなく、レートは、実質的に一定である。適応的に符号化することができることが非常に望ましい。さらに、PradhanおよびRamchandranの手法は、本明細書で説明する意味で増分的ではない。彼らの手法は、容量に近づく通信路符号に基づいていないため、その圧縮性能は制限される。性能は、また、その方法では硬入力（ビタビ）復号器しか使用されないため、通常、軟入力情報を使用することができないという事実により制限される。要約すると、PradhanおよびRamchandranは、要件のうちのいくつかは満足するが、高圧縮レート、適切且つ増分的レート適応性および情報理論的限界に近づく性能という要件は満足しない。
【０１０５】
別の手法は、シンドロームベースの復号器の基礎として、低密度パリティ検査（ＬＤＰＣ）符号を使用する。これについては、A. Liveris、Z. XiongおよびC. Georghiades著「Compression of binary sources with side information at the decoder using LDPC codes」、IEEE Communications Letters, vol.6, pp.440-442, October 2002を参照願いたい。この手法は、広範囲での整数入力を可能としない。非常に高いレートで適切に実行するＬＤＰＣ符号を生成することが困難であるため、この方法は、また、非常に高い圧縮レートを可能としない。この手法は、また、ビデオ信号等、時間の経過によりデータレートが変化する信号に対して重要である、増分的なレート適応性も可能としない。
【発明の開示】
【発明が解決しようとする課題】
【０１０６】
要約すると、実際的なシンドロームベースの符号化方法に対し、上に列挙した要件のすべてを満足する従来技術による方法はなく、これらの要件のすべてを満足することが本発明の目的である。
【課題を解決するための手段】
【０１０７】
本発明は、シンドローム信号として１つまたは複数の他の入力信号と相関するＮ個のサンプルの入力信号を符号化する方法およびシステムを提供する。さらに、本発明は、元の入力信号を回復するようにシンドロームビットストリームを復号する対応する方法を提供する。
【０１０８】
本方法を、まず入力信号を整数に変換し且つ量子化することにより、実数値信号または整数値信号の非可逆圧縮に適用することができる。したがって、信号のすべてを、入力信号を都合のよい範囲を有する整数に変換する標準の変換および量子化方法により任意に前処理する。
【０１０９】
符号化は、以下のように動作する。初期信号を、従来の方法で符号化する。初期符号化信号は、すべての情報源からのすべての後続する信号に対する初期補助情報としての役割を果たす。他のすべての信号を、ビットプレーンの形式でシンドロームビットに対してのみ符号化する。
【０１１０】
各ビットプレーンに対して送出されるシンドロームビットの数を、符号器により、復号器からのフィードバック通信路を使用して、または信号間の条件付き確率分布に基づく推定から確定する。
【０１１１】
各ビットプレーンに対して使用される直列連接累積（ＳＣＡ）符号は、送出する必要のあるシンドロームビットの数に基づく。符号を、基本符号、たとえば、積符号または拡張ハミング符号を連続的にＳＣＡ符号に分割することにより、増分的に調整する。これにより、符号化レートが適応的になり、これは、従来技術によるシンドローム符号化装置において得られなかった非常に望ましい特徴である。基本符号を、シンドローム復号器も既知である所定のスケジュールに従って分割する。
【０１１２】
ＳＣＡ符号に基づくシンドローム符号器は、以下のようにシンドロームビットを生成する。まず、情報源からのビットプレーンのビットを逆累算器に入力した後、逆置換に入力し、その後、ＳＣＡ符号の基本符号におけるパリティ検査を使用してシンドロームビットを確定する。
【０１１３】
復号方法は、以下のように入力信号を復元する。利用可能な補助情報およびシンドロームビットを使用して符号化信号を復元する。復元後、復号信号を、次の信号の補助情報として使用し、以下同様に続ける。
【０１１４】
各信号に対して送出されるシンドロームビットの数を、所定のブロック符号分割スケジュールとともに使用して、復号器におけるブロック符号のサイズを確定する。
【０１１５】
各信号を、多段復号器を使用して復号される１組のビットプレーンによって表す。ビットプレーンを、所定の順序で復号する。確率分布に基づき、第１のビットプレーンのビットの事前確率を推定する。後続するビットプレーンにおける確率は、先に復号されたビットプレーンの結果を条件として、確率分布に基づく。
【０１１６】
受け取ったシンドロームが正しく満足されるように適切に変更された直列連接累積符号の復号器に対する入力として、事前確率を使用する。
【発明を実施するための最良の形態】
【０１１７】
シンドローム符号器の全体構造
図１２は、本発明による符号器１２００を示す。符号器は、変換１２１０、量子化器１２２０、整数符号１２３０、圧縮モジュール１２４０、フィードバック復号器およびエントロピー推定器１２５０並びにシンドローム符号器１２６０を含む。変換、量子化器、符号化器および圧縮器は、符号化される各入力信号１２０１〜１２０３に対して直列に連結されている。
【０１１８】
最初の２つの任意のステップでは、信号を、２Ｂ個のあり得る値をとるＮ個の整数によって表すことができるように変換し（１２１０）、量子化する（１２２０）。ここでは、Ｂをビットプレーンの数と呼ぶ。使用することができる変換の種類の例には、離散コサイン変換（ＤＣＴ）がある。
【０１１９】
次に、整数を符号化して１２３０、Ｂ個のビットプレーン１２３１にする。
【０１２０】
そして、各ビットプレーンを別々に圧縮する（１２４０）。第１の信号１２０１のビットプレーンを、従来の方法で符号化する。他のすべての信号をシンドロームビットに符号化する。
【０１２１】
シンドローム符号器１２６０によって生成されるシンドロームビット１２６１の数を、２つの方法で推定することができる。第１の方法では、フィードバック復号器１２５０が、復号器が先に送信され符号化された信号を復号することができたか否かを示すことができるものとする。符号器は、復号が成功したという肯定応答を受け取るまでビットを送出し続ける。この方法は、後述するように、シンドロームビットを増分的に送出することができるという事実に依存する。この方法には、最小数のシンドロームビットが送出され、且つ復号が常に成功するという利点がある。
【０１２２】
第２の方法では、条件付き確率分布に基づいて条件付きエントロピーを推定する。シンドロームビットの数を、条件付きエントロピーの数より多くし、それにより復号が成功することを確信することができる。
【０１２３】
圧縮方法の選択
各信号に対し、従来の符号器を使用して信号を送出するか、またはシンドロームビットを使用することによって送出するかを判断する。Ｔ個の信号に、ＸＡ、ＸＢ、ＸＣ、・・・、ＸＴと付す。適用によっては、異なる信号上のラベルを時間指標として解釈することができる。簡単のために、信号の同時確率分布ｐ（ＸＡ，ＸＢ，ＸＣ，・・・，ＸＴ）はマルコフ構造を有する、すなわち、下式（１０）であるとする。
【０１２４】
【数８】
2008511239.tif 000010
【０１２５】
以下、同時確率分布がマルコフ構造を有していない場合に行うことができる変更について説明する。
【０１２６】
マルコフ構造を想定すると、符号器および復号器は、以下のように動作する。信号ＸＡを、他のいかなる信号との相関も関係なく、従来の方法で約Ｈ（ＸＡ）個のビットに符号化する。信号ＸＢを、約Ｈ（ＸＢ｜ＸＡ）個のシンドロームビットに圧縮し、信号ＸＣを、約（ＸＣ｜ＸＢ）個のシンドロームビットに符号化するといったことを行う。復号器は、信号ＸＡを回復する。回復された信号ＸＡを使用して信号ＸＢを回復し、回復された信号ＸＢを使用してＸＣを回復するといったことを行う。
【０１２７】
解決すべき問題は、符号器が信号のすべてにアクセスすることができない場合であっても、先に復号された信号を使用して、次の信号を復号する方法である。一般に、多くの信号を用いる一般的な分散情報源符号化問題を、一度に１つの補助情報を伴う情報源符号化（ＳＣＳＩ）問題を解決することによって解決することができる。
【０１２８】
同時確率分布が単純なマルコフ構造を有していない場合であっても、分布は、通常、ベイズネットワークとしてモデル化することができる構造を有する。たとえば、同時確率分布の構造は、下式であるものとする。
【０１２９】
【数９】
2008511239.tif 000011
【０１３０】
次の信号を回復するために、まず２つの先の信号を回復し、それら先の信号の両方によって決まる条件付き確率分布関数を使用して次の信号を回復する。２つの先の信号を従来の方法で取得することができるということが留意されるべきである。
【０１３１】
それら信号間の同時確率分布が単純なマルコフ構造を有するものとする。このため、第１の信号を従来の方法で符号化し、且つ復号し、他のすべての信号に対してシンドロームビットを使用し、それらを、先に復元された信号からの補助情報を使用して逐次復元する。
【０１３２】
前処理
符号器は、入力としてＮ個の整数サンプルの形式の信号を取得する。各サンプルの整数値は、２Ｂ個の範囲のあり得る値を有し、Ｂは整数である。たとえば、Ｂが６である場合、各サンプルは、６４個のあり得る値をとることができる。
【０１３３】
信号が異なるフォーマットを有する場合、前処理ステップ１２１０および１２２０を実行することができる。たとえば、信号が２Ｂより大きい実数値または整数を含む場合、量子化により、信号を２Ｂの範囲のあり得る値を有する整数に変換することができる。
【０１３４】
別法として、量子化器１２２０を、変換ステップ１２１０の前に置くことができる。たとえば、符号化される信号が２次元画像を有する場合に、変換ステップを使用することができる。各画像をマクロブロックに分割することができ、各マクロブロックにＤＣＴ１２１０を適用することができる。そして、ＤＣＴの係数を量子化する（１２２０）。かかるマクロブロック変換は、信号内の相関を低減するために有用であり、多くの画像およびビデオ圧縮方法の標準的な部分である。
【０１３５】
変換係数を、それらの重要度に応じて異なる数のビットプレーンに量子化することが望まれる場合がある。かかる場合、同じ重要度を有する係数をすべてグループとして別々に符号化する。重要な点は、前処理により、各信号が、各々が２Ｂ個のあり得る値を取ることができるＮ個の整数値サンプルのグループに変換されることが保証されるということである。
【０１３６】
本発明の好ましい実施の形態では、Ｎは、数千以上の程度の非常に大きい数である。本明細書での例の説明を扱い易くするために、それより小さいＮを用いる例を使用する。大きいＮの値が好ましい理由は、大きいブロック長の符号化および復号方法は、上述した最適な情報理論的情報源符号化限界に近づくことができるためである。通信路符号化問題に対する最適な限界に近づくために、大きいブロック長の符号を使用し、同様に、分散情報源符号化問題に対する最適な限界に達するために、長いかまたは大きい信号を処理する符号器および復号器を使用する。
【０１３７】
ビットプレーン整数符号の選択
信号のＮ個の整数の各々を、整数符号１２３０によって符号化する（１２３１）。たとえば、整数が０から１５までの範囲である場合、４つのビットプレーンにわたるもっとも簡単な符号化では、０を００００に、１を０００１に、２を００１０に、３を００１１に、４を０１００に、等のようにマップする。Ｇｒａｙ符号等の他の符号を使用してもよい。
【０１３８】
直列連接累算符号を使用するシンドロームの計算
最初の信号を従来の方法で符号化し（１２４０）、後続する信号をシンドロームビット１２６１に符号化する。シンドロームビットを、ＳＣＡ符号を使用するシンドローム符号器１２６０によって生成する。上述したように、本発明には、ＰＡ符号およびＥＨＡ符号が好ましい。
【０１３９】
Ｎ個の整数の各々は、２Ｂ個のあり得る値のうちの１つをとることができる。したがって、ここでは、各ビットプレーンに対して１つのＢ個のＳＣＡ符号のセットを使用する。各ビットプレーンに対し、使用するＳＣＡ符号のレートを適応的に調整することができる。
【０１４０】
たとえば、Ｎを、ＬおよびＭがおよそ等しい大きさの整数であり、積Ｎ＝ＬＭに因数分解することができる場合には、ＰＡ符号を使用することができる。各ビットプレーンに対して最高レートのＰＡ符号は、ＳＰＣ符号の単一の積を使用する。最高レートのＰＡ符号は、レート（Ｌ−１）（Ｍ−１）／ＬＭを有する。
【０１４１】
別法として、Ｎが２のべき乗の和であるとすると、ＥＨＡ符号を使用することができる。たとえば、Ｎ＝１９２である場合、［Ｎ＝１２８，ｋ＝１２０］拡張ハミング符号および［Ｎ＝６４，ｋ＝５７］拡張ハミング符号を含むＥＨＡ符号を使用することができる。この例では、合計１５のシンドロームビットに対し、［Ｎ＝１２８，ｋ＝１２０］符号は、８つのシンドロームビットを生成し、［Ｎ＝６４，ｋ＝５７］符号は、７つのシンドロームビットを生成する。
【０１４２】
各ビットプレーンに対し、使用する特定の符号を、復号が成功するために十分なシンドロームビットが送出されるように調整する。言い換えれば、本発明による符号化は、レート適応型である。
【０１４３】
ＰＡ符号に対するシンドロームビットの確定
図１３は、シンドロームビットが追加されたＰＡ符号の拡張ファクターグラフ１３００を示す。この拡張ファクターグラフを、ＰＡ符号のシンドロームビットの符号器のための基礎として使用することができる。変数ノード１３０５は、情報源ビットであり、上に付随し、且つ積符号側の変数ノード１３０１〜１３０２は、シンドロームビットである。ブロック１３２０は、置換であり、グラフは、また、変数ノード１３０３およびファクターノード１３０４も含む。
【０１４４】
図１４は、対応する符号器１４００を示す。情報源Ｘ１４１０は、信号Ｘ１４０１を生成する。単一ビットプレーンのＮ個のビットを逆累算器１４２０に送出する。逆累算器は、隣接するビットのモジュロ２和を確定する。第１のビットは、常に、０とモジュロ２加算される。たとえば、ビットのＮ＝６系列（１０１１１０）は、逆累算器に送出されると、（１１１００１）に変換される。ここでは、逆累算器から出るビットを「シフトされたビット」１４２１と呼ぶ。
【０１４５】
シフトされたビットを、ＰＡ符号を定義するために使用する置換の逆を使用して置換する（１４３０）。
【０１４６】
シフトされ置換されたビット１４３１を、ＰＡ符号の単一パリティ検査の積に対応する矩形に配置し、各行および列のモジュロ２和を確定する（１４４０）。これらのモジュロ２和は、シンドロームビット１４４１である。
【０１４７】
符号化を説明する等価な方法では、各ビットプレーンにおけるＮ個のビットを、ファクターグラフのそれらの変数ノード位置に割り当て、その後、他の変数ノードをすべてすでに確定されている変数ノードに基づいて確定する。まず、情報源ビットからシフトされたビットを確定し、次に、シフトされたビットからシンドロームビットを確定する。
【０１４８】
ＥＨＡ符号に対するシンドロームビットの計算
図１５は、シンドロームビットが付加されたＥＨＡ符号の拡張ファクターグラフ１５００を示す。この拡張ファクターグラフを、ＥＨＡ符号のシンドロームビットの符号器のための基礎として使用することができる。
【０１４９】
シンドロームビットを計算するために単一パリティ検査の積の代りに拡張ハミング符号１５１０のパリティ検査を使用する場合、ＥＨＡ符号のシンドロームビットを符号化するステップは、最後のステップまで、図１３に示すようなＰＡ符号に対するステップと同一である。変数ノード１５０５は、情報源ビットであり、ハミング符号１５１０の上に付随する変数ノード１５０１は、シンドロームビットである。ブロック１５２０は、置換であり、グラフは、また、変数ノード１５０３およびファクターノード１５０４も含む。
【０１５０】
ＰＡ符号のレートの増分的変更
図１６に示すように、ＰＡ符号を使用する場合、各ビットプレーンに対して使用されるシンドロームビットの数は、以下のように増分的に増大することができる。Ｎ＝６４であり、最高レートのＰＡ符号が単一パリティ検査符号の８×８積を使用する場合、図１６は、この符号を８×８格子１６００で表し、１つの変数ノード１６０１は、各行に関連するシンドロームビットを表し、別の変数ノード１６０２は、各列に関連するシンドロームビットを表す。格子の各正方形１６０３は、２つのパリティ検査、すなわち、同じ行の他の変数ノードおよびシンドロームビットのすべてを含む１つのパリティ検査と、同じ列の他の変数ノードおよびシンドロームビットのすべてを含む１つのパリティ検査とに関係する変数ノードを表す。この符号は、各行に１つ、且つ、各列に１つの１６個のシンドロームビットを使用する。
【０１５１】
追加の８つのシンドロームビットを送出する必要があると想定する。こうするためには、図１７に示すように、８×８積符号を表すグラフ１７００を、２つの８×４積符号１７０１〜１７０２に分割する。ここで、積符号１７０１における４つのビットの８つの行に対応する８つのシンドロームビットを確定し送出する。積符号１７０２における４つのビットの８つの行に対応する８つのシンドロームビットは、送出せず、８つのビット行に対してすでに送出されたシンドロームビットから、且つ積符号１７０１に対してすでに送出されたシンドロームビットから、直接確定する。
【０１５２】
さらなるビットを送出する必要がある場合、８×４積符号の各々をさらに４×４積符号に分割することができ、それら積符号のうちの１つの列に対応するシンドロームビットを送出することができる。ここでもまた、他の新たな積符号の列に対し、追加のシンドロームビットを送出することを回避することができる。それは、それらのビットを先に送出されたシンドロームビットから確定することができるためである。
【０１５３】
この手続きを反復することができる。追加のシンドロームビットを送出する必要がある場合、ＳＰＣ符号の各積を、ＳＰＣ符号の２つの積に分割することができる。追加のシンドロームビットは、直接送出し、他の符号のシンドロームビットは、先に送信されたシンドロームビットから確定することができるため、送出しない。このように、必要なシンドロームビットのすべてを、先に送出されたシンドロームビットに含まれる情報を無駄にすることなく増分的に送出することができる。
【０１５４】
ＥＨＡ符号のレートの増分的な変更
ＥＨＡ符号を使用する場合、各ビットプレーンに対して使用するシンドロームビットの数を、以下のように増分的に増大させることができる。例として、ＥＨＡ符号の基本符号のうちの１つが［Ｎ＝１６，ｋ＝１１，ｄ＝４］拡張ハミング符号であるとする。拡張ハミング符号のパリティ検査行列は、非常に規則的な構造を有する。たとえば、［Ｎ＝１６，ｋ＝１１，ｄ＝４］拡張ハミング符号のパリティ検査行列は、下式（１１）である。
【０１５５】
【数１０】
2008511239.tif 000012
【０１５６】
この基本符号は、行列の各行に対して５つのシンドロームビットを１つ生成する。３つの追加のシンドロームビットを生成する必要があると想定する。これを行うためには、［Ｎ＝１６，ｋ＝１１，ｄ＝４］拡張ハミング符号を、下式（１２）のパリティ検査行列を有する２つの［Ｎ＝８，ｋ＝４，ｄ＝４］拡張ハミング符号に分割する。
【０１５７】
【数１１】
2008511239.tif 000013
【０１５８】
第１の小さい拡張ハミング符号のパリティ検査行列の８つの列は、より大きい拡張ハミング符号のパリティ検査行列の最初の８つの列に対応し、第２の小さい拡張ハミング符号のパリティ検査行列の８つの列は、より大きい拡張ハミング符号のパリティ検査行列の最後の８つの列に対応する。
【０１５９】
２つの小さい拡張ハミング符号に対し８つのシンドロームビットを生成するためには、第１の小さい拡張ハミング符号の第２行、第３行および第４行に対応する３つの追加のシンドロームビットを生成すればよい。他の行に対応するシンドロームビットを、以下のように確定することができる。第１の小さい拡張ハミング符号の第１行のシンドロームビットは、大きい行列の第２行のシンドロームビットに等しい。第２の小さい拡張ハミング符号の第１行のシンドロームビットは、大きい行列の第１行のシンドロームビットと第１の小さいパリティ検査行列の第１行のシンドロームビットとのモジュロ２和に等しい。第２の小さい行列の第２行のシンドロームビットは、第１の小さいパリティ検査行列の第２行のシンドロームビットと大きいパリティ検査行列の第３行のシンドロームビットとのモジュロ２和に等しい。他の必要なシンドロームビットも同様に確定することができる。
【０１６０】
任意のサイズの拡張ハミング符号に対し、Ｎ＝１６の拡張ハミング符号を分割する手続きを使用することができる。かかる符号のすべてを、２つのより小さい拡張ハミング符号に分割することができ、新たな拡張ハミング符号のシンドロームビットを、常に、追加のシンドロームビットを送出し、且つ、すでに送出されたビットから他のビットを確定することにより送信することができる。このように、先に送信されたシンドロームビットの情報を無駄にするのを回避することができる。拡張ハミング符号を分割する時、本発明では、ＥＨＡ符号の拡張ハミング符号のすべてのサイズがおよそ等しいように符号を分割することが好ましい。
【０１６１】
分割スケジュール
ＳＣＡ符号の基本符号を、復号器において既知である所定スケジュールに従って分割することが重要である。たとえば、ＥＨＡ符号を使用する場合、好ましいスケジュールは、常に、最大ブロック長を有する２つの第１の利用可能な拡張ハミング符号に分割するというものである。
【０１６２】
シンドローム復号器の全体構造
図１８は、本発明による復号器１８００を示す。復号器は、本質的には、元の信号を復元するように、受け取ったシンドロームビットの復元を実行する。復号器は、従来の復号器１８１０と、１つまたは複数のシンドローム復号器１８２０とを含む。第１の信号１８０１は、従来の方法で符号化されており、残りの信号１８０２〜１８０３は、すべてシンドロームビットとして符号化されている。その場合、復号器は、信号を復元し、その復元した信号を、第２のビットストリームに対する補助情報１８１１として使用する。第２の信号１８０２を復号すると、復元された信号を、第３の情報源に対する補助情報１８１２として使用し、以下同様に行う。
【０１６３】
相関する情報源に対する確率分布の形式
シンドローム復号器への重要な入力は、相関信号間の確率分布の推定値である。本発明では、先に、同時確率分布全体が下式のように同時マルコフ構造を有するものと想定した。
【０１６４】
【数１２】
2008511239.tif 000014
【０１６５】
補助情報Ｙを使用して復号される各信号Ｘに対し、条件付き確率分布ｐ（ｘ｜ｙ）の推定値を有することが重要である。
【０１６６】
条件付き確率分布は、通常、信号の各整数にわたり独立して分散されるガウス関数またはラプラシアン分布の形式を有する。すなわち、信号Ｘの各整数は、信号Ｙにおける対応する整数と同様であり、信号が量△だけ異なる確率は、△における何らかのガウス分布またはラプラシアン分布で低減する。
【０１６７】
当然ながら、条件付き確率分布の正確な形式は、特定の適用によって決まる。適用によっては、確率分布を、１組の利用可能な相関信号を「トレーニング」セットとして使用することにより推定することができる。
【０１６８】
多段シンドローム復号器
各信号に対するシンドロームビットを別々に復号する。各信号に対し、１組のビットプレーンを復号する。
【０１６９】
図１９は、本発明によるシンドローム復号器１９００を示す。復号器１９００は、各ビットプレーン１９０１に対しシンドローム変更直列連接累積復号器１９１０を含む。また、復号器１９００は、ビット確率推定値１９２１を生成するビット証拠推定器１９２０も含む。
【０１７０】
ビットプレーン１９０１を復号する順序を選択する。１つの妥当な選択は、最初に最上位ビットを復号し、結果としての剰余類符号語１９０２を使用して第２の最上位ビットを復号するのを助け、最下位ビットを復号するまで以下同様に行うというものである。別の妥当な選択は、最下位ビットから最上位ビットまで反対の順序で復号するというものである。結果としての剰余類符号語１９０２もまた、推定器１９２０に提供する。
【０１７１】
第１のビットプレーンを復号するためには、まず、各ビットに対し、推定された確率分布を使用して０または１であるその事前確率を確定する。これらの確率を、受け取ったシンドロームビットが満足されるように復号するように変更された、直列連接累積符号の復号器に対する軟入力として使用する。
【０１７２】
第２のビットプレーンを復号するために、先に復号された第１のビットプレーンを条件として、推定された確率分布を使用して各ビットに対し、その事前確率を計算する。さらなるビットプレーンを復号するためには、まず、先に復号されたビットプレーンのすべてを条件として、推定された確率分布を使用して事前確率を計算する。最終的に、ビットプレーンのすべてを復号し、復号は、完了する。
【０１７３】
最後に、復元されたビットプレーンを逆変換１９３０に送出し、逆変換１９３０は、符号器において適用された任意の変換（たとえばＤＣＴ変換）の影響を取り消し、復元された信号１９０３が得られる。
【０１７４】
ビット証拠推定器
ビット証拠推定器１９２０への入力は、先に復号された情報源の復号されたビットプレーン１９０４と、信号Ｘとその補助情報Ｙとの間の条件付き確率分布１９０５と、先に復号されたＸのビットプレーンの結果１９０２とである。出力１９２１は、復号される次のビットプレーンに対し、各ビットが０または１である確率に対する推定値である。ビット証拠推定器１９２０は、先に復号されたビットが与えられると依然として可能なすべての整数値にわたり確率分布を合計する。
【０１７５】
たとえば、復号される次のビットプレーンが第ｂビットプレーンであり、ビット証拠推定器が、ここで、そのビットプレーンの第ｉビット（ｘｂｉと呼ぶ）に対し作用しているものとする。ｘｂｉが１である確率を確定するために、ビット証拠推定器は、先に復号されたビットプレーンと一貫するすべての整数にわたり入力確率分布を合計し、先に復号されたビットプレーンと一貫するすべての整数にわたる入力確率分布の合計によって除算すると、ｘｂｉが１であるようにする。
【０１７６】
シンドローム変更直列連接累積復号器
図２０は、本発明によるシンドローム変更ＳＣＡ復号器２０００を示す。シンドローム変更ＳＣＡ復号器は、入力として、ビット証拠推定器１９２０によって生成されたビットプレーンの各ビットに対する確率推定値１９２１と、受け取ったシンドロームビット１９０１とを使用する。
【０１７７】
シンドローム変更ＳＣＡ復号器は、まず、受け取ったシンドロームビットの数と、既知の基本符号分割スケジュール２０１０とを使用して、使用する基本符号２０２０を確定する。
【０１７８】
シンドローム変更ＳＣＡ復号器は、ＳＣＡ符号に対して使用される方法のうちの任意のものを使用することができる。行う必要のある変更は、基本符号を処理する復号器の一部に対する変更のみである。復号器のその部分は、通信路復号器として使用される場合、１組の入力確率推定値が与えられると、「シフト」ビットに対する１組の確率推定値を生成する。シンドローム変更ＳＣＡ復号器は、依然としてそれを行うが、ここではまた、受け取ったシンドロームもまた満足されるように制約を満足するように変更される。
【０１７９】
たとえば、シンドロームビットがパリティ検査に連結され、パリティ検査もまた複数の他のシフトビットに連結される場合、且つ、シンドロームビットが０に等しい場合、基本符号に対する復号器は、それら他のシフトビットに対し１組の事後確率を出力する。シンドロームビットが１である場合に対応する事後確率の組を取得するためには、０に等しいシフトビットに対する出力された事後確率を、１に等しいシフトビットに対する出力された事後確率にリセットし、またその逆もある。
【０１８０】
図２０に示す好ましい実施の形態では、シンドローム変更ＳＣＡ復号器２０００は、反復復号方法を使用し、それは、累積符号２０３０および基本符号２０２０を交互に復号する。好ましい実施の形態では、累積符号を、ＢＣＪＲ方法を使用し、ビット確率推定値１９２１および基本符号の復号器からのシフトビットに対するビット確率推定値２００１を使用して復号する。基本符号を、累積符号からのシフトビットに対するビット確率推定値２００２と、受け取ったシンドロームビット１９０１とを使用して復号する。
【０１８１】
好ましい実施の形態では、シンドローム変更ＳＣＡ復号器は、一定の数の反復に対して、累積符号を復号すること、および基本符号を復号することを交互に行い、その後、累積符号の復号器は、ビットプレーンのビットに対し最終ビット推定値２００３を生成する。これらの推定値は、閾値処理され２０４０、すなわち、ビットプレーンのビットに対する最終推定値２００４を取得するように硬判定に変換される。
【０１８２】
そして、ビットプレーンのビットに対する最終推定値を検査する（２０５０）ことにより、最終推定値が剰余類符号語であるか否か、すなわち累積制約およびシンドロームビットが満足されるか否かを判断する。そうである場合、復号は、成功しており、剰余類符号語２００５を復元された信号として出力する。そうでない場合、フィードバック通信路が存在しない限り復号器は、失敗し、存在する場合は、さらなるシンドロームビットに対する要求２００６を生成する。
【０１８３】
元の信号の復元
図２１は、本発明による逆変換２１００を示す。剰余類符号語２００５から元の信号２１０３を復元する。剰余類符号語２００５を、まず、符号器１２００で使用されたものと同じ整数符号１２３０に従って整数２１０２の系列に変換する。符号器において変換により整数が取得された場合、復号器における整数を対応する逆変換２１２０に送出し、最終的な復元された信号２１０３を取得する。
【０１８４】
発明の効果
シミュレーションにより、本発明が実際的なシンドロームベースの符号化に対する望ましい要件を有することが示される。本システムをシミュレートするために、合成相関信号を生成した。それら信号は、０から２５５までの範囲のおよそ１０００個の整数を含み、信号の各整数は、ガウス分布またはラプラシアン分布により隣接する信号の対応する整数と相関する。
【０１８５】
本発明によるシステムは、システムの計算されたエントロピーよりほんのわずかに大きい（分布の細部に応じて、２％〜５％の間のオーバヘッド）複数のシンドロームビットを使用してかかる信号を圧縮することができた。それは、先に概説した他の要件のすべてを達成しながら、この結果を達成することができた。
【０１８６】
ビデオ圧縮システムへの適用
説明した本発明は、特に、携帯電話または単純なデジタルカメラで見ることができるような複雑性の低い符号器において、ビデオを符号化するために適している。関連特許出願は、この適用について詳細に説明している。本発明により、高圧縮レートが可能となり、増分的にレート適応型であり、低符号化複雑性および低復号複雑性に対して優れた性能を有するため、これらの利点は、ビデオ圧縮システムでも同様に得られる。
【０１８７】
本発明を、好ましい実施の形態の例を用いて説明したが、本発明の精神および範囲内でさまざまな他の適応および変更を行ってもよいということが理解されなければならない。したがって、本発明の真の精神および範囲内にあるかかる変形および変更のすべてを包含することが添付の特許請求の範囲の目的である。
【図面の簡単な説明】
【０１８８】
【図１】従来技術によるSlepian-Wolf圧縮システムのブロック図である。
【図２】従来技術による圧縮システムのブロック図である。
【図３】相関信号に対して動作する従来技術による圧縮システムのブロック図である。
【図４】従来技術による、復元確率を確定するために送出される最小数のビットのグラフである。
【図５】通信路符号化問題に対する従来技術による方法のブロック図である。
【図６】従来技術によるハミング符号のファクターグラフである。
【図７】シンドロームビットに対応する変数ノードを含む、従来技術によるハミング符号の拡張ファクターグラフである。
【図８】繰返し累積（ＲＡ）符号の従来技術による符号器のブロック図である。
【図９】従来技術によるＲＡ符号例のファクターグラフである。
【図１０】従来技術による単一パリティ検査符号の積のファクターグラフである。
【図１１】従来技術による直列連接累積（ＳＣＡ）符号のファクターグラフである。
【図１２】本発明による符号器のブロック図である。
【図１３】本発明によるシンドロームビットを含む積累積（ＰＡ）符号の拡張ファクターグラフである。
【図１４】本発明によるＰＡ符号を使用するシンドロームビット符号器のブロック図である。
【図１５】本発明によるシンドロームビットを含む拡張ハミング累積（ＥＨＡ）符号の拡張ファクターグラフである。
【図１６】本発明による単一パリティ検査符号の８×８積の拡張ファクターグラフのブロック図である。
【図１７】本発明による単一パリティ検査符号の２つの８×４積の拡張ファクターグラフのブロック図である。
【図１８】本発明による復号器のブロック図である。
【図１９】本発明による多段シンドローム復号器のブロック図である。
【図２０】本発明によるシンドローム変更ＳＣＡ復号器のブロック図である。
【図２１】本発明による逆変換のブロック図である。
【図１】
2008511239.tif 000015
【図２】
2008511239.tif 000016
【図３】
2008511239.tif 000017
【図４】
2008511239.tif 000018
【図５】
2008511239.tif 000019
【図６】
2008511239.tif 000020
【図７】
2008511239.tif 000021
【図８】
2008511239.tif 000022
【図９】
2008511239.tif 000023
【図１０】
2008511239.tif 000024
【図１１】
2008511239.tif 000025
【図１２】
2008511239.tif 000026
【図１３】
2008511239.tif 000027
【図１４】
2008511239.tif 000028
【図１５】
2008511239.tif 000029
【図１６】
2008511239.tif 000030
【図１７】
2008511239.tif 000031
【図１８】
2008511239.tif 000032
【図１９】
2008511239.tif 000033
【図２０】
2008511239.tif 000034
【図２１】
2008511239.tif 000035
【国際調査報告】
2008511239.tif 000036
2008511239.tif 000037
2008511239.tif 000038