(57)【要約】【課題】本発明は、並列処理を行う上で必要となる最小限のＸＯＲ演算回数により演算処理を行うことができる符号化・復号化装置を提供することを目的とする。【解決手段】符号化・復号化処理部１０は、所定の規則性を有する検査行列に基づいて入力データに対応するハミング符号の符号語を生成する符号化処理を行うとともに検査行列に基づいてハミング符号の受信語のエラー位置を検出する復号化処理を行い、ハミング符号が符号長２m−１及び情報ビット数２m−ｍ−１の２元ハミング符号である場合に、ＸＯＲ演算回数を（２m+1−２ｍ−２）回処理して復号化処理する演算回路を備えている。【選択図】図１
2014064065.tif 000002
【特許請求の範囲】
【請求項１】
所定の規則性を有する検査行列に基づいて入力データに対応するハミング符号の符号語を生成する符号化手段と、前記検査行列に基づいてハミング符号の受信語のエラー位置を検出する復号化手段とを備える符号化・復号化装置であって、前記復号化手段は、ハミング符号が符号長２m−１及び情報ビット数２m−ｍ−１の２元ハミング符号である場合に、ＸＯＲ演算回数を（２m+1−２ｍ−２）回処理して復号化処理する演算回路を備えている符号化・復号化装置。
【請求項２】
前記符号化手段は、ハミング符号が符号長２m−１及び情報ビット数２m−ｍ−１の２元ハミング符号である場合に、ＸＯＲ演算回数を（２m+1−３ｍ−２）回処理して符号化処理する演算回路を備えている請求項１に記載の符号化・復号化装置。
【請求項３】
前記復号化手段又は前記符号化手段は、１回のＸＯＲ演算に起因する遅延時間をｔとした場合に、前記演算回路の遅延時間が（ｍ−１）ｔに設定されている請求項１又は２に記載の符号化・復号化装置。
【請求項４】
符号長２m−１及び情報ビット数２m−ｍ−１の２元ハミング符号の受信語ｒj，ｊ＝１，２，…，２m−１に対してＸＯＲ演算を複数回行ってエラー位置を検出するシンドロームｓi，ｉ＝１，２，…，ｍを生成する復号化処理の演算回路設定方法であって、以下の規則１から規則４に基づいて表記された順序でＸＯＲ演算を行うように演算回路を構成する演算回路設定方法。
＜規則１＞
左端の列に上から順にs1からsmを並べる。
＜規則２＞
ｊの二進表記であるｂm-1ｂm-2…ｂ0，ｂi ∈{０，１}について以下の値を求め、
【数１４】
2014064065.tif 000022
この値が同じものを小さい値１から大きい値ｍの順に左から右に列として配置し、各列ではｊの小さい値から大きい値の順に上から下に配置する。
＜規則３＞
規則２で作成した配置図において、ｂm-1ｂm-2…ｂ0を値０か値１の１ビットを保持する節点ｊとし、各節点ｊの保持する値をｖ（ｊ）として、演算開始時刻での値ｖ（ｊ）をｒjとする。左端の列に配置された節点ｊ＝２i-1をｓiに対応させ、ｓiを求めるｒjのＸＯＲ演算の演算式に基づいてｒjに対応する節点ｊ同士を線で結ぶ。
＜規則４＞
ｊ＜ｊ’を満たす節点ｊと節点ｊ’との間を結ぶ線がある場合には、演算開始時刻から１回のＸＯＲ演算に起因する遅延時間に基づいて設定されたタイミングでｖ（ｊ）及びｖ（ｊ’）のＸＯＲ演算を行い、節点ｊの値をＸＯＲ演算結果とする。
【請求項５】
ｍ＝ｋ−１（ｋは、３以上の自然数）におけるシンドロームを生成する演算回路に基づいてｍ＝ｋにおけるシンドロームを生成する演算回路を設定する請求項４に記載された演算回路設定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶処理装置、通信処理装置等のデータ処理装置に用いられる符号化・復号化装置及び符号化・復号化処理を行う演算回路の設定方法に関する。
【背景技術】
【０００２】
記憶処理装置や通信処理装置等のデータ処理装置は、一般的にデータの誤り検出及び訂正を行う誤り訂正機能を備えている。誤り訂正機能としては、１ビット訂正可能なハミング符号（短縮化ハミング符号語）を用いた符号化・復号化方式が提案されている。こうした符号化・復号化方式では、情報ビット列（情報ベクトル）及び生成行列に基づいてハミング符号を生成する符号化処理を実行するとともに、生成行列に対応する検査行列（パリティ検査行列）及びハミング符号に基づいてエラー位置を検出する復号化処理を実行する。
【０００３】
情報ビット列は、記憶処理装置では記録媒体に記憶される入力データが該当し、通信処理装置では送信データが該当する。そして、ハミング符号は、情報ビット列及びパリティビット列（パリティデータ）を組み合せて構成される。復号化処理では、記憶処理装置では記録媒体から読み出されるハミング符号からなる出力データのエラー位置を検出し、通信処理装置では受信データのエラー位置を検出して、そのエラー位置を示すデータ（以下「シンドローム（syndrome）」と称する）を生成する。エラー訂正処理では、復号化処理により検出されたエラー位置のエラービットを訂正してデータ出力処理を行う。
【０００４】
簡単な誤り訂正符号の１つである２元ハミング符号を用いた符号化・復号化装置における排他的論理和（ＸＯＲ）の演算処理について考える。２元体をＦ2と表記し、その元を０と１で表す。２元体での加法については、以下の通り表記する。
【数１】
2014064065.tif 000003
なお、この表記において、２項間の記号は排他的論理和（ＸＯＲ）である。
２以上の任意の整数ｍに対して、Ｆ2＝{０，１}上のすべての非零のｍ次元ベクトルを列として並べたｍ行２m−１列の行列を検査行列として定義される符号は符号長２m−１、情報ビット数２m−ｍ−１の２元ハミング符号であり、（２m−１，２m−ｍ−１）ハミング符号と表記する。（２m−１，２m−ｍ−１）ハミング符号を定める検査行列をＨと表記する。特に、検査行列のｊ列目ｈjTを
ｈjT＝（ｈ1,j，ｈ2,j，…，ｈi,j，…，ｈm,j）∈Ｆ2m
とし、
【数２】
2014064065.tif 000004
を満たすようにｈjを定めた検査行列をＨmと表記する。ただし、ｈTはｈの転置を表す。（２m−１，２m−ｍ−１）ハミング符号は最小距離が３であり、ハミング限界を等号で満たす完全符号である（非特許文献１参照）。
【０００５】
そして、（２m−１，２m−ｍ−１）ハミング符号における検査行列Ｈでの列の並べ方は任意であり、巡回符号である（２m−１，２m−ｍ−１）ハミング符号はシフトレジスタを用いたｍ段符号器や２m−ｍ−１段符号器及び巡回ハミング符号の復号器を用いた符号化・復号化装置によって実現することができる（非特許文献１参照）。
【０００６】
これに対して、符号器及び復号器の高速化を図る方法として、符号語や復号結果の各ビットを並列に出力する並列符号器及び並列復号器が提案されている（特許文献１参照）。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
こうした並列符号器及び並列復号器については、演算処理速度が高速化するものの演算回路が複雑化するため実用化に至っていないのが現状である。演算処理では２入力１出力のＸＯＲ演算を組み合せて処理するのが一般的であるが、こうしたＸＯＲ演算の回数は、演算処理速度の向上、演算回路の構成等に直接影響を与えるため、安定した並列処理を行う上で必要となる最適な演算回数の設定が求められている。
【０００８】
そこで、本発明は、並列処理を行う上で必要となる最小限のＸＯＲ演算回数により演算処理を行うことができる符号化・復号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係る符号化・復号化装置は、所定の規則性を有する検査行列に基づいて入力データに対応するハミング符号の符号語を生成する符号化手段と、前記検査行列に基づいてハミング符号の受信語のエラー位置を検出する復号化手段とを備える符号化・復号化装置であって、前記復号化手段は、ハミング符号が符号長２m−１及び情報ビット数２m−ｍ−１の２元ハミング符号である場合に、ＸＯＲ演算回数を（２m+1−２ｍ−２）回処理して復号化処理する演算回路を備えている。さらに、前記符号化手段は、ハミング符号が符号長２m−１及び情報ビット数２m−ｍ−１の２元ハミング符号である場合に、ＸＯＲ演算回数を（２m+1−３ｍ−２）回処理して符号化処理する演算回路を備えている。さらに、前記復号化手段又は前記符号化手段は、１回のＸＯＲ演算に起因する遅延時間をｔとした場合に、前記演算回路の遅延時間が（ｍ−１）ｔに設定されている。
【００１０】
本発明に係る演算回路設定方法は、符号長２m−１及び情報ビット数２m−ｍ−１の２元ハミング符号の受信語ｒj，ｊ＝１，２，…，２m−１に対してＸＯＲ演算を複数回行ってエラー位置を検出するシンドロームｓi，ｉ＝１，２，…，ｍを生成する復号化処理の演算回路設定方法であって、以下の規則１から規則４に基づいて表記された順序でＸＯＲ演算を行うように演算回路を構成する。
＜規則１＞
左端の列に上から順にs1からsmを並べる。
＜規則２＞
ｊの二進表記であるｂm-1ｂm-2…ｂ0，ｂi ∈{０，１}について以下の値を求め、
【数１４】
2014064065.tif 000005
この値が同じものを小さい値１から大きい値ｍの順に左から右に列として配置し、各列ではｊの小さい値から大きい値の順に上から下に配置する。
＜規則３＞
規則２で作成した配置図において、ｂm-1ｂm-2…ｂ0を値０か値１の１ビットを保持する節点ｊとし、各節点ｊの保持する値をｖ（ｊ）として、演算開始時刻での値ｖ（ｊ）をｒjとする。左端の列に配置された節点ｊ＝２i-1をｓiに対応させ、ｓiを求めるｒjのＸＯＲ演算の演算式に基づいてｒjに対応する節点ｊ同士を線で結ぶ。
＜規則４＞
ｊ＜ｊ’を満たす節点ｊと節点ｊ’との間を結ぶ線がある場合には、演算開始時刻から１回のＸＯＲ演算に起因する遅延時間に基づいて設定されたタイミングでｖ（ｊ）及びｖ（ｊ’）のＸＯＲ演算を行い、節点ｊの値をＸＯＲ演算結果とする。
【００１１】
さらに、上記の演算回路設定方法において、ｍ＝ｋ−１（ｋは、３以上の自然数）におけるシンドロームを生成する演算回路に基づいてｍ＝ｋにおけるシンドロームを生成する演算回路を設定する。
【発明の効果】
【００１２】
本発明によれば、並列処理を行う上で必要となる最小限のＸＯＲ演算回数により演算処理を行うことができるので、演算処理速度の向上、演算回路の簡略化を図ることができる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態に係る符号化・復号化装置に関するブロック構成図である。
【図２】並列符号化処理に用いる演算回路の例に関する概略構成図である。
【図３】並列復号化処理に用いる演算回路の例に関する概略構成図である。
【図４】Ｒm(s)をパスカルの三角形における最初の７段を用いた場合に関する説明図である。
【図５】算出されたＲm(s)の値を示すリストである。
【図６】並列復号化処理における演算回路に関する表記例を示す説明図である。
【図７】ｍ＝３の場合の簡略表記図を作成する手順の例を示す説明図である。
【図８】ｍ＝２，３，４，５の場合の簡略表記図をまとめて示した説明図である。
【図９】ｍ＝３におけるｓiの算法及び算法に用いる値ｊの一覧を示す説明図である。
【図１０】ｍ＝５におけるｓiの算法及び算法に用いる値ｊの一覧を示す説明図である。
【発明を実施するための形態】
【００１４】
以下、本発明に係る実施形態について詳しく説明する。図１は、本実施形態に係る符号化・復号化装置に関するブロック構成図である。符号化・復号化装置１は、符号化・復号化処理部１０、符号化データ生成部１１及び誤り訂正処理部１２を備えており、各部の機能を実現する回路構成を有するＩＣにより構成することができる。
【００１５】
この例では、符号化・復号化装置１は、記憶部２０に接続されており、記憶部２０に書き込むデータの符号化を行うとともに記憶部２０から読み出されるデータの復号化を行う。なお、符号化・復号化装置１を通信装置に適用する場合には、外部の通信ネットワークと送受信する送受信部に接続する。
【００１６】
符号化・復号化処理部１０は、装置の外部から転送される入力データに対して符号化処理を行うとともに記憶部２０から読み出されるデータを復号化処理する。符号化処理では、入力データの情報ビット列に基づいてパリティビット列からなるパリティデータを生成する。生成されたパリティデータは、入力データとともに符号化データ生成部１１に入力されて、入力データの情報ビット列及びパリティデータからなる符号化データが生成されて記憶部２０に送信されて記憶される。復号化処理では、記憶部２０から読み出された符号化データのエラー位置の検出を行い、検出されたエラー位置を示すシンドロームを生成する。生成されたシンドロームは、読み出された符号化データとともに誤り訂正処理部１２に入力されて、エラー位置に対応するデータを訂正したデータを出力データとして装置の外部に転送する。
【００１７】
通信装置に適用される場合には、入力データとして送信データを符号化・復号化処理部１０に入力し、符号化データ生成部１１から出力される符号化データを送受信部に転送して通信ネットワークを介して送信する。また、受信データは、送受信部で受信した後符号化・復号化処理部１０に入力してエラー位置の検出を行った後誤り訂正処理部１２により訂正処理を行って出力される。
【００１８】
次に、符号化・復号化処理部１０における演算処理について説明する。（２m−１，２m−ｍ−１）ハミング符号の符号語ｃ、符号語ｃに対応させた情報ビット列ｂ、及び、符号語ｃを記憶した後読み出された受信語ｒをそれぞれ以下の通り表記する。
ｃ＝（ｃ1，ｃ2，…，ｃn）∈Ｆ2n，ｎ＝２m−１
ｂ＝（ｂ1，ｂ2，…，ｂk）∈Ｆ2k，ｋ＝２m−ｍ−１
ｒ＝（ｒ1，ｒ2，…，ｒn）∈Ｆ2n
そして、受信語ｒに対して復号化処理して類推される符号語Ｃを復号語とし、以下の通り表記する。
Ｃ＝（Ｃ1，Ｃ2，…，Ｃn）∈Ｆ2n
【００１９】
ハミング符号におけるシンドローム復号法では、受信語ｒに対する検査行列Ｈmによるシンドロームｓは、以下の通り表記し、
ｓ＝（ｓm，ｓm-1，…，ｓ1）∈Ｆ2m
シンドロームｓを以下の通り定める。
ｓ＝ｒＨmT
また、シンドロームｓに対して(ｓ)2を以下の通り定める。
【数３】
2014064065.tif 000006
そして、復号語Ｃを以下の通り定める。
【数４】
2014064065.tif 000007
ここで、Ｉ(i=(ｓ)2)は、ｉが(ｓ)2に等しい場合には１となり、ｉが(ｓ)2に等しくない場合には０となる。そのため(ｓ)2が０ならば受信語ｒをそのまま復号語Ｃとし、(ｓ)2が１以上ｎ以下であるときは１箇所のエラー位置を推定して訂正する復号化処理が行われる。こうしたハミング符号におけるシンドローム復号法は、通信路が定常無記憶である２元対称通信路である場合には、最尤復号となる。
【００２０】
以上説明した符号化処理及び復号化処理について、以下の検査行列Ｈ3
【数５】
2014064065.tif 000008
で定義される（７，４）ハミング符号による並列符号化処理及びシンドローム復号法による並列復号化処理を例にとり、ＸＯＲ演算回数を説明する。この例では、情報ビット列ｂ及びそれに対応する符号語ｃは以下の通りになる。
ｂ＝（ｂ1，ｂ2，ｂ3，ｂ4）∈Ｆ24
ｃ＝（ｃ1，ｃ2，ｃ3，ｃ4，ｃ5，ｃ6，ｃ7）∈Ｆ27
そして、ｃ3、ｃ5、ｃ6及びｃ7のパリティビットを以下の通り定める。
ｃ3＝ｂ1
ｃ5＝ｂ2
ｃ6＝ｂ3
ｃ7＝ｂ4
この場合、残りのパリティビットは以下の通り定められる。
【数６】
2014064065.tif 000009
こうして、４ビットの情報ビット列ｂの入力に対してパリティビットｃ1，ｃ2及びｃ4を定める符号器の一部は、それぞれ右辺の項のＸＯＲ演算を処理する回路により実現することができる。
【００２１】
図２は、並列符号化処理に用いる演算回路の例に関する概略構成図である。図２では、並列復号化処理を行う演算回路におけるＸＯＲ演算の順序を木構造で表記している。パリティビットｃiの演算処理の最後のＸＯＲ演算を根節点とし、ｃiの演算処理に用いたＸＯＲ演算を内節点とし、ｃiの演算処理に用いたｂiの集合を葉節点の集合とし、これらの節点を樹枝状に連接して枝とするツリー図で表記しており、入力側である右側から出力側である左側に枝をたどることでＸＯＲ演算の順序が設定されるようになっている。
【００２２】
図２（ａ）に示す例では、（７，４）ハミング符号における３ビットのパリティビットについて、それぞれ独立に２回のＸＯＲ演算を行っており、合計６回のＸＯＲ演算で各パリティビットを求めている。この場合、パリティビットを求める上記の演算式においてＸＯＲ演算は可換であることから、ＸＯＲ演算の順序を変えることができる。上記の演算式では、ｃ3及びｃ7、ｃ5及びｃ7並びにｃ6及びｃ7のそれぞれのＸＯＲ演算が共通している。そのため、例えば、共通するｃ6及びｃ7のＸＯＲ演算を先に処理して、その演算結果を演算式に代入すれば、ｃ2及びｃ4を３回のＸＯＲ演算で求めることができるため、３ビットのパリティビットを合計５回のＸＯＲ演算で求めることができる。図２（ｂ）は、５回のＸＯＲ演算を行う場合の演算回路の概略構成図である。
【００２３】
上記の演算式のようにパリティビットを求める２項演算において２項の対に共通のＸＯＲ演算が存在する場合は、ＸＯＲ演算の回数を減らすことができる。以下の説明では、ＸＯＲの２項演算において２項の対に存在する共通の対を「冗長な対」と称し、冗長な対に基づいてＸＯＲ演算を削減することを「冗長な対の削減」と称する。なお、上記の演算式では、ｃ1、ｃ2及びｃ4の３ビットのパリティビットを４回のＸＯＲ演算で求めることはできない。なぜなら、（ｃ3，ｃ7）、（ｃ5，ｃ7）及び（ｃ6，ｃ7）の３つの冗長な対のいずれかを削減した場合、２項の対には同じ対がなくすべて相異なっているため、冗長な対が存在しなくなってこれ以上ＸＯＲ演算の回数を削減することはできなくなる。
【００２４】
次に、（７，４）ハミング符号の並列復号化処理における、ＸＯＲ演算に起因する遅延時間について説明する。例えば、上記の検査行列Ｈ3で定まる（７，４）ハミング符号の受信語ｒ及びそれに対応するシンドロームｓ以下の通りになる。
ｒ＝（ｒ1，ｒ2，ｒ3，ｒ4，ｒ5，ｒ6，ｒ7）∈Ｆ27
ｓ＝（ｓ3，ｓ2，ｓ1）∈Ｆ23
そして、ｓ3、ｓ2及びｓ1は、以下の通り定まる。
【数７】
2014064065.tif 000010
【００２５】
図３は、並列復号化処理に用いる演算回路の例に関する概略構成図である。図３についても、図２と同様にツリー図により演算回路を表記している。上記のシンドロームビットの演算式においても冗長な対（ｒ6，ｒ7）、（ｒ5，ｒ7）及び（ｒ3，ｒ7）が存在する。そのため、冗長な対を削減することで、ＸＯＲ演算の回数を削減することができる。図３（ａ）は、冗長な対（ｒ6，ｒ7）を削減した演算回路の例を示している。なお，図３（ａ）では、ｒi＝０、ｉ＝１，２，４とすれば，上記の情報ビット列ｂに対応するパリティビットｃi、ｉ＝１，２，４を求める演算回路として使用することもできる。
【００２６】
また、図３（ｂ）は、ＸＯＲ演算に起因する遅延時間の観点から構成した演算回路の例を示している。２入力１出力となる１回のＸＯＲ演算に起因する遅延時間をｔとすると、図３（ａ）に示す例ではシンドロームビットｓiを求める演算処理に演算開始から時間３ｔを要するが、図３（ｂ）では演算開始から時間２ｔとなり、遅延時間を短縮することができる。節点及び枝で構成されるｓiに関する木構造において、同時に演算処理されるＸＯＲ演算の段数を「木の深さ」とすれば、図３（ａ）に示す場合は木の深さが３となり、図３（ｂ）に示す例では木の深さが２となる。ｓiに対応させたグラフの木の深さをｄiとすると、ｓiのＸＯＲ演算に起因する遅延時間はｄiｔとなる。そして、並列復号化処理に用いる回路構成全体の遅延時間をｄｔとすれば、ｄは以下の通り定めることができる。
ｄ＝ｍａｘ{ｄi，ｉ＝１，２，…，ｍ}
すなわち、並列復号化処理に用いる各シンドロームビットの演算回路に対応する木構造の遅延時間のうち最も長い遅延時間が回路構成全体の遅延時間となる。
【００２７】
次に、並列符号化処理及び並列復号化処理におけるＸＯＲ演算回数の下界について説明する。（２m−１，２m−ｍ−１）ハミング符号の並列符号化処理においてｍビットのパリティビットを求めるために必要とするＸＯＲ演算回数の最小値をＮm,eと表記し、（２m−１，２m−ｍ−１）ハミング符号の並列復号化処理においてｍビットのシンドロームを求めるために必要とするＸＯＲ演算回数の最小値をＮm,dと表記する。
【００２８】
（２m−１，２m−ｍ−１）ハミング符号の検査行列Ｈの各行は、それぞれ２m-1個の「１」の要素があり、符号化処理においてｍビットのパリティビットの演算処理は、各パリティビットを独立して２m-1−２回のＸＯＲ演算により行う場合、ＸＯＲ演算回数の合計は、ｍ（２m-1−２）回となる。同様に、（２m−１，２m−ｍ−１）ハミング符号の並列復号化処理においてｍビットのシンドロームの演算処理は、各シンドロームビットを独立して２m-1−１回のＸＯＲ演算により行う場合、ＸＯＲ演算回数の合計は、ｍ（２m-1−１）回となる。
【００２９】
ｍビットのパリティビット(又はシンドローム) の演算処理を各ビット毎に独立してＸＯＲ演算により行った場合に、冗長な対の削減可能なＸＯＲ演算回数をＲmと表記し、Ｒmのある上界をＲm(s)と表記する。この場合、最小値Ｎm,e及びＮm,dは、ｍ＝２，３，…に対して以下の式を満たす。
ｍ（２m-1−２）−Ｒm(s)≦Ｎm,e＜ｍ（２m-1−２）・・・・（１）
ｍ（２m-1−１）−Ｒm(s)≦Ｎm,d＜ｍ（２m-1−１）・・・・（２）
【００３０】
そして、Ｒmについては、以下の式を満たすようになる。
Ｒm≦（ｍ−４）（２m-1＋１）＋６・・・・（３）
式（３）については、次のように証明することができる。（２m−１，２m−ｍ−１）ハミング符号の検査行列Ｈのある２列の列番号を表すｊ1及びｊ2を１≦ｊ1＜ｊ2≦２m−１とし、あるｋ個の行番号を表すｉ1，ｉ2，…，ｉkを１≦ｉ1＜ｉ2＜…＜ｉk≦ｍとする。検査行列Ｈのｊ1列目とｊ2列目において、ｉ1，ｉ2，…，ｉk行目の要素がすべて「１」であれば、冗長の対に対応するｋ回のＸＯＲ演算をまとめて１回のＸＯＲ演算で行うことで、ｋ−１回のＸＯＲ演算が削除可能となる。
【００３１】
（２m−１，２m−ｍ−１）ハミング符号の検査行列Ｈは、すべての非零のｍ次元ベクトルを列として並べたｍ行２m−１列の行列である。検査行列Ｈの各列はすべて異なっており、「１」の要素がｋ1個であるｊ1列目と「１」の要素がｋ2個であるｊ2列目に対応するＸＯＲ演算をまとめて１回のＸＯＲ演算により行うことで、ｋ1≠ｋ2である場合にはｍｉｎ{ｋ1，ｋ2}−１回までＸＯＲ演算の回数を削除可能であり、ｋ1＝ｋ2である場合にはｋ1−２回までＸＯＲ演算の回数を削除可能である。したがって、以下の関係式が導かれる。
【数８】
2014064065.tif 000011
以上のとおり式（３）が証明される。そして、式（３）を用いて式（１）及び式（２）は、以下の通り表記でき、ＸＯＲ演算回数の下界が評価できる。
２m+1−３ｍ−２≦Ｎm,e・・・・（６）
２m+1−２ｍ−２≦Ｎm,d・・・・（７）
また、Ｒm(s)については、以後式（３）により以下の通り表記する。
Ｒm(s)＝（ｍ−４）（２m-1＋１）＋６・・・・（８）
図４は、Ｒm(s)をパスカルの三角形における最初の７段を用いた場合に関する説明図である。この場合、Ｒ2(s)＝０となり、ｍ≧３では、以下の漸化式を満たす。
Ｒm(s)＝２Ｒm-1(s)＋２m-1−ｍ・・・・（９）
さらに、Ｒm(s)を係数とする以下の母関数
【数９】
2014064065.tif 000012
は、式（５）により以下の式で与えられる（R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989）。
【数１０】
2014064065.tif 000013
ｍ＝２，３，…，１２の場合のＲm(s)の値を図５に示す。
【００３２】
Ｒn+3(s)，ｎ＝０，１，２，…は、次の２つのパターンで生成される数列に等しいことが知られている（N. J. A. Sloane, On-line Encyclopedia of Integer Sequences）。一つ目のパターンは、１からｎ＋２までの整数の集合Ａn＝{１，２，…，ｎ＋２}における空集合を除くすべての部分集合の径の和に等しい。ここで、集合Ａの径は、集合Ａに属する最大値から集合Ａに属する最小値を引いた値として定義される。例えば、ｎ＝０ならばＡ0＝{１，２}であり、空集合を除くすべての部分集合{１}，{２}，{１，２}の径はそれぞれ０，０，１となってその合計は１となる。同様にｎ＝１ならばＡ1＝{１，２，３}であり，空集合を除くすべての部分集合の径の和は６となる。
【００３３】
二つ目のパターンは、以下の通り設定された、２のべき乗の部分和の列Ｂnに対する畳み込みと等しい。
【数１１】
2014064065.tif 000014
たとえば、Ｂ0＝（１）、Ｂ1＝（１，３）、Ｂ2＝（１，３，７）に対して、畳み込みは、それぞれ以下の通りとなる。
Ｂ0；１
Ｂ1；１×３＋３×１＝６
Ｂ2；１×７＋３×３＋７×１＝２３
【００３４】
次に、上述のように求められたＸＯＲ演算回数の下界を下限とする回路構成について説明する。（２m−１，２m−ｍ−１）ハミング符号を用いた並列符号化処理及び並列復号化処理におけるＸＯＲ演算回数の下限は、式（６）及び式（７）により以下の通り設定される。
Ｎm,e＝２m+1−３ｍ−２＝２（２m−ｍ−１）−ｍ・・・・（１０）
Ｎm,d＝２m+1−２ｍ−２＝２（２m−ｍ−１）・・・・（１１）
ここでは、（２m−１，２m−ｍ−１）ハミング符号の検査行列として上記の検査行列Ｈmを用い、２入力１出力となる１回のＸＯＲ演算に起因する遅延時間をｔとして、ＸＯＲ演算回数を下限に設定するとともに遅延時間（ｍ−１）ｔとなる回路構成について述べる。まず、並列復号化処理における遅延時間が（ｍ−１）ｔとなる回路構成について、ｍ＝２から順に再帰的にｍ＝２，３，…を考える。シンドロームsにおけるsi，ｉ＝１，２，…，ｍの演算開始時刻を０とする。ｍ＝２の場合、s1及びs2は以下の通り設定される。
【数１２】
2014064065.tif 000015
【００３５】
図６は、並列復号化処理における演算回路に関する表記例を示す説明図である。図６（ａ）では、s1及びs2を求める演算回路を図３と同様の表記方法で記載している。以後の説明を容易にするために、こうした演算回路の簡略表記の方法を次のように定める。簡略表記では、まず、以下の式を満たすｊを設定する。
【数１３】
2014064065.tif 000016
そして、設定されたｊに関する二進数表記（ｂm-1ｂm-2…ｂ0）2を用いてｒjの代わりに単にｂm-1ｂm-2…ｂ0と表記する。そして、以下の規則１から規則４に従って表記する。
＜規則１＞
左端の列に上から順にs1からsmを並べる。
＜規則２＞
ｂm-1ｂm-2…ｂ0，ｂi ∈{０，１}について以下の値を求め、
【数１４】
2014064065.tif 000017
この値が小さい値１から大きい値ｍの順に右から左に列として分類し、各列ではｊ＝（ｂm-1ｂm-2…ｂ0）2の小さい値から大きい値の順に上から下に配置する。
＜規則３＞
規則２で作成した配置図において、ｂm-1ｂm-2…ｂ0を値０か値１の１ビットを保持する節点とし、節点（ｂm-1ｂm-2…ｂ0）2又は節点ｊ, ｊ＝（ｂm-1ｂm-2…ｂ0）2と表記する。節点ｊの保持する値をｖ（ｊ）とし、時刻０での値ｖ（ｊ）を復号化処理ではｒjとする。なお，符号化処理では時刻０での値ｖ（ｊ）は、ｊ＝２i-1，ｉ＝１，２，…，ｍを除きｖ（ｊ）＝ｃjとし、ｊ＝２i-1，ｉ＝２，…，ｍではｖ（ｊ）＝ｃj+1とし、ｖ（１）＝ｃ3とする。
＜規則４＞
ｊ＜ｊ’を満たす節点ｊと節点ｊ’との間に、（ｉ1）δ（又は（ｉ1，…，ｉk）δ）とラベル付けされた線がある場合には、時刻（δ−１）t〜δｔの間にｖ（ｊ）及びｖ（ｊ’）のＸＯＲ演算を行い、時刻δｔでの節点ｊの値を以下のＸＯＲ演算結果とする。
【数１５】
2014064065.tif 000018
この場合、ラベル（ｉ1）δ（又は（ｉ1，…，ｉk）δ）は時刻（δ−１）t〜δｔの間に行われたＸＯＲ演算結果がｓi1（又は複数のｓi1，…，ｓik）を求めるために用いられることを意味する。以後、ラベル（ｉ1）δ（又は（ｉ1，…，ｉk）δ）の表記において、ｉkをラベルにおけるｋ番目のインデックス又は単にインデックスと称し、δをラベルにおける下付の時刻δと称する。
【００３６】
ｍ＝ｋ−１におけるｓ1，ｓ2，…，ｓk-1を求める演算回路を表す簡略表記を用いてｍ＝ｋにおけるｓ1，ｓ2，…，ｓkを求める回路を表す簡略表記を定める手順を次に示す。なお、簡略表記において、時刻（ｍ−１）ｔに節点ｊ, ｊ＝２i-1，ｉ＝１，２，…，ｍが保持する値がｓiの値となる。
＜手順１＞
次の２つの図を上記規則１及び２に従って１つの図にまとめる。
（１図）ｍ＝ｋ−１での簡略表記で各節点（ｂk-2ｂk-3…ｂ0）2の先頭ビットに０を追加した節点（０ｂk-2ｂk-3…ｂ0）2に変更した図
（２図）ｍ＝ｋ−１での簡略表記で各節点（ｂk-2ｂk-3…ｂ0）2の先頭ビットに１を追加した節点（１ｂk-2ｂk-3…ｂ0）2に変更し、ｓ1，ｓ2，…，ｓk-1を除いた図
＜手順２＞
手順１で作成された図において、節点２i-1と節点２i-1＋２k-1とを結ぶ線を追加し、その線にラベルとして（ｉ）k-1を付与する処理を、ｉ＝１，…，ｋ−１としてｋ−１回行う。
＜手順３＞
手順２で作成された図において、ｓkと節点２k-1を追加する。
＜手順４＞
手順３で作成された図において、次の（手順４−１）をα＝１，…，ｋ−１としてｋ−１回行う。
（手順４−１）
節点２k-1と節点ｊ＋２α-1とを結ぶ線を追加する。追加した線のラベルを（ｋ）αに更新する。αが２以上であれば、（手順４−２）によりラベルにインデックスｋの追加を再帰的に繰り返す。
（手順４−２）
更新したラベルにおける下付の時刻をβとする。更新したラベル（ｋ）β，β＝α又はｋを含むすべてのラベル（・，ｋ）βを付与された線で結ばれた右側の節点について、その節点から出ている線のラベルにおける下付の時刻γがγ＜βを満たすすべてのラベル（・）γに対して、インデックスｋを追加して（・，ｋ）γとする処理を再帰的に繰り返す。
【００３７】
図６（ｂ）は、以上説明した手順により簡略表記した例を示している。ｍ＝２の場合にｓ1及びｓ2を求める図６（ａ）と同様の演算回路を簡略表記している。図６（ｂ）に示すｍ＝２の場合の簡略表記図を用いて，ｍ＝３の場合の簡略表記図を作成する手順の例を図７に示す。図７では、線のラベルが１つ前の手順におけるラベルと同じ場合にはその表記を省略している。手順１では、０を追加した節点（００１）、（０１０）及び（０１１）に変更した図及び１を追加した節点（１０１）、（１１０）及び（１１１）に変更した図を１つの図にまとめて併記している。手順２では、節点（００１）と（１０１）とを結ぶ線を追加してラベル（１）2を付与し、節点（０１０）と（１１０）とを結ぶ線を追加してラベル（２）2を付与している。手順３では、ｓ3及び節点（１００）を追加し、手順４−１では、節点（１００）と（１０１）とを結ぶ線を追加してラベル（３）1を付与し、節点（１００）と（１１０）とを結ぶ線を追加してラベル（３）2を付与している。手順４−２では、節点（１１０）と（１１１）とを結ぶ線のラベルを（２，３）1に更新している。この場合、ＸＯＲ演算に起因する遅延時間は２ｔとなる。
【００３８】
図８は、ｍ＝２，３，４，５の場合の簡略表記図をまとめて示している。図８では、ｍ＝４，５の図では、インデックスの要素数が１個の場合にラベル表示を省略している。図８に示すｍ＝３の簡略表記図よりｍ＝３におけるｓiの算法を導き出すことができる。図９は、ｍ＝３におけるｓiの算法（図９（ａ））及び算法に用いる値ｊの一覧（図９（ｂ））を示す。値ｊは、以下の通り設定される。
【数１６】
2014064065.tif 000019
図１０は、ｍ＝５におけるｓiの算法（図１０（ａ））及び算法に用いる値ｊの一覧（図１０（ｂ））を示す。値ｊは、図９に示す例と同様に設定される。図９（ｂ）及び図１０（ｂ）では、同じｗ毎に区切りの横線を追加している。
【００３９】
図９に示す算法及びそれに用いる値ｊに基づいて図３（ｂ）に示す演算回路を得ることができる。すなわち、ｍ＝３の場合に手順１から手順４を適用することで、図３（ｂ）に示す演算回路が設定される。手順２及び手順４−１により，簡略表記において節点ｊの右からｋ, ｋ≦ｍ−１本の線が出ている場合には、各線の左側の節点ｊ’に対応する値ｊ’の小さい順（図８では、ｋ本の線の上からの順) に時刻０〜ｔ，ｔ〜２ｔ，…，（ｋ−１）ｔ〜ｋｔ毎にその線に対応するＸＯＲ演算が行われる。一般に、２以上の自然数ｍの場合に手順１〜手順４を適用することで、並列復号化処理におけるｓ＝（ｓ1，ｓ2，…，ｓm）＝ｒＨmTを満たすｓi，ｉ＝１，２，…，ｍのある算法が定まり、（２m−１，２m−ｍ−１）ハミング符号の並列復号化処理を行う演算回路を得ることができる。例えば、図８に示すｍ＝５の簡略表記に基づいて、図１０に示すｍ＝５におけるｓiの算法及び算法に用いる値が得られる。
【００４０】
なお、ｍにおける算法に用いる値ｊが設定されていれば、ｍs≦ｍにおける値ｊを次の手順Ａにより求めることができる。
【数１７】
2014064065.tif 000020
手順Ａによりｍ＝５における値ｊのリスト（図１０（ｂ））からｍ＝２，３，４における値ｊのリストが得られる。そのため、ｍ＝ｋの簡略表記に対応する演算回路を用いて、ｍがｋより小さい演算回路として利用することが可能となり、演算回路の共通化や演算回路の変更を容易に行うことができ、演算回路のコストダウン及びフレキシビリティを高めることができる。
【００４１】
手順１〜手順４のアルゴリズムにより得られる簡略表記においてラベルのインデックスの要素数がｋ，ｋ≧２個のものは冗長な対のＸＯＲ演算に対応しており、対応するｋ回のＸＯＲ演算をまとめて１回のＸＯＲ演算で行うことで、ｋ−１回のＸＯＲ演算を削除可能である。ｍにおけるｓi，ｉ＝１，２，…，ｍのある算法を与える手順１〜手順４のアルゴリズムにより得られる削減可能なＸＯＲ演算の回数Ｒm(a)は、図８に基づいて以下の通りとなる。
Ｒ2(a)＝０
Ｒ3(a)＝１
Ｒ4(a)＝６
Ｒ5(a)＝２３
【００４２】
検査行列Ｈmにおいて各行における要素が１の個数は２m-1個であり、ｓiを独立して演算する場合に用いられるＸＯＲ演算の回数は２m-1−１回である。一方、ｍにおけるｓi，ｉ＝１，２，…，ｍの算法を与える手順１〜手順４では、手順４−１においてラベル（ｍ）α，α＝１，２，…，ｍ−１が付与されて、インデックスｍが追加される回数はｍ−１回であり、手順４−２においてインデックスｍが追加される回数をＳmとすると、手順１〜手順４における再帰構造からＳ2＝０であり、３≦ｎ≦ｍにおいて以下の漸化式を満たす。
Ｓn＝２Ｓn-1＋ｎ−２
この漸化式より、ｍ≧２に対して、Ｓm＝２m-1−ｍであり、ｍにおける簡略表記のラベルのインデックスｍに基づく削除可能なＸＯＲ演算の回数はＳm回であることがわかる。また、ｍにおけるｓi，ｉ＝１，２，…，ｍの算法を与える手順１より、ｍにおける簡略表記から、ラベルのインデックスｍに基づくもの以外で削除可能なＸＯＲ演算の回数は２Ｒm-1(a)回であることがわかる。そのため、ｍ≧３において
Ｒm(a)＝２Ｒm-1(a)＋Ｓm＝２Ｒm-1(a)＋２m-1−ｍ・・・・（１２）
である。Ｒ2(a)＝Ｒ2(s)＝０、式（９）及び式（１２）により、ｍ≧２において
Ｒm(a)＝Ｒm(s)＝（ｍ−４）（２m-1＋１）＋６
が成り立つ。
【００４３】
以上のことより、（２m−１，２m−ｍ−１）ハミング符号の並列復号化処理においてｓi，ｉ＝１，２，…，ｍを求めるＸＯＲ演算回数が式（１１）を満たすとともに遅延時間（ｍ−１）ｔである演算回路を構成することができる。（２m−１，２m−ｍ−１）ハミング符号の並列符号化処理においてｍビットのパリティビット
【数１８】
2014064065.tif 000021
を求める演算回路の簡易表記は、ｍにおけるｓi，ｉ＝１，２，…，ｍの算法を与える手順１〜手順４で得られる簡易表記において、ｓiを［数１８］に示すパリティビットに変更し、節点１及び節点３を結ぶ線並びにｉ＝１，２，…，ｍでの節点２i-1及び節点２i-1＋１を結ぶ線とそれら線のラベル（ｉ’）1，ｉ’＝１，２，…，ｍを削除することで得られる。こうして得られた簡易表記から［数１８］に示すｍビットのパリティビットを求める演算回路が定まり，そのＸＯＲ演算回数は式（１０）を満たす。
【００４４】
手順１〜手順４で定まる（２m−１，２m−ｍ−１）ハミング符号の並列復号化処理でシンドロームを求める演算回路は、２≦ｍs≦ｍを満たす（２ms−１，２ms−ｍs−１）ハミング符号の並列符号化処理でのパリティビットを求める演算回路や並列復号化処理でのシンドロームを求める演算回路に利用可能である。さらに、これらの演算回路は、１≦ｋs≦２ms−ｍs−１，２≦ｍs≦ｍを満たす（ｋs＋ｍs，ｋs）ハミング符号の並列符号化処理でのパリティビットを求める演算回路や並列復号化処理でのシンドロームを求める演算回路に利用可能である。検査行列がＨmでなく一般の検査行列Ｈ場合には、列の置換に対して演算回路への入力の配置をＨの列に合わせて並び直せば、上述した手順を適用できる。そのため、検査行列がハミング符号の検査行列に分解できるＢＣＨ符号のシンドロームの演算にも適用可能である。
【００４５】
手順１〜手順４で得られるｍにおける簡易表記は、ｍ個の集合のベン図と関連付けることができ、集合{１，２，…，ｍ}の空集合を除いたべき集合での包含の関係によるハッセ図においてある規則に従って線を除いた図と関連付けることもできる。
【符号の説明】
【００４６】
１・・・符号化・復号化装置、１０・・・符号化・復号化処理部、１１・・・符号化データ生成部、１２・・・誤り訂正処理部、２０・・・記憶部
【先行技術文献】
【特許文献】
【００４７】
【特許文献１】米国特許第７，２９３，２２２号明細書
【非特許文献】
【００４８】
【非特許文献１】F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977
【図１】
2014064065.tif 000023
【図２】
2014064065.tif 000024
【図３】
2014064065.tif 000025
【図４】
2014064065.tif 000026
【図５】
2014064065.tif 000027
【図６】
2014064065.tif 000028
【図７】
2014064065.tif 000029
【図８】
2014064065.tif 000030
【図９】
2014064065.tif 000031
【図１０】
2014064065.tif 000032