[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP4487212B2 - 復号装置および方法、送受信システム、受信装置および方法、並びにプログラム - Google Patents

復号装置および方法、送受信システム、受信装置および方法、並びにプログラム Download PDF

Info

Publication number
JP4487212B2
JP4487212B2 JP2007272517A JP2007272517A JP4487212B2 JP 4487212 B2 JP4487212 B2 JP 4487212B2 JP 2007272517 A JP2007272517 A JP 2007272517A JP 2007272517 A JP2007272517 A JP 2007272517A JP 4487212 B2 JP4487212 B2 JP 4487212B2
Authority
JP
Japan
Prior art keywords
matrix
unit
quasi
unit matrix
shift
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP2007272517A
Other languages
English (en)
Other versions
JP2009100421A (ja
Inventor
峰志 横川
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sony Corp
Original Assignee
Sony Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sony Corp filed Critical Sony Corp
Priority to JP2007272517A priority Critical patent/JP4487212B2/ja
Priority to EP08253289A priority patent/EP2088679A3/en
Priority to TW097139222A priority patent/TWI373922B/zh
Priority to KR1020080101347A priority patent/KR20090040223A/ko
Priority to US12/253,324 priority patent/US8234555B2/en
Priority to CN2008101702881A priority patent/CN101442317B/zh
Publication of JP2009100421A publication Critical patent/JP2009100421A/ja
Application granted granted Critical
Publication of JP4487212B2 publication Critical patent/JP4487212B2/ja
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6508—Flexibility, adaptability, parametrability and configurability of the implementation
    • H03M13/6513—Support of multiple code types, e.g. unified decoder for LDPC and turbo codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1111—Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1131—Scheduling of bit node or check node processing
    • H03M13/1137—Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
    • H03M13/1165—QC-LDPC codes as defined for the digital video broadcasting [DVB] specifications, e.g. DVB-Satellite [DVB-S2]
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
    • H03M13/1168—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices wherein the sub-matrices have column and row weights greater than one, e.g. multi-diagonal sub-matrices
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/118—Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure
    • H03M13/1185—Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure wherein the parity-check matrix comprises a part with a double-diagonal
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6508—Flexibility, adaptability, parametrability and configurability of the implementation
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6508—Flexibility, adaptability, parametrability and configurability of the implementation
    • H03M13/6516—Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Multimedia (AREA)
  • Error Detection And Correction (AREA)

Description

本発明は、復号装置および方法、送受信システム、受信装置および方法、並びにプログラムに関し、特に、構造の異なる複数のLDPC符号の復号ができ、かつ、回路規模縮小も図ることができる復号装置および方法、送受信システム、受信装置および方法、並びにプログラムに関する。
通信システムにおいては、コーディングを使用して雑音のある通信チャネルに渡る信頼性ある通信が行われている。例えば、衛星ネットワークのようなワイヤレス（または無線）システムでは、地理的および環境的要因からの雑音源が多い。これらの通信チャネルは固定容量を表し、ある信号対雑音比（ＳＮＲ）におけるシンボル当たりのビットに関して表すことができ、シャノン限界として知られる理論的上限を規定している。結果として、コーディング設計はこのシャノン限界に近づくレートを達成することを目的としている。この目的は、帯域幅制約衛星システムに対して特に密接な関係がある。
近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と称される手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、LDPC符号と称する）が脚光を浴びつつある。
LDPC符号は、R. G. Gallagerによる非特許文献１において最初に提案されたものであり、その後、非特許文献２，３等において再注目されるに至ったものである。
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくに従って、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことが利点として挙げられる。
以下、このようなLDPC符号について具体的に説明する。なお、LDPC符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
LDPC符号は、そのLDPC符号を定義する検査行列(parity check matrix)が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの"1"の個数が非常に少なく構成されるものであり、疎な検査行列をHで表すものとすると、そのような検査行列Hとしては、例えば、図１に示すように、各列のハミング重み（"1"の数）(weight)が"3"であり、且つ、各行のハミング重みが"6"であるもの等がある。
このように、各行及び各列のハミング重みが一定である検査行列Hによって定義されるLDPC符号は、レギュラーLDPC符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Hによって定義されるLDPC符号は、イレギュラーLDPC符号と称される。
このようなLDPC符号による符号化は、検査行列Hに基づいて生成行列Gを生成し、この生成行列Gを２元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号による符号化を行う符号化装置は、まず、検査行列Hの転置行列HTとの間に、式GHT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、k×n行列である場合には、符号化装置は、生成行列Gに対してkビットからなる情報メッセージ（ベクトルu）を乗算し、nビットからなる符号語ｃ（＝uＧ）を生成する。この符号化装置によって生成された符号語は、値が"0"の符号ビットが"+1"に、値が"1"の符号ビットが"−1"にといったようにマッピングされて送信され、所定の通信路を介して受信側において受信されることになる。
なお、例えば、nビットの符号語cが、kビットの情報メッセージuに続けて、n-kビットのパリティビットを配置したビット列に一致する組織符号である場合に、n-k行n列の検査行列Hにおいて、nビットの符号語cのうちのkビットの情報メッセージuに対応するn-k行k列の部分を情報部というとともに、n-kビットのパリティビットに対応するn-k行n-k列の部分をパリティ部ということとすると、パリティ部が、下三角行列または上三角行列になっていれば、情報メッセージuのLDPC符号への符号化は、検査行列Hを用いて行うことができる。
即ち、例えば、検査行列Hが、図２に示すように、情報部と、下三角行列のパリティ部とで構成され、パリティ部の下三角の部分の要素が、すべて1であるとすると、符号語cのパリティビットの１番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第１行において1になっている要素に対応するビットのEXOR（排他的論理和）を演算した値となる。
また、符号語cのパリティビットの２番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第２行において1になっている要素に対応するビットと、パリティビットの１番目のビットのEXORを演算した値となる。
さらに、符号語cのパリティビットの３番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第３行において1になっている要素に対応するビットと、パリティビットの１番目および２番目のビットのEXORを演算した値となる。
以下、同様にして、符号語cのパリティビットのi番目のビットは、情報メッセージuのうちの、検査行列Hの情報部の第i行において1になっている要素に対応するビットと、パリティビットの１乃至i-1番目のビットのEXORを演算した値となる。
以上のようにして、n-kビットのパリティビットを求め、kビットの情報メッセージuに続けて配置することにより、nビットの符号語cを得ることができる。
一方、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案したアルゴリズムであって、バリアブルノード(バリアブルノード（メッセージノード(message node)とも呼ばれる。）)と、チェックノード(チェックノード)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのもを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Gallagerは、LDPC符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
LDPC符号の復号は、例えば、図３に示すような手順に従って行われる。なお、ここでは、符号長の長さのLDPC符号の受信データのi番目をU0(u0i)とし、チェックノードから出力されるj番目のメッセージ（チェックノードに接続しているj番目の枝から出力されるメッセージ）をujとし、バリアブルノードから出力されるi番目のメッセージ（バリアブルノードに接続しているi番目の枝から出力されるメッセージ）をviとする。また、ここでは、メッセージとは、値の"0"らしさを表す、いわゆる対数尤度比(log likelihood ratio)等を表現する実数値である。
まず、LDPC符号の復号においては、図３に示すように、ステップＳ１１において、受信データU0(u0i)が受信され、メッセージujが"0"に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数kが"0"に初期化され、処理は、ステップＳ１２に進む。ステップＳ１２において、受信データU0(u0i)を用いて、式（１）に示すバリアブルノードの演算を行うことによってメッセージviが求められ、さらに、このメッセージviを用いて、式（２）に示すチェックノードの演算を行うことによってメッセージujが求められる。
Figure 0004487212
 ・・・（１）
Figure 0004487212
 ・・・（２）
ここで、式（１）と式（２）におけるdvとdcは、それぞれ、検査行列Hの縦方向（列）と横方向（行）の"1"の個数、つまり、列の重み（ハミング重み）と行の重みを示す任意に選択可能とされるパラメータであり、例えば、(3,6)符号の場合には、dv=3，dc=6となる。
なお、式（１）又は（２）の演算においては、それぞれ、メッセージを出力しようとする枝(edge)から入力されたメッセージを、和又は積演算の対象としては用いないことから、和又は積演算の範囲が、１ないしdv-1又は１ないしdc-1となっている。また、式（２）に示す演算は、２入力v1，v2に対して１が得られる式（３）に示す関数R(v1,v2)のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行うことができる。
Figure 0004487212
 ・・・（３）
Figure 0004487212
 ・・・（４）
ステップＳ１２では、さらに、変数kが"1"だけインクリメントされ、処理は、ステップＳ１３に進む。ステップＳ１３では、変数kが所定の繰り返し復号回数N以上であるか否かが判定される。ステップＳ１３において、変数kがN以上ではないと判定された場合、処理は、ステップＳ１２に戻り、以下、同様の処理が繰り返される。
また、ステップＳ１３において、変数kがN以上であると判定された場合、処理は、ステップＳ１４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージvが求められて出力され、LDPC符号の復号処理が終了する。
Figure 0004487212
 ・・・（５）
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からのメッセージujを用いて行われる。
このようなLDPC符号の復号では、例えば(3,6)符号の場合には、図４に示すように、各ノード間でメッセージの授受が行われる。なお、図４において"="（イコール）で示すノードは、バリアブルノードを表し、式（１）に示したバリアブルノードの演算が行われる。また、図４において"+"（プラス）で示すノードは、チェックノードを表し、式（２）に示したチェックノードの演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、"+"で示すチェックノードにて、dc-1個の入力メッセージ（チェックノードに入力されるメッセージvi）の排他的論理和演算を行い、"="で示すバリアブルノードにて、受信データRに対して、dv-1個の入力メッセージ（バリアブルノードに入力されるメッセージuj）が全て異なるビット値であった場合には、符号を反転して出力する。
また、近年、LDPC符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、LDPC符号の復号を摸式化して説明する。
図５は、(3,6)符号のLDPC符号（符号化率1/2、符号長12）の検査行列(parity check matrix)Hの例である。LDPC符号の検査行列Hは、図６のように、タナーグラフを用いて書き表すことができる。ここで、図６において、"+"で表されるのが、チェックノードであり、"="で表されるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列の行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝(edge)であり、検査行列Hの"1"に相当する。すなわち、検査行列の第ｊ行第ｉ列のコンポーネントが１である場合には、図６において、上からｉ番目のバリアブルノード（"="のノード）と、上からｊ番目のチェックノード（"+"のノード）とが、枝により接続される。枝は、バリアブルノードに対応するLDPC符号（の受信データ）のビットが、チェックノードに対応する拘束条件を持つことを表す。なお、図６は、図５の検査行列Hのタナーグラフとなっている。
LDPC符号の復号方法であるサムプロダクトアルゴリズム(Sum Product Algorithm)は、バリアブルノードの演算とチェックノードの演算とを繰り返し行う。
バリアブルノードでは、図７のように、式（１）のバリアブルノードの演算を行う。すなわち、図７において、バリアブルノードに接続している枝のうちのi番目の枝に対応するメッセージviは、バリアブルノードに接続している残りの枝からのメッセージu1及びu2と、受信データu0iとを用いて計算される。他の枝に対応するメッセージも同様に計算される。
チェックノードの演算について説明する前に、式（２）を、式a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b)の関係を用いて、式（６）のように書き直す。但し、sign(x)は、x≧0のとき1（論理０）であり、x＜0のとき-1（論理１）である。
Figure 0004487212
 ・・・（６）
さらに、x≧0において、非線形関数φ(x)=-ln(tanh(x/2))を定義すると、その逆関数φ-1(x)は、式φ-1(x)=2tanh-1(e-x)で表されるから、式（６）は、式（７）のように書くことができる。
Figure 0004487212
 ・・・（７）
チェックノードでは、図８のように、式（７）のチェックノードの演算を行う。すなわち、図８において、チェックノードに接続している枝のうちのj番目の枝に対応するメッセージujは、チェックノードに繋がっている残りの枝からのメッセージv1,v2,v3,v4,v5を用いて計算される。他の枝に対応するメッセージも同様に計算される。
なお、関数φ(x)は、φ(x)=ln((ex+1)/(ex-1))とも表すことができ、x＞0において、φ(x)=φ-1(x)、すなわち、非線形関数φ(x)の演算結果と、その逆関数φ-1(x)の演算結果とは同一である。関数φ(x)及びφ-1(x)をハードウェアに実装する際には、LUT(Look Up Table)を用いて実装される場合があるが、両者は同一のLUTとなる。
また、式（１）のバリアブルノードの演算は、式（５）と、次の式（８）とに分けることができる。
Figure 0004487212
 ・・・（８）
したがって、式（５）及び式（８）と、式（７）の演算を繰り返し行うことにより、式（１）のバリアブルノードの演算と、式（７）のチェックノードの演算を繰り返し行うことができる。この場合、式（５）及び式（８）のバリアブルノードの演算のうちの、式（５）の演算の結果を、そのまま、最終的な復号結果とすることができる。
サムプロダクトアルゴリズムをハードウェアに実装して、復号装置とする場合、式（１）（、又は式（５）及び式（８））で表されるバリアブルノード演算（バリアブルノードの演算）及び式（７）で表されるチェックノード演算（チェックノードの演算）を、適度な回路規模と動作周波数で繰り返し行うことが必要である。
以下、このような復号装置の実装の例について説明する。
LDPC符号の復号アルゴリズムは、その特徴として極めて高い並列処理復号装置の実装を可能とする。しかしながら、符号長が大きい符号の完全並列復号装置は回路規模が非常に大きくなり、実現が困難である。
そこで、近年、現実的な回路規模での復号装置の実装に適した構造を持つLDPC符号が提案され、DVB-S.2（ETSI EN302307）等の伝送方式に採用されている。よって、以下、かかるLDPC符号を、DVB-S.2のLDPC符号と称する。
DVB-S.2のLDPC符号は、検査行列に対して行／列置換を施すことにより、次のような構造を持つ行列により表すことができるようになっている。
即ち、P=360としたとき、P×Pの単位行列、その単位行列のコンポーネントである１のうち１個以上が０になった行列（以下、適宜、準単位行列という）、単位行列または準単位行列をサイクリックシフト(cyclic shift)した行列（以下、適宜、シフト行列という）、単位行列、準単位行列、またはシフト行列のうちの２以上(複数)の和（以下、適宜、和行列という）、P×Pの０行列を構成行列として、複数の構成行列の組合わせにより構成される検査行列によって、DVB-S.2のLDPC符号は表すことができるようになっている。なお、以下、かかる構造の検査行列を、P×Pの構造の検査行列と称する。そして、以下、P×Pの構造の検査行列で表されるLDPC符号を、「Pの符号」と称する。
このような「Pの符号」を用いることで、P個の受信値（Pビット）およびP個のメッセージ（Pビット）を同時に処理する復号装置が実装可能となっている。
ただし、以下では説明を容易なものとすべく、P=6として説明を行っていく。図９は、符号化率2/3、符号長108のLDPC符号を表す検査行列であって、6×6の構造の検査行列の一例を示している。なお、図９の例では、6×6の構造を明確なものとすべく、6×6の各構成行列の間には間隔が空けられている。また、図９の例では、見易さのため、「０」の代わりに「．」と記述されている。即ち、図９の例の検査行列は、6×6の単位行列、その単位行列の１のうち１個が０になった準単位行列、それらのシフト行列、それらの和行列、6×6の０行列といった構成行列の組合わせにより構成されている。
図１０は、このような「P=6のLDPC符号」を復号する復号装置の一例を示している。
図１０の例の復号装置は、受信値バッファ２００、受信値格納メモリ２０１、ノード演算部２０２、シフト部２０３、メッセージ格納メモリ２０４、および復号結果格納メモリ２０５を含むように構成されている。
受信値バッファ２００は、通信路を通して受信したデータD200を１符号分蓄え、データD201として受信値格納メモリ２０１に転送する。なお、受信値バッファ２００に採用されている伝送方式によっては、受信値バッファ２００において符号ビットの並び替えが行われる場合もある。
受信値格納メモリ２０１は、受信値データD201を図９の検査行列の列の順に6個（1個は6ビット）ずつを同時に読み出し、即ち、6×6の構成行列を単位として読み出し、それらを6個の受信データD202として、ノード演算部２０２に供給する。
ノード演算部２０２は、６つのノード演算器２１０−１乃至２１０−６を有している。６つのノード演算器２１０−１乃至２１０−６は、受信値格納メモリ２０１から供給される６個の受信データD202のうちの所定の１個と、メッセージ格納メモリ２０４から供給される６個のメッセージD205のうちの所定の1個とを用いて、図示せぬ制御部の指示に基づいて、チェックノード演算またはバリアブルノード演算をそれぞれ並行に行い、計算したメッセージD203をシフト部２０３にそれぞれ供給する。即ち、ノード演算器２１０−１乃至２１０−６によってそれぞれ同時演算された６個のメッセージD203が出力されて、シフト部２０３に供給される。また、バリアブルノード演算時には、ノード演算器２１０−１乃至２１０−６によってそれぞれ演算された６個の復号結果D206が同時に出力されて、復号結果格納メモリ２０５に供給される。
シフト部２０３には、ノード演算部２０２から６個のメッセージD203が供給される場合、それに対応する枝が図９の検査行列において元となる単位行列などを幾つサイクリックシフトしたものであるかの情報が図示せぬ制御部から提供される。そこで、シフト部２０３は、この情報に基づいて、６個のメッセージD203を並べ替えるサイクリックシフトを行い、その結果をメッセージD204として、メッセージ格納メモリ２０４に供給する。
メッセージ格納メモリ２０４は、シフト部２０３から供給された６個のメッセージD204を、図示せぬ制御部から指定されるアドレスに格納する。また、メッセージ格納メモリ２０４は、図示せぬ制御部から指定されるアドレスから読みだした6個のデータを６個のメッセージD205としてノード演算部２０２に供給する。
復号結果格納メモリ２０５は、ノード演算部２０２のノード演算器２１０−１乃至２１０−６から同時にそれぞれ供給される6ビット分の復号結果D206、即ち6個の復号結果D206を格納し、復号が完了した後に、復号結果D207として出力する。
なお、この図１０の復号装置は、各種メモリへの読み書きの順番やシフト量を適切に制御することで、単一の符号のみならず、同じ構造を持つ別の符号の復号を行なうこともできる。
図１１は、ノード演算部２０２の６つのノード演算器２１０−１乃至２１０−６のそれぞれの構成例を示している。なお、以下、６つのノード演算器２１０−１乃至２１０−６を個々に区別する必要がない場合、単に、ノード演算器２１０と称する。
図１１の例のノード演算器２１０は、式(１)に従ったバリアブルノード演算と、式(７)に従ったチェックノード演算とを相互に切り替えて行うことができる。
ノード演算器２１０は、外部からメッセージ（データ）が供給（入力）される入力ポートとして、２つの入力ポートP301,P302を有している。すなわち、入力ポートP301には、図１０の受信値格納メモリ２０１から読み出された受信データD202が供給される。入力ポートP302には、図１０のメッセージ格納メモリ２０４から読み出されたメッセージD205が供給される。
また、ノード演算器２１０は、図１０のシフト部２０３に対してメッセージD203を供給（出力）する出力ポートP303と、図１０の復号結果格納メモリ２０５に対して復号結果D206を供給（出力）する出力ポートP304を有している。
ノード演算器２１０は、セレクタ３０１,３１６,３１８を有している。これらのセレクタ３０１,３１６,３１８が“v”の側を選択した場合には、ノード演算器２１０はバリアブルノード演算を行うことになる。これに対して、セレクタ３０１,３１６,３１８が“c”の側を選択した場合には、ノード演算器２１０はチェックノード演算を行うことになる。
まず、バリアブルノード演算を行う場合の動作の観点から、ノード演算器２１０の説明をする。
メッセージ格納メモリ２０４から供給される１列分のチェックノードからのメッセージD205が入力ポートP302を介して、メッセージD301（メッセージuj）として一つずつ入力され、セレクタ３０１を通過してメッセージD306として加算器３０２に入力される。加算器３０２には、セレクタ３１７の出力データD323も入力される。即ち、メッセージD306に対して、セレクタ３１７の出力データD323が加算されて、その加算値がレジスタ３０３に格納される。
ここで、セレクタ３１７の入力がレジスタ３０３の出力データD307側に切り替えられている場合、加算器３０２において、メッセージD306に対して、レジスタ３０３に格納してあるデータD307が加算されて、その加算値がレジスタ３０３に再格納される。
一方、セレクタ３１７の入力がセレクタ３１８の出力データD322側に切り替えられている場合、加算器３０２において、メッセージD306に対して、セレクタ３１８の出力データD322が加算される。即ち、セレクタ３１８の出力データD322とは、入力ポートP301に受信データD300として受信された受信データD202(u0i)である。よって、加算器３０２において、メッセージD306に対して、受信データD202(u0i)が加算されて、その加算値がレジスタ３０３に格納される。
このような動作が１列分繰り返されると、レジスタ３０３には、ｊ＝１からdvまでのΣuj＋u0iに相当するデータが蓄積される。かかるデータD307（ｊ＝１からdvまでのΣuj＋u0i）は、セレクタ３０４を介してレジスタ３０５に格納される。
一方、遅延用FIFO３１０は、レジスタ３０５から新たなデータD308（ｊ＝１からdvまでのΣuj＋u0i）が出力されるまでの間、セレクタ３０１が出力したチェックノードからのメッセージD306を遅延し、遅延入力メッセージD315として減算器３１２に供給する。
遅延入力メッセージD315は、減算器３１２においてレジスタ３０５の出力データD308から減算されて、その減算値D316（ｊ＝１からdv-1までのΣuj＋u0i)がセレクタ３１６を通過して、メッセージD321となる。このメッセージD312が、出力メッセージD203として出力ポートP303から出力されて図１０のシフト部２０３に供給される。
以上の内容を換言すると、ノード演算器２１０は、バリアブルノードに繋がっている全てのチェックノードからのメッセージと受信データの和から、求めたいチェックノードからのメッセージを引いて、求めたい枝 (edge)へのメッセージを計算することで、式(１)の演算を実現している。
次に、チェックノード演算を行う場合の動作の観点から、ノード演算器２１０の説明をする。
図１０のメッセージ格納メモリ２０４から供給される１行分のバリアブルノードからのメッセージD205が入力ポートP302を介して、メッセージD301（メッセージvi）として一つずつ入力され、その絶対値D303(|vi|)がLUT３００に供給される。
LUT３００は、そこに入力される値を引数xとして、式（７）のチェックノード演算における非線形関数φ(x)の演算結果を出力するLUTであり、絶対値D303(|vi|)の供給に対して、非線形関数φ(|vi|)の演算を行った演算結果D305（φ(|vi|)）を読み出す。
この演算結果D305（φ(|vi|)）は、セレクタ３０１を通過してメッセージD306として加算器３０２に入力される。加算器３０２において、このメッセージD306に対して、セレクタ３１７の出力データD323が加算されて、即ち、レジスタ３０３に格納してあるデータD307が加算されて、その加算値がレジスタ３０３に再格納される。このように、データD307は、演算結果D305（φ(|vi|)）の積算値となる。
1行分のメッセージD301（メッセージvi）の各演算結果D305（φ(|vi|)）が積算されると、その積算値D307（i＝１からdcまでのΣφ(|vi|))はセレクタ３０４を通過して、レジスタ３０５に格納される。
一方、遅延用FIFO３１０は、レジスタ３０５から新たなデータD308（i＝１からdcまでのΣφ(|vi|))が出力されるまでの間、セレクタ３０１の出力データD306、即ち、LUT３００の演算結果D305を遅延し、遅延データD315として減算器３１２に供給する。
減算器３１２において、レジスタ３０５に格納されている積算メッセージD308から、遅延データD315が減算され、その減算値D316（i＝１からdc-1までのΣφ(|vi|))はLUT３１４に供給される。
LUT３１４は、そこに入力される値を引数xとして、式（７）のチェックノード演算における非線形関数φ(x)の逆関数φ-1(x)の演算結果を出力するLUTであり、減算器３１２からの減算値D316（ｉ＝１からdc-1までのΣφ(|vi|)）の供給に対して、逆関数φ-1（Σφ(|vi|)）の演算を行った演算結果D318（φ-1(Σφ(|vi|)))を出力する。
以上の処理と並行して、各メッセージD301の正負を表す符号ビット(sign bit)D304 (sign(vi))と、レジスタ３０７に格納されている値D310との排他的論理和がEXOR回路３０６において演算されることで、その演算結果D309がレジスタ３０７に再格納される。
レジスタ３０７において、1行分の符号ビットが積算されたところで、その積算値D310(ｉ＝１からdcまでのΠsign(vi)）がセレクタ３０８を通過して、レジスタ３０９に格納される。
一方、遅延用FIFO３１０は、レジスタ３０９から新たなデータD311(ｉ＝１からdcまでのΠsign(vi))が出力されるまでの間、積算に用いられた符号ビットD304(sign(vi))を遅延し、遅延符号ビットD313 としてEXOR回路３１５に供給する。
この遅延符号ビットD313と、レジスタ３０９の積算値D311との排他的論理和がEXOR回路３１５において演算されることで、その演算結果、即ちｉ＝１からdc-1までのΠsign(vi)が符号ビットD319として出力される。
最終的に、LUT３１４の演算結果D318（φ-1(Σφ(|vi|)))に対して、この符号ビットD319が付加された値D320が、セレクタ３１６を通過してメッセージD321となる。このメッセージD312が、出力メッセージD203として出力ポートP303から出力されて図１０のシフト部２０３に供給される。
以上の内容を換言すると、ノード演算器２１０は、チェックノードに繋がっている全てのバリアブルノードからのメッセージの和から、求めたいバリアブルノードからのメッセージを引くことで、式(７)の演算を実現している。
また、ノード演算器２１０は、復号の最終段（例えば、あらかじめ定められた繰り返し復号の回数Nだけ行われるバリアブルノード演算及びチェックノード演算のうちの最後に行われるバリアブルノード演算）において、式（１）のバリアブルノード演算の代わりに、式（５）の演算が行われ、その演算結果、即ち、レジスタ３０５からの出力データD308が、復号結果D206として出力ポートP304から出力されて図１０の復号結果格納メモリ２０５に供給される。
なお、図１０の例の復号装置は、「P=6の符号」の復号装置であるが、Pが6以外の「Pの符号」の復号装置も基本的に図１０の例と基本的に同様の構成を取ることができる。
R. G. Gallager, "Low Density Parity Check Codes", Cambridge, Massachusetts: M. I. T. Press, 1963 D. J. C. MacKay, "Good error correcting codes based on very parse matrices", Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999 M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, "Analysis of low density codes and improved designs using irregular graphs", in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998
しかしながら、「Pの符号」の復号装置を、従来の技術で図１０の例と同様の構成で実現する場合、ノード演算器は６並列でなくP並列必要となる。また、シフト部も、６×６ではなくP×Pのサイクリックしフトを行う必要がある。さらにまた、各種メモリも、６個のデータではなくP個のデータを同時に読み書きできる必要がある。
よって、Pの値が大きい場合には、復号装置全体の回路規模が増大してしまうという問題が生ずる。
また、従来の復号装置では、「Pの符号」以外の例えば「Qの符号」の復号を行なうことができない。従って、ひとつの伝送システムに用いる符号はすべて、「Pの符号」であることが必要であった。そのため、例えば、伝送レートの高い固定受信機向けのサービス用に「Pの符号」、伝送レートは低いが消費電力制限の大きい携帯型受信機向けのサービス用には「Qの符号」を採用するような伝送システムでは、共用受信機を構成する場合に、「Pの符号」と「Qの符号」のそれぞれに対して専用の復号装置を別々に設ける必要がある、といった問題も生じてしまう。
本発明は、このような状況に鑑みてなされたものであり、構造の異なる複数のLDPC符号の復号ができ、回路規模縮小も図ることができる復号装置を提供することを目的とするものである。
本発明の一側面の復号装置は、LDPC(Low Density Parity Check)符号を復号する復号装置であって、前記LDPC符号が、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される第１の形態で受信される場合と、QがPとは異なる値であって１以外の値であるとき、Q×Qの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはQ×Qの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第２の構造の行列で表現される第２の形態で受信される場合とが存在し、FをPとQの１以外の公約数としたとき、前記第１の形態または前記第２の形態のLDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行う演算を少なくとも実行する。
前記F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行い、各演算の結果得られるF個のメッセージを出力するメッセージ計算手段と、前記メッセージ計算手段から出力されるF個の前記メッセージに対して、F×Fのサイクリックシフトを行って出力するシフト手段と、前記シフト手段から出力されるF個の前記メッセージの書き込み、書き込まれたF個の前記メッセージの読み出し、または、F個の前記受信値の読み出し若しくは書き込みができる記憶手段とを復号装置は備える。
F×Fの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはF×Fの０行列を第３の構成行列として、複数の前記第３の構成行列の組合せによる第３の構造の行列を定義した場合に、前記第１の構造または前記第２の構造の検査行列で表現される前記受信値に対して少なくとも列置換処理を施すことで、前記メッセージ計算手段への前記受信値の提供の制御として、前記第３の構成行列に対応するF個の前記受信値を単位とする提供の制御を行う制御手段をさらに備える。
本発明の一側面の復号方法およびプログラムは、本発明の一側面の上述した復号装置に対応する方法およびプログラムである。
本発明の一側面の復号装置および方法並びにプログラムにおいては、LDPC(Low Density Parity Check)符号を復号する復号装置において、次のような処理が実行される。即ち、前記LDPC符号が、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される第１の形態で前記復号装置に受信される場合と、QがPとは異なる値であって１以外の値であるとき、Q×Qの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはQ×Qの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第２の構造の行列で表現される第２の形態で前記復号装置に受信される場合とが存在し、FをPとQの１以外の公約数としたとき、前記第１の形態または前記第２の形態のLDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算が並列的に行われる。
本発明の一側面の送受信システムは、LDPC(Low Density Parity Check)符号を誤り訂正符号として用いる送受信システムであって、前記LDPC符号の形態として、１以外の任意の整数値をαとしたときに、α×αの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはα×αの０行列を構成行列として、複数の前記構成行列の組合せによる構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記構造の行列で表現される形態が取り得る場合、１以外の整数値Fの倍数となる相異なる複数の整数値のうちの、K個（Kは２以上の整数値）の整数値が選択され、選択された前記K個の整数値が前記αとしてそれぞれ代入されたときに取りうる前記K種類の前記形態のLDPC符号が、誤り訂正符号としてそれぞれ用いられる。
本発明の一側面の送受信システムでは、次のようなLDPC(Low Density Parity Check)符号が誤り訂正符号として用いられる。即ち、前記LDPC符号の形態として、１以外の任意の整数値をαとしたときに、α×αの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはα×αの０行列を構成行列として、複数の前記構成行列の組合せによる構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記構造の行列で表現される形態が取り得る場合、１以外の整数値Fの倍数となる相異なる複数の整数値のうちの、K個（Kは２以上の整数値）の整数値が選択され、選択された前記K個の整数値が前記αとしてそれぞれ代入されたときに取りうる前記K種類の前記形態のLDPC符号が、誤り訂正符号としてそれぞれ用いられる。
本発明の一側面の受信装置は、LDPC(Low Density Parity Check)符号を誤り訂正符号として用いる送受信システムの受信装置である。詳細には、本発明の一側面の受信装置は、前記LDPC符号の形態として、１以外の任意の整数値をαとしたときに、α×αの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはα×αの０行列を構成行列として、複数の前記構成行列の組合せによる構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記構造の行列で表現される形態が取り得る場合、１以外の整数値Fの倍数となる相異なる複数の整数値のうちの、K個（Kは２以上の整数値）の整数値が選択され、選択された前記K個の整数値が前記αとしてそれぞれ代入されたときに取りうる前記K種類の前記形態のLDPC符号が、誤り訂正符号としてそれぞれ用いられる送受信システムの受信装置であって、前記K種類のうちの何れかの種類の形態のLDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行う演算を少なくとも実行する復号手段を備える。
本発明の一側面の受信方法は、本発明の一側面の上述した受信装置に対応する方法である。
本発明の一側面の受信装置では、次のようなLDPC(Low Density Parity Check)符号が誤り訂正符号として用いられる。即ち、前記LDPC符号の形態として、１以外の任意の整数値をαとしたときに、α×αの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはα×αの０行列を構成行列として、複数の前記構成行列の組合せによる構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記構造の行列で表現される形態が取り得る場合、１以外の整数値Fの倍数となる相異なる複数の整数値のうちの、K個（Kは２以上の整数値）の整数値が選択され、選択された前記K個の整数値が前記αとしてそれぞれ代入されたときに取りうる前記K種類の前記形態のLDPC符号が、誤り訂正符号としてそれぞれ用いられる。そして、前記K種類のうちの何れかの種類の形態のLDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行う演算が少なくとも実行される。
本発明によれば、LDPC(Low Density Parity Check)符号を復号する復号装置、その復号装置を構成要素に含む受信装置、またはその受信装置を構成要素に含む送受信システムを提供できる。特に、構造の異なる複数のLDPC符号の復号ができ、復号装置や受信装置全体の回路規模縮小も図ることができる。
次に、本発明の手法について説明する。
本明細書でいう「Pの符号」とは、準巡回(QC（Quasi Cyclic)）符号の性質を持ったLDPC符号のひとつである。
ここでQC符号とは、任意の符号語を、ある自然数の周期だけ巡回シフトした系列が、元の符号語以外の符号語となる符号のことをいう。
QC符号の検査行列は、巡回行列（cyclic matrix）を用いて表すことができる。かかる巡回行列が、本明細書でいうシフト行列であり、全ての列がある任意の列、例えば最初の列の巡回シフト（サイクリックシフト）である行列として定義される。
「Pの符号」に含まれるシフト行列は、上述したように、P×Pの単位行列または準単位行列がサイクリックシフトされて生成される。即ち、P×Pの単位行列または準単位行列に対して、サイクリックシフトを１列ずつ順次施していくことで、相異なる種類のシフト行列が順次生成されていくことになる。そして、P列分のサイクリックシフトが行われると、元の単位行列または準単位行列が再度得られることになる。即ち、このようなサイクリックシフトの単位がPとなっている。
ここで、留意すべき点は、厳密には、「Pの符号」で用いられる「準単位行列」とそのシフト行列は、QC符号には含まれない点である。即ち、「Pの符号」を含むDVB-S2のLDPC符号には行／列置換後に、右上の１個所のみ、「準単位行列」が現れる。その意味で、厳密には、DVB-S2のLDPC符号は、QC符号ではない。ただし、DVB-S2のLDPC符号の復号器では、この欠けた部分に簡単な例外処理を施しているだけなので、復号器のアーキテクチャとしては、QCの場合と何等違いはない。以上のことから、「Pの符号」は、QC符号のひとつであると記述せずに、QC符号の性質を持ったと記述した次第である。
換言すると、P×Pのシフト行列、その生成元となるP×Pの単位行列若しくはP×Pの準単位行列、これらの和であるP×Pの和行列、P×Pの０行列を構成行列として、各構成行列を規則的に配置させた行列が、P×Pの構造の検査行列である。「Pの符号」は、このような規則的な構造の検査行列として表すことができるゆえ、準巡回符号の性質を持っているのである。
即ち、「Pの符号」とは、P×Pのシフト行列等のP×Pの構成行列を単位として構成されるという規則性を有している。よって、「Pの符号」の復号装置を、従来の技術で図１０の例と同様の構成で実現する場合、ノード演算器は６並列でなくP並列必要となっていた。また、シフト部も、６×６ではなくP×Pのサイクリックシフトを行う必要があった。さらにまた、各種メモリも、６個のデータではなくP個のデータを同時に読み書きできる必要があった。
そこで、本発明人は、P×Pの構造の検査行列に対して、行や列の置換を行うことで、F×Fの構成行列（ただし、Fは１以外のPの約数）を規則的に配置させた行列に並び替える処理またはそれと等価な処理（以下、これらをまとめて並び替え処理と称する）を実行し、並び替え処理後の行列を用いて復号を行う、といった手法を発明した。ここで、F×Fの構成行列の種類としてはP×Pの構成行列と同種類の行列、即ち、F×Fの単位行列、F×Fの準単位行列、F×Fのシフト行列、および、F×Fの和行列、F×Fの０行列が存在する。
なお、並び替える処理またはそれと等価な処理をまとめて並び替え処理と呼称することにしたのは、次の理由による。即ち、P×Pの構造の検査行列に対して行または列を実際に並び替えて行列の構造を変換させた状態でメモリに格納させた後に、復号する（ノード演算器側に提供する）ことは必須ではないからである。即ち、例えば、P×Pの構造のままで検査行列をメモリに格納させ、ノード演算器に提供する段階で、行または列を並び替える手法と等価な手法により、選択的にメモリから読み出してノード演算器に提供してもよいからである。即ち、ノード演算器からすると、検査行列の並び替えが行われた状態と等価な状態で、各受信データが提供されれば足りるからである。
換言すると、本発明の手法とは、P×Pの構造の検査行列で表現される受信値に対して少なくとも列の置換をする処理若しくはそれと等価な処理を含む並び替え処理を施す手法であり、これにより、ノード演算器への受信値の提供の制御として、F×Fの構成行列に対応するF個の受信値を単位とした提供を実現する手法であるといえる。
このような本発明の手法を適用することで、「Pの符号」を復号する場合でも、ノード演算器の並列数をP並列からF並列に削減することができる。また、シフト部も、P×PではなくF×Fのサイクリックシフトを行えば足りるようになる。さらにまた、各種メモリも、P個のデータではなくF個のデータを同時に読み書きできればよくなる。
以上のように、本発明の手法を適用することで、復号装置全体として、従来の復号装置と比較して大幅に回路規模を削減できるようになる。ただし、詳細については後述するが、Pの約数は複数存在する場合があり、かかる場合に、最小値をFとする必要はなく、伝送レートや回路の動作周波数に応じた最適値をFとして採用すると好適である。
さらにまた、詳細については後述するが、Pとは異なる値であって１（という値）以外のQが、Fを約数に持つ場合、即ち、FがPとQの公約数の場合、本発明の手法を適用することで、上述のF並列のノード演算器等を構成とする復号装置を用いて、「Pの符号」のみならず「Qの符号」も選択的に切り換えて復号することが可能になる。
具体的には例えば、P=6に対してF=3とした場合には、本発明の手法を適用することで、復号装置は、図１２の構成を取ることができる。即ち、図１２は、本発明を適用した復号装置の構成例を示している。
図１２の例の復号装置は、受信値バッファ５００、受信値格納メモリ５０１、ノード演算部５０２、シフト部５０３、メッセージ格納メモリ５０４、復号結果格納メモリ５０５、および制御部５０６を含むように構成されている。
このように、図１２の例の復号装置は、全体の構成、即ち、各構成要素（ブロック）の繋がりや、復号装置全体からみた場合の各構成要素の役割（機能）は、制御部５０６を除き、上述の図１０の例の復号装置と基本的に同様である。しかしながら、各構成要素の視点からすると、次のような違いがある。
即ち、図１０の例の受信値バッファ２００、受信値格納メモリ２０１、メッセージ格納メモリ２０４、および復号結果格納メモリ２０５は、P=６個のデータ（6ビット）を同時に読み書きできるメモリ構成をとっている。これに対して、受信値バッファ５００、受信値格納メモリ５０１、メッセージ格納メモリ５０４、復号結果格納メモリ５０５は、F=3個のデータ（3ビット）を同時に読み書きできるメモリ構成をとっている。
また、図１０の例のシフト部２０３は、６×６（＝P×P）のサイクリックシフトを行う構成を有している。これに対して、図１２の例のシフト部５０３は、３×３（＝F×F）のサイクリックシフトを行う構成を有している。
また、図１０の例のノード演算部２０２は、P=６個のノード演算器２１０−１乃至２１０−６を有している。これに対して、図１２の例のノード演算部５０２は、F=３個のノード演算器５１０−１乃至５１０−３を有している。
よって、以上の各構成要素の違いがあることから、図１２の例の復号装置は全体として、図１０の例の従来の復号装置と比較して、回路規模が縮小された装置として構成することができる。
なお、ノード演算器５１０−１乃至５１０−３は、図１１の構成のノード演算器２１０をそのまま採用することができる。もっとも、ノード演算器５１０−１乃至５１０−３自体は、図１１の構成以外の構成を採用した場合にも、本発明を適用できることは言うまでも無い。
また、ノード演算器５１０−１乃至５１０−３の代わりに、３つのバリアブルノード演算器と３つのチェックノード演算器とが別々の回路として構成されている復号装置に対しても、本発明を適用できることも言うまでも無い。
さらにまた、ノード演算器５１０−１乃至５１０−３を用いずにバリアブルノード演算を行う場合にも、本発明を適用できることも言うまでも無い。
以下、図１２の例の復号装置の動作について説明する。
なお、後述するように、図１２の例の復号装置は、Fを約数に持つ任意のPについて、「Pの符号」を復号することができる。ただし、動作の説明をする際には、図１０の例の従来の復号装置との比較を容易なものとすべく、復号対象は、図９の６×６の構造の検査行列で示される「P=6のLDPC符号」であるとする。
受信値バッファ５００は、通信路を通して受信したデータD500を１符号分蓄え、受信値格納メモリ５０１に転送する。
ここで、検査行列の列の並び替えは符号系列の並び替えに相当する。よって、制御部５０６の制御に基づいて、次のような並び替え処理が受信値バッファ５００において実行される。
即ち、図９の検査行列は、６×６の構成行列の集合体として表されている。そこで、６×６の構成行列を並び替えの単位として、その６×６の構成行列を、所定規則に基づいて、３×３の構成行列の集合体となる行列に並び替えを行う、といった並び替え処理が実行される。ここで、所定規則としては、行番号または列番号を２で割った余りが同一になる行と列同士で構成される行列を、即ち、遇数または奇数でそれぞれ区分した行列を、３×３の構成行列とする、といった規則が採用されているとする。
具体的には例えば、図１３は、図９の検査行列の構成行列の一例であって、６×６のシフト行列を示している。図１３において、○（丸印）内の数値は列番号を示しており、□（四角印）内の数値は行番号を示している。
この図１３の６×６のシフト行列に対して、上述の規則に従った並び替え処理が施されると、図１４の行列が得られることとなる。図１４の行列は、図中点線で区分されているように、3×3の０行列、3×3の準単位行列、３×３のシフト行列といったように、３×３の構成行列（点線で区分されている４つの構成行列）で構成されていることがわかる。
以上のような並び替え処理が、その他の６×６の各構成行列にもそれぞれ施される。その結果、図９の６×６の構造の検査行列は、図１５の構造の行列に並び替えられることになる。なお、図１５の例では、３×３の構成行列を単位として区分されていることを明確にすべく、3×3の各構成行列の間には間隔が空けられている。即ち、図１５の例の行列は、3×3の単位行列、3×3の準単位行列、3×3のシフト行列、3×3の和行列、3×3の０行列の組合わせにより構成されている。
よって、図１２の受信値格納メモリ５０１の後段の動作は、6（＝P）が3(=F)に変化した以外は、図１０の受信値格納メモリ２０１の後段の動作と同様となる。換言すると、あたかも「P=3の符号」を復号するのと全く同様の動作が行われる。
なお、伝送方式として、そもそも符号ビットの順番を入れ替えて通信路に送出する方式が採用されている場合は、その並び替えも、上述の並び替え処理とともにまたはその前後に、受信値バッファ５００において行われる。
以上、Fとして、P=6の約数である3を採用した場合の例について説明した。当然ながら、P=6の別の約数（１を除く）、即ち2を採用することもできる。ただし、この場合、図９の６×６の構造の検査行列に施される並び替え処理において採用される所定規則とは、次のような規則となる。即ち、行番号または列番号を３で割った余りが同一になる行と列同士で構成される行列を、２×２の構成行列とする、といった規則が採用される。
具体的には例えば、図１３の６×６のシフト行列に対して、かかる規則に従った並び替え処理が施されると、図１６の行列が得られる。図１６の行列は、図中点線で区分されているように、2×2の０行列、2×2の準単位行列、2×2のシフト行列といったように、2×2の構成行列（点線で区分されている９つの構成行列）で構成されていることがわかる。
よって、この場合も、受信値格納メモリ５０１の後段の動作は、6（＝P）が2(=F)に変化した以外は、図１０の例の受信値格納メモリ２０１以降の後段の動作と同様になる。換言すると、あたかも「P=2のLDPC符号」を復号するのと全く同様の動作が行われる。
即ち、F=2とした場合には、復号装置は、図１２の構成をとる必要はなく、2並列のノード演算器、2×2のサイクリックシフトを行うシフト部、および、2個のデータ（2bit）のデータを同時に読み書きできる各種メモリを有する構成を取れば足りる。
さらに、以上においてはPが6である場合の例について説明したが、当然ながらPは6以外となる場合がある。例えば、検査行列の構造によっては、P=360となる場合がある。このように任意の値がPとなる場合でも、本発明の手法は適用可能である。そして、本発明の手法によれば、Pが決定した後は、１以外の任意の約数をFとして採用することも可能である。
即ち、任意のPと、そのPの約数のうちの１を除く任意のFが採用された場合、P×Pの構造の検査行列（PのLDPC符号）に対して、次のような所定規則に従った並び替え処理を施すとで、F並列のノード演算器、F×Fのサイクリックシフトを行うシフト部、および、F個のデータ（Fビット）のデータを同時に読み書きできる各種メモリを有する構成で、復号装置を実装できるようになる。
この場合の所定規則とは、P=F×Jとすると、行番号0乃至P-1または列番号0乃至P-1をJで割った余りが同一になる行と列同士で構成される行列を、F×Fの構成行列とする、といった規則となる。そして、かかる規則に従った並び替え処理が、P×Pの構造の検査行列を構成するP×Pの各種構成行列のそれぞれに施されることになる。
なお、上述したように、ここでいう並べ替え処理とは、P×Pの構造の検査行列を並び替えた状態でメモリに記録することまでに限定する処理ではない。即ち、上述の例では、受信値バッファ５００において並び替え処理が実行され、並び替え後の行列がいったん格納されて、その並び替え後の行列が、受信値格納メモリ５０１を介してノード演算部５０２に提供されていた。しかしながら、ノード演算部５０２の前段のメモリでは、P×Pの構造の検査行列のまま格納させておき、かかるメモリからノード演算部５０２に対して提供する際に、上述の所定規則に従った並び替え処理を読み出しの処理として適用し、即ち、上述の所定規則に従って選択的にメモリからデータを読み出して、ノード演算部５０２に提供するようにしてもよい。即ち、ここでいう並べ替え処理とは、このような読み出し処理も含めた広義な概念の処理である。なお、読み出し処理の制御については、制御部（図１２の例では制御部５０６）に担当させれば容易に実現可能である。
また、上述の例とは、符号長108，符号化率2/3の例であったが、これらの値は例示にしか過ぎないことは言うまでもない。即ち、例えば、P=6となり、エッジ総数が同じかそれ以下であれば、任意の符号長、任意の符号化率を採用しても、制御信号を変えることで、同一の復号装置を用いて復号することが可能である。さらに、Pが同じで符号長とエッジの総数がそれぞれ所定値以下であるという条件を満たす符号の復号装置は、同じ条件を満たし得る符号長、異なる符号化率の符号であっても復号することができる。
以上の内容をまとめると、本発明を適用することで、Pの値に拘束されることなく、伝送レートや動作周波数に応じて、復号の並列性Fを可能な範囲内（Pの約数という範囲内）で任意に選択できる。これにより、回路規模の小さい復号装置を開発することが容易に可能になる。
即ち、例えば、Pが例えば360のときには、 Fは360，180，120といった約数の中から任意のものを選択することができる。このFは、上述した如くノード演算器の並列数になっていることからもわかるように、本発明を採用した場合には復号の並列性を示す値であるといえる。そこで、復号装置の開発者等は、復号の並列性を考慮しつつ、伝送レートと回路の動作周波数に応じて最適な値をFとして選ぶことができるようになる。
即ち、必要な伝送レートに対して、F として大きい値のPの約数を選択ときには、復号の並列性が必要以上に高いため、復号に必要な時間よりも長い間隔でしかデータが到来しない。そこで、データが到来する時間と復号に必要な時間が同程度になるように、Pの約数のうちの適当な値をFとして選ぶことで、復号の並列性を下げ、その結果、復号装置の回路規模を削減できる。また、将来的に回路が高速動作するようになれば、Fとして小さい値を採用したとしても、復号装置の並列性を下げても従来と同等の性能を達成することが可能になる。
さらに、PとQ（ただし、P > Q）が公約数を持つとき、その公約数を復号の並列性Fとして採用した復号装置は、「Pの符号」と「Qの符号」の両者を復号することが可能である。
従って、例えば、高い伝送レートを必要とするサービスには大きな「Pの符号」を用い、携帯型受信機用サービス（それゆえ伝送レートが低くてよいサービス）には小さな「Qの符号」を用いた場合でも、１つの復号装置で、どちらのサービスの符号も復号できる復号機能を備えた共通受信装置を実現することができる。
即ち、共通受信装置を実現可能であることは、「Pの符号」と「Q の符号」の両方を伝送システムの中に共存させることを可能にする。
例えば、DVB-S.2のLDPC符号を8PSK,30Msym/sで送信する場合には、符号ビットのビットレートは90Mbpsになる。検査行列の列重みの平均は概ね3.5程度であるため、符号1ビット当たりに必要な演算量は、復号回数を50回とすると、3.5×50×2=350程度になる。よって、クロック数としては、この演算量に、回路の効率性として仮に1.5を掛けた数が必要になる。そのクロック数を演算の並列性360で割ると、復号装置は90Mbps×350×1.5/360=131.25MHzで動作すればよいことになる。
この場合、復号の並列性をP=360とした従来の復号装置では、360個のデータを同時に読み書きできるメモリを実現すべく、ビット数が大きく、ワード数の少ない面積効率の悪いRAMを採用する必要があった。また、かかる従来の復号装置では、ノード演算器も360個有する必要があった。このようなことから、従来の復号装置は、回路規模が非常に大きなものであった。
ここで、仮に、DVB-S.2のLDPC符号を、上述の90Mbpsよりも低い伝送方式、例えば15Mbpsの伝送方式に応用する場合、復号の並列性をF=60としても、同じ動作周波数で同じ復号回数を実現すること、即ち同じ復号性能を達成することができる。
復号の並列性をF=60とすることができれば、同時に読み書きすべきデータが60個で済む。よって、メモリを構成する場合には、上述の従来の面積効率の悪いRAMと比較してワード数が6倍のRAMであって、そのビット数を減らした同一総数のRAMを採用することができる。或いは、そのビット数自体は同一のRAMを採用した場合でも、RAMの総数を減らすことが可能になる。いずれにしても、同じビット数のデータを保存するための面積効率が格段に上がることになる。また、ノード演算器の数もF=60個になるため、論理回路の規模も減らすことができる。
即ち、DVB-S.2のLDPC符号を、例えば地上波の放送に利用する場合、消費電力の問題で携帯型移動受信機での受信は難しくなる。そこで、例えば携帯型受信機向けには、Qを60としたより短い符号長の符号を用いてサービスを行う場合が想定できる。そのような場合であっても、本発明を適用することで、復号の並列性をF=60として符号長64800の符号まで復号できる復号装置であって、「P=360の符号」と「Q=60の符号」の両者を復号可能な復号装置を容易に実現することができる。よって、かかる復号装置を備えた受信装置は、固定受信用サービス（「P=360の符号」を用いるサービス）と、携帯型受信機用サービス（「Q=60の符号」を用いるサービス）の両方を受信することが可能になる。
以上の内容をまとめると、本発明を適用することで、大きな値Pを持つLDPC符号の復号装置を、その約数Fに基づいて実装することが可能になる。即ち、ビットレートの低い伝送方式や、将来回路が高速化した場合には、従来と比較して回路規模の小さい復号装置を実現することが可能になる。
また、本発明を適用することで、公約数Fを持つ整数に基づく符号は、全てFに基づく復号装置で復号することができるようになる。よって、伝送レートや受信形態の異なるサービスに応じて、適した大きさのLDPC符号をひとつの伝送システムに共存させることが可能になる。
即ち、上述の例の伝送システムは、「Pの符号」と「Qの符号」の２種類のみが用いられたが、１以外の整数値Fの倍数となる相異なる複数の整数値のうちの、システムの設計者等により選択されたK個（Kは２以上の整数値）の整数値α（αは、選択されたK個の整数値を示す）のそれぞれに対応するK種類の「αの符号」を用いることが可能になる。
ところで、上述した一覧表示処理も含む一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。
上述した一連の処理をソフトウエアにより実行させる場合、本発明が適用される復号装置は、例えば、図１７に示されるコンピュータで構成することもできる。
図１７において、CPU（Central Processing Unit）１００１は、ROM（Read Only Memory）１００２に記録されているプログラム、または記憶部１００８からRAM（Random Access Memory）１００３にロードされたプログラムに従って各種の処理を実行する。RAM１００３にはまた、CPU１００１が各種の処理を実行する上において必要なデータなども適宜記憶される。
CPU１００１、ROM１００２、およびRAM１００３は、バス１００４を介して相互に接続されている。このバス１００４にはまた、入出力インターフェース１００５も接続されている。
入出力インターフェース１００５には、キーボード、マウスなどよりなる入力部１００６、ディスプレイなどよりなる出力部１００７、ハードディスクなどより構成される記憶部１００８、および、モデム、ターミナルアダプタなどより構成される通信部１００９が接続されている。通信部１００９は、インターネットを含むネットワークを介して他の装置（図示せず）との間で行う通信を制御する。
入出力インターフェース１００５にはまた、必要に応じてドライブ１０１０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどよりなるリムーバブルメディア１０１１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部１００８にインストールされる。
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどに、ネットワークや記録媒体からインストールされる。
このようなプログラムを含む記録媒体は、図１７に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（ＭＤ（Mini-Disk）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア（パッケージメディア）１２１１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているROM１００２や、記憶部１００８に含まれるハードディスクなどで構成される。
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、その順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
また、本明細書において、システムとは、複数の装置や処理部により構成される装置全体を表すものである。
LDPC 符号の検査行列の例を示す図である。 LDPC符号の下三角形な検査行列の例を示す図である。 LDPC符号を復号する際の一連の処理行程を説明するフローチャートである。 メッセージの流れの説明図である。 (3,6) LDPC 符号の 検査行列の例を示す図である。 図５の検査行列のタナーグラフを示す図である。 バリアブルノードでのメッセージ計算を説明する図である。 チェックノードでのメッセージ計算を説明する図である。 ６×６の構造の検査行列の例を示す図である。 LDPC 符号の従来の復号装置の構成例を示すブロック図である。 ノード演算器の構成例を示すブロック図である。 本発明が適用されるLDPC符号の構成例を示すブロック図である。 ６×６のシフト行列の一例を示す図である。 図１３のシフト行列の行や列を並べることで、３×３の構成行列を生成する手法を説明する図である。 図９の６×６の構造の検査行列に対して、図１４の手法の並び替え処理を施すことで得られる３×３の構造の行列を示す図である。 図１３のシフト行列の行や列を並べることで、２×２の構成行列を生成する手法を説明する図である。 本発明が適用される復号装置の他の実施形態としての、コンピュータの構成例を示すブロック図である。
符号の説明
５００ 受信値バッファ， ５０１ 受信値格納メモリ， ５０２ ノード演算部， ５０３ シフト部， ５０４ 復号結果格納メモリ， ５０５ メッセージ格納メモリ， １００１ CPU， １００２ ROM， １００３ RAM， １００８ 記憶部， １０１０ リムーバブルメディア

Claims (8)

  1. LDPC(Low Density Parity Check)符号を復号する復号装置において、
    前記LDPC符号が、
    P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される第１の形態で受信される場合と、
    QがPとは異なる値であって１以外の値であるとき、Q×Qの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはQ×Qの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第２の構造の行列で表現される第２の形態で受信される場合とが存在し、
    FをPとQの１以外の公約数としたとき、前記第１の形態または前記第２の形態のLDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行う演算を少なくとも実行する
    復号装置。
  2. 前記F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行い、
    各演算の結果得られるF個のメッセージを出力するメッセージ計算手段と、
    前記メッセージ計算手段から出力されるF個の前記メッセージに対して、F×Fのサイクリックシフトを行って出力するシフト手段と、
    前記シフト手段から出力されるF個の前記メッセージの書き込み、書き込まれたF個の前記メッセージの読み出し、または、F個の前記受信値の読み出し若しくは書き込みができる記憶手段と
    を備える請求項１に記載の復号装置。
  3. F×Fの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはF×Fの０行列を第３の構成行列として、複数の前記第３の構成行列の組合せによる第３の構造の行列を定義した場合に、前記第１の構造または前記第２の構造の検査行列で表現される前記受信値に対して少なくとも列置換処理を施すことで、前記メッセージ計算手段への前記受信値の提供の制御として、前記第３の構成行列に対応するF個の前記受信値を単位とする提供の制御を行う制御手段
    をさらに備える請求項２に記載の復号装置。
  4. LDPC(Low Density Parity Check)符号を復号する復号装置の復号方法において、
    前記LDPC符号が、
    P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される第１の形態で前記復号装置に受信される場合と、
    QがPとは異なる値であって１以外の値であるとき、Q×Qの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはQ×Qの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第２の構造の行列で表現される第２の形態で前記復号装置に受信される場合とが存在し、
    FをPとQの１以外の公約数としたとき、前記第１の形態または前記第２の形態のLDPC符号を受信した結果得られる受信値を復号するために前記復号装置が演算するステップとして、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行う演算のステップを含む
    復号方法。
  5. LDPC(Low Density Parity Check)符号を復号する復号装置を制御するコンピュータに、
    前記LDPC符号が、
    P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を第１の構成行列として、複数の前記第１の構成行列の組合せによる第１の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第１の構造の行列で表現される第１の形態で前記復号装置に受信される場合と、
    QがPとは異なる値であって１以外の値であるとき、Q×Qの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはQ×Qの０行列を第２の構成行列として、複数の前記第２の構成行列の組合せによる第２の構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記第２の構造の行列で表現される第２の形態で前記復号装置に受信される場合とが存在し、
    FをPとQの１以外の公約数としたとき、前記第１の形態または前記第２の形態のLDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算
    を並列的に行う演算する
    ステップを実行させるプログラム。
  6. LDPC(Low Density Parity Check)符号を誤り訂正符号として用いる送受信システムにおいて、
    前記LDPC符号の形態として、１以外の任意の整数値をαとしたときに、α×αの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはα×αの０行列を構成行列として、複数の前記構成行列の組合せによる構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記構造の行列で表現される形態が取り得る場合、
    １以外の整数値Fの倍数となる相異なる複数の整数値のうちの、K個（Kは２以上の整数値）の整数値が選択され、選択された前記K個の整数値が前記αとしてそれぞれ代入されたときに取りうる前記K種類の前記形態のLDPC符号が、誤り訂正符号としてそれぞれ用いられる
    送受信システム。
  7. LDPC(Low Density Parity Check)符号を誤り訂正符号として用いる送受信システムの受信装置において、
    前記LDPC符号の形態として、１以外の任意の整数値をαとしたときに、α×αの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはα×αの０行列を構成行列として、複数の前記構成行列の組合せによる構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記構造の行列で表現される形態が取り得る場合、
    １以外の整数値Fの倍数となる相異なる複数の整数値のうちの、K個（Kは２以上の整数値）の整数値が選択され、選択された前記K個の整数値が前記αとしてそれぞれ代入されたときに取りうる前記K種類の前記形態のLDPC符号が、誤り訂正符号としてそれぞれ用いられる
    送受信システムの受信装置であって、
    前記K種類のうちの何れかの種類の形態のLDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行う演算を少なくとも実行する復号手段を
    備える受信装置。
  8. LDPC(Low Density Parity Check)符号を誤り訂正符号として用いる送受信システムの受信装置のうちの、
    前記LDPC符号の形態として、１以外の任意の整数値をαとしたときに、α×αの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはα×αの０行列を構成行列として、複数の前記構成行列の組合せによる構造の検査行列で元々表現されるか、または、元々の検査行列の行と列のうちの少なくとも1以上の置換により前記構造の行列で表現される形態が取り得る場合、
    １以外の整数値Fの倍数となる相異なる複数の整数値のうちの、K個（Kは２以上の整数値）の整数値が選択され、選択された前記K個の整数値が前記αとしてそれぞれ代入されたときに取りうる前記K種類の前記形態のLDPC符号が、誤り訂正符号としてそれぞれ用いられる
    送受信システムの受信装置の受信方法であって、
    前記K種類のうちの何れかの種類の形態のLDPC符号を受信した結果得られる受信値を復号するための演算として、F個のチェックノードの演算またはF個のバリアブルノードの演算を並列的に行う演算を少なくとも実行する
    ステップを含む受信方法。
JP2007272517A 2007-10-19 2007-10-19 復号装置および方法、送受信システム、受信装置および方法、並びにプログラム Expired - Fee Related JP4487212B2 (ja)

Priority Applications (6)

Application Number Priority Date Filing Date Title
JP2007272517A JP4487212B2 (ja) 2007-10-19 2007-10-19 復号装置および方法、送受信システム、受信装置および方法、並びにプログラム
EP08253289A EP2088679A3 (en) 2007-10-19 2008-10-09 Data decoding apparatus, data decoding method, data transmitting/receiving system, data receiving apparatus, data receiving method and program
TW097139222A TWI373922B (en) 2007-10-19 2008-10-13 Data decoding apparatus, data decoding method, data tramsmitting/receiving system, data receiving apparatus, data receiving method and program
KR1020080101347A KR20090040223A (ko) 2007-10-19 2008-10-15 복호 장치 및 방법, 송수신 시스템, 수신장치 및 방법, 및 프로그램
US12/253,324 US8234555B2 (en) 2007-10-19 2008-10-17 Data decoding apparatus, data decoding method, data transmitting/receiving system, data receiving apparatus, data receiving method and program
CN2008101702881A CN101442317B (zh) 2007-10-19 2008-10-20 数据解码装置和方法、发送/接收系统、接收装置和方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2007272517A JP4487212B2 (ja) 2007-10-19 2007-10-19 復号装置および方法、送受信システム、受信装置および方法、並びにプログラム

Publications (2)

Publication Number Publication Date
JP2009100421A JP2009100421A (ja) 2009-05-07
JP4487212B2 true JP4487212B2 (ja) 2010-06-23

Family

ID=40564717

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2007272517A Expired - Fee Related JP4487212B2 (ja) 2007-10-19 2007-10-19 復号装置および方法、送受信システム、受信装置および方法、並びにプログラム

Country Status (6)

Country Link
US (1) US8234555B2 (ja)
EP (1) EP2088679A3 (ja)
JP (1) JP4487212B2 (ja)
KR (1) KR20090040223A (ja)
CN (1) CN101442317B (ja)
TW (1) TWI373922B (ja)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8276053B2 (en) * 2009-11-08 2012-09-25 Mediatek Inc. Decoding circuit operating in response to decoded result and/or a plurality of viterbi target levels with pattern dependency
TW201126537A (en) * 2010-01-20 2011-08-01 Sunplus Technology Co Ltd Memory utilization method for low density parity check code, low density parity check code decoding method and apparatus thereof
US8539304B1 (en) * 2010-04-27 2013-09-17 Marvell International Ltd. Parallel encoder for low-density parity-check (LDPC) codes
JP4861509B1 (ja) 2010-10-29 2012-01-25 株式会社東芝 符号化・復号化装置、データ記憶装置、及び方法
WO2012098909A1 (ja) * 2011-01-21 2012-07-26 パナソニック株式会社 符号化方法、復号方法、符号化器、及び、復号器
US10063262B2 (en) 2011-02-28 2018-08-28 Inphi Corporation Non-concatenated FEC codes for ultra-high speed optical transport networks
US10103751B2 (en) * 2011-02-28 2018-10-16 Inphi Corporation Non-concatenated FEC codes for ultra-high speed optical transport networks
US8918694B2 (en) 2011-02-28 2014-12-23 Clariphy Communications, Inc. Non-concatenated FEC codes for ultra-high speed optical transport networks
CN107534511B (zh) 2015-11-17 2020-04-28 华为技术有限公司 低密度奇偶校验码的译码方法和译码器
US10050642B2 (en) * 2016-03-17 2018-08-14 Silicon Motion Inc. Low power scheme for bit flipping low density parity check decoder
US10116333B2 (en) * 2016-07-29 2018-10-30 Sandisk Technologies Llc Decoder with parallel decoding paths
KR102523059B1 (ko) * 2018-04-18 2023-04-19 에스케이하이닉스 주식회사 에러 정정 회로 및 그것을 포함하는 메모리 시스템
US10998919B2 (en) * 2019-10-02 2021-05-04 Microsoft Technology Licensing, Llc Coded stream processing
US11424766B1 (en) 2020-01-31 2022-08-23 Marvell Asia Pte Ltd. Method and device for energy-efficient decoders
US11265015B2 (en) * 2020-05-15 2022-03-01 SK Hynix Inc. Out-of-order processing for bit-flipping decoders in non-volatile memory devices

Family Cites Families (27)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20030033570A1 (en) * 2001-05-09 2003-02-13 Khannanov Roman R. Method and apparatus for encoding and decoding low density parity check codes and low density turbo product codes
US6633856B2 (en) * 2001-06-15 2003-10-14 Flarion Technologies, Inc. Methods and apparatus for decoding LDPC codes
US7203887B2 (en) * 2002-07-03 2007-04-10 The Directtv Group, Inc. Method and system for routing in low density parity check (LDPC) decoders
US7162684B2 (en) * 2003-01-27 2007-01-09 Texas Instruments Incorporated Efficient encoder for low-density-parity-check codes
US6957375B2 (en) * 2003-02-26 2005-10-18 Flarion Technologies, Inc. Method and apparatus for performing low-density parity-check (LDPC) code operations using a multi-level permutation
JP4224777B2 (ja) * 2003-05-13 2009-02-18 ソニー株式会社 復号方法および復号装置、並びにプログラム
JP4225163B2 (ja) * 2003-05-13 2009-02-18 ソニー株式会社 復号装置および復号方法、並びにプログラム
US7296208B2 (en) * 2003-07-03 2007-11-13 The Directv Group, Inc. Method and system for generating parallel decodable low density parity check (LDPC) codes
KR100809619B1 (ko) * 2003-08-26 2008-03-05 삼성전자주식회사 이동 통신 시스템에서 블록 저밀도 패러티 검사 부호부호화/복호 장치 및 방법
FI121431B (fi) * 2004-09-13 2010-11-15 Tamfelt Pmc Oy Paperikoneessa käytettävä kudosrakenne ja menetelmä sen valmistamiseksi
WO2006039801A1 (en) * 2004-10-12 2006-04-20 Nortel Networks Limited System and method for low density parity check encoding of data
CN100550655C (zh) * 2004-11-04 2009-10-14 中兴通讯股份有限公司 一种低密度奇偶校验码的编码器/译码器及其生成方法
KR100924189B1 (ko) 2004-12-02 2009-10-29 미쓰비시덴키 가부시키가이샤 복호 장치 및 통신 장치
CN100583651C (zh) * 2004-12-22 2010-01-20 Lg电子株式会社 用于使用信道代码解码的装置和方法
US7900127B2 (en) * 2005-01-10 2011-03-01 Broadcom Corporation LDPC (Low Density Parity Check) codes with corresponding parity check matrices selectively constructed with CSI (Cyclic Shifted Identity) and null sub-matrices
JP4622654B2 (ja) * 2005-04-25 2011-02-02 ソニー株式会社 復号装置および復号方法
JP2006340016A (ja) 2005-06-01 2006-12-14 Toshiba Microelectronics Corp 誤り訂正符号復号装置及びそれを用いた復号方法
JP2007036776A (ja) * 2005-07-28 2007-02-08 Sony Corp 復号装置および復号方法
JP2007081602A (ja) * 2005-09-13 2007-03-29 Sony Corp 復号装置および復号方法
KR100946905B1 (ko) * 2005-09-27 2010-03-09 삼성전자주식회사 저밀도 패리티 검사 부호를 사용하는 통신 시스템에서 신호 송수신 장치 및 방법
US7707479B2 (en) * 2005-12-13 2010-04-27 Samsung Electronics Co., Ltd. Method of generating structured irregular low density parity checkcodes for wireless systems
US7805652B1 (en) * 2006-02-10 2010-09-28 Marvell International Ltd. Methods for generating and implementing quasi-cyclic irregular low-density parity check codes
JP2007272517A (ja) 2006-03-31 2007-10-18 National Institute Of Multimedia Education マイクロシナリオデータ分析システムおよびマイクロシナリオデータ分析プログラム
JP4856605B2 (ja) * 2006-08-31 2012-01-18 パナソニック株式会社 符号化方法、符号化装置、及び送信装置
JP4702632B2 (ja) * 2007-04-06 2011-06-15 ソニー株式会社 符号化方法および符号化装置、並びにプログラム
JP2008301152A (ja) 2007-05-31 2008-12-11 Sony Corp 復号装置および方法、並びにプログラム
JP4487213B2 (ja) * 2007-10-19 2010-06-23 ソニー株式会社 復号装置および方法、並びにプログラム

Also Published As

Publication number Publication date
CN101442317B (zh) 2012-07-11
EP2088679A2 (en) 2009-08-12
JP2009100421A (ja) 2009-05-07
US20090106621A1 (en) 2009-04-23
CN101442317A (zh) 2009-05-27
TW200935754A (en) 2009-08-16
US8234555B2 (en) 2012-07-31
TWI373922B (en) 2012-10-01
KR20090040223A (ko) 2009-04-23
EP2088679A3 (en) 2012-08-01

Similar Documents

Publication Publication Date Title
JP4487213B2 (ja) 復号装置および方法、並びにプログラム
JP4487212B2 (ja) 復号装置および方法、送受信システム、受信装置および方法、並びにプログラム
JP4224777B2 (ja) 復号方法および復号装置、並びにプログラム
KR101090001B1 (ko) 복호 장치 및 복호 방법, 및 기록 매체
JP4807063B2 (ja) 復号装置、制御方法、およびプログラム
KR101164283B1 (ko) 복호 장치 및 복호 방법
JP4285148B2 (ja) 復号装置および復号方法、並びにプログラム
JP4284600B2 (ja) 復号装置
JP2008301152A (ja) 復号装置および方法、並びにプログラム
JP4821724B2 (ja) 復号装置および復号方法
JP4729964B2 (ja) 復号装置および復号方法
JP4730592B2 (ja) 復号装置および復号方法
JP4288582B2 (ja) 復号装置および復号方法、並びにプログラム

Legal Events

Date Code Title Description
A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20090709

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20090831

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20100304

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20100317

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130409

Year of fee payment: 3

R151 Written notification of patent or utility model registration

Ref document number: 4487212

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R151

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130409

Year of fee payment: 3

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140409

Year of fee payment: 4

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

LAPS Cancellation because of no payment of annual fees