TOP > 国内特許検索 > 演算回路設定方法 > 明細書

明細書 :演算回路設定方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5999634号 (P5999634)
公開番号 特開2014-064065 (P2014-064065A)
登録日 平成28年9月9日(2016.9.9)
発行日 平成28年9月28日(2016.9.28)
公開日 平成26年4月10日(2014.4.10)
発明の名称または考案の名称 演算回路設定方法
国際特許分類 H03M  13/19        (2006.01)
FI H03M 13/19
請求項の数または発明の数 2
全頁数 16
出願番号 特願2012-206395 (P2012-206395)
出願日 平成24年9月19日(2012.9.19)
審査請求日 平成27年7月16日(2015.7.16)
特許権者または実用新案権者 【識別番号】504145320
【氏名又は名称】国立大学法人福井大学
発明者または考案者 【氏名】岩田 賢一
【氏名】福間 慎治
【氏名】大島 怜也
個別代理人の代理人 【識別番号】100111855、【弁理士】、【氏名又は名称】川崎 好昭
審査官 【審査官】岡 裕之
参考文献・文献 米国特許出願公開第2007/0277085(US,A1)
大島 怜也 他,ハミング符号の並列符号器と並列復号器におけるXOR演算回数の最適化,電子情報通信学会技術研究報告,2012年 9月20日,Vol.112, No.215,pp.25-30,IT2012-35
調査した分野 H03M 13/19
IEEE Xplore
CiNii
特許請求の範囲 【請求項1】
符号長2m-1及び情報ビット数2m-m-1の2元ハミング符号の受信語rj,j=1,2,…,2m-1に対してXOR演算を複数回行ってエラー位置を検出するシンドロームsi,i=1,2,…,mを生成する復号化処理の演算回路設定方法であって、以下の規則1から規則4に基づいて表記された順序でXOR演算を行うように演算回路を構成する演算回路設定方法。
<規則1>
左端の列に上から順にs1からsmを並べる。
<規則2>
jの二進表記であるbm-1m-2…b0,bi ∈{0,1}について以下の値を求め、
【数14】
JP0005999634B2_000021t.gif
この値が同じものを小さい値1から大きい値mの順に左から右に列として配置し、各列ではjの小さい値から大きい値の順に上から下に配置する。
<規則3>
規則2で作成した配置図において、bm-1m-2…b0を値0か値1の1ビットを保持する節点jとし、各節点jの保持する値をv(j)として、演算開始時刻での値v(j)をrjとする。左端の列に配置された節点j=2i-1をsiに対応させ、siを求めるrjのXOR演算の演算式に基づいてrjに対応する節点j同士を線で結ぶ。
<規則4>
j<j’を満たす節点jと節点j’との間を結ぶ線がある場合には、演算開始時刻から1回のXOR演算に起因する遅延時間に基づいて設定されたタイミングでv(j)及びv(j’)のXOR演算を行い、節点jの値をXOR演算結果とする。
【請求項2】
m=k-1(kは、3以上の自然数)におけるシンドロームを生成する演算回路に基づいてm=kにおけるシンドロームを生成する演算回路を設定する請求項1に記載された演算回路設定方法。
発明の詳細な説明 【技術分野】
【0001】
本発明は、記憶処理装置、通信処理装置等のデータ処理装置に用いられる符号化・復号化装置及び符号化・復号化処理を行う演算回路の設定方法に関する。
【背景技術】
【0002】
記憶処理装置や通信処理装置等のデータ処理装置は、一般的にデータの誤り検出及び訂正を行う誤り訂正機能を備えている。誤り訂正機能としては、1ビット訂正可能なハミング符号(短縮化ハミング符号語)を用いた符号化・復号化方式が提案されている。こうした符号化・復号化方式では、情報ビット列(情報ベクトル)及び生成行列に基づいてハミング符号を生成する符号化処理を実行するとともに、生成行列に対応する検査行列(パリティ検査行列)及びハミング符号に基づいてエラー位置を検出する復号化処理を実行する。
【0003】
情報ビット列は、記憶処理装置では記録媒体に記憶される入力データが該当し、通信処理装置では送信データが該当する。そして、ハミング符号は、情報ビット列及びパリティビット列(パリティデータ)を組み合せて構成される。復号化処理では、記憶処理装置では記録媒体から読み出されるハミング符号からなる出力データのエラー位置を検出し、通信処理装置では受信データのエラー位置を検出して、そのエラー位置を示すデータ(以下「シンドローム(syndrome)」と称する)を生成する。エラー訂正処理では、復号化処理により検出されたエラー位置のエラービットを訂正してデータ出力処理を行う。
【0004】
簡単な誤り訂正符号の1つである2元ハミング符号を用いた符号化・復号化装置における排他的論理和(XOR)の演算処理について考える。2元体をF2と表記し、その元を0と1で表す。2元体での加法については、以下の通り表記する。
【数1】
JP0005999634B2_000002t.gif
なお、この表記において、2項間の記号は排他的論理和(XOR)である。
2以上の任意の整数mに対して、F2={0,1}上のすべての非零のm次元ベクトルを列として並べたm行2m-1列の行列を検査行列として定義される符号は符号長2m-1、情報ビット数2m-m-1の2元ハミング符号であり、(2m-1,2m-m-1)ハミング符号と表記する。(2m-1,2m-m-1)ハミング符号を定める検査行列をHと表記する。特に、検査行列のj列目hjT
jT=(h1,j,h2,j,…,hi,j,…,hm,j)∈F2m
とし、
【数2】
JP0005999634B2_000003t.gif
を満たすようにhjを定めた検査行列をHmと表記する。ただし、hTはhの転置を表す。(2m-1,2m-m-1)ハミング符号は最小距離が3であり、ハミング限界を等号で満たす完全符号である(非特許文献1参照)。
【0005】
そして、(2m-1,2m-m-1)ハミング符号における検査行列Hでの列の並べ方は任意であり、巡回符号である(2m-1,2m-m-1)ハミング符号はシフトレジスタを用いたm段符号器や2m-m-1段符号器及び巡回ハミング符号の復号器を用いた符号化・復号化装置によって実現することができる(非特許文献1参照)。
【0006】
これに対して、符号器及び復号器の高速化を図る方法として、符号語や復号結果の各ビットを並列に出力する並列符号器及び並列復号器が提案されている(特許文献1参照)。
【発明の概要】
【発明が解決しようとする課題】
【0007】
こうした並列符号器及び並列復号器については、演算処理速度が高速化するものの演算回路が複雑化するため実用化に至っていないのが現状である。演算処理では2入力1出力のXOR演算を組み合せて処理するのが一般的であるが、こうしたXOR演算の回数は、演算処理速度の向上、演算回路の構成等に直接影響を与えるため、安定した並列処理を行う上で必要となる最適な演算回数の設定が求められている。
【0008】
そこで、本発明は、並列処理を行う上で必要となる最小限のXOR演算回数により演算処理を行うことができる符号化・復号化装置を提供することを目的とする。
【課題を解決するための手段】
【0010】
本発明に係る演算回路設定方法は、符号長2m-1及び情報ビット数2m-m-1の2元ハミング符号の受信語rj,j=1,2,…,2m-1に対してXOR演算を複数回行ってエラー位置を検出するシンドロームsi,i=1,2,…,mを生成する復号化処理の演算回路設定方法であって、以下の規則1から規則4に基づいて表記された順序でXOR演算を行うように演算回路を構成する。
<規則1>
左端の列に上から順にs1からsmを並べる。
<規則2>
jの二進表記であるbm-1m-2…b0,bi ∈{0,1}について以下の値を求め、
【数14】
JP0005999634B2_000004t.gif
この値が同じものを小さい値1から大きい値mの順に左から右に列として配置し、各列ではjの小さい値から大きい値の順に上から下に配置する。
<規則3>
規則2で作成した配置図において、bm-1m-2…b0を値0か値1の1ビットを保持する節点jとし、各節点jの保持する値をv(j)として、演算開始時刻での値v(j)をrjとする。左端の列に配置された節点j=2i-1をsiに対応させ、siを求めるrjのXOR演算の演算式に基づいてrjに対応する節点j同士を線で結ぶ。
<規則4>
j<j’を満たす節点jと節点j’との間を結ぶ線がある場合には、演算開始時刻から1回のXOR演算に起因する遅延時間に基づいて設定されたタイミングでv(j)及びv(j’)のXOR演算を行い、節点jの値をXOR演算結果とする。
【0011】
さらに、上記の演算回路設定方法において、m=k-1(kは、3以上の自然数)におけるシンドロームを生成する演算回路に基づいてm=kにおけるシンドロームを生成する演算回路を設定する。
【発明の効果】
【0012】
本発明によれば、並列処理を行う上で必要となる最小限のXOR演算回数により演算処理を行うことができるので、演算処理速度の向上、演算回路の簡略化を図ることができる。
【図面の簡単な説明】
【0013】
【図1】本実施形態に係る符号化・復号化装置に関するブロック構成図である。
【図2】並列符号化処理に用いる演算回路の例に関する概略構成図である。
【図3】並列復号化処理に用いる演算回路の例に関する概略構成図である。
【図4】Rm(s)をパスカルの三角形における最初の7段を用いた場合に関する説明図である。
【図5】算出されたRm(s)の値を示すリストである。
【図6】並列復号化処理における演算回路に関する表記例を示す説明図である。
【図7】m=3の場合の簡略表記図を作成する手順の例を示す説明図である。
【図8】m=2,3,4,5の場合の簡略表記図をまとめて示した説明図である。
【図9】m=3におけるsiの算法及び算法に用いる値jの一覧を示す説明図である。
【図10】m=5におけるsiの算法及び算法に用いる値jの一覧を示す説明図である。
【発明を実施するための形態】
【0014】
以下、本発明に係る実施形態について詳しく説明する。図1は、本実施形態に係る符号化・復号化装置に関するブロック構成図である。符号化・復号化装置1は、符号化・復号化処理部10、符号化データ生成部11及び誤り訂正処理部12を備えており、各部の機能を実現する回路構成を有するICにより構成することができる。

【0015】
この例では、符号化・復号化装置1は、記憶部20に接続されており、記憶部20に書き込むデータの符号化を行うとともに記憶部20から読み出されるデータの復号化を行う。なお、符号化・復号化装置1を通信装置に適用する場合には、外部の通信ネットワークと送受信する送受信部に接続する。

【0016】
符号化・復号化処理部10は、装置の外部から転送される入力データに対して符号化処理を行うとともに記憶部20から読み出されるデータを復号化処理する。符号化処理では、入力データの情報ビット列に基づいてパリティビット列からなるパリティデータを生成する。生成されたパリティデータは、入力データとともに符号化データ生成部11に入力されて、入力データの情報ビット列及びパリティデータからなる符号化データが生成されて記憶部20に送信されて記憶される。復号化処理では、記憶部20から読み出された符号化データのエラー位置の検出を行い、検出されたエラー位置を示すシンドロームを生成する。生成されたシンドロームは、読み出された符号化データとともに誤り訂正処理部12に入力されて、エラー位置に対応するデータを訂正したデータを出力データとして装置の外部に転送する。

【0017】
通信装置に適用される場合には、入力データとして送信データを符号化・復号化処理部10に入力し、符号化データ生成部11から出力される符号化データを送受信部に転送して通信ネットワークを介して送信する。また、受信データは、送受信部で受信した後符号化・復号化処理部10に入力してエラー位置の検出を行った後誤り訂正処理部12により訂正処理を行って出力される。

【0018】
次に、符号化・復号化処理部10における演算処理について説明する。(2m-1,2m-m-1)ハミング符号の符号語c、符号語cに対応させた情報ビット列b、及び、符号語cを記憶した後読み出された受信語rをそれぞれ以下の通り表記する。
c=(c1,c2,…,cn)∈F2n,n=2m-1
b=(b1,b2,…,bk)∈F2k,k=2m-m-1
r=(r1,r2,…,rn)∈F2n
そして、受信語rに対して復号化処理して類推される符号語Cを復号語とし、以下の通り表記する。
C=(C1,C2,…,Cn)∈F2n

【0019】
ハミング符号におけるシンドローム復号法では、受信語rに対する検査行列Hmによるシンドロームsは、以下の通り表記し、
s=(sm,sm-1,…,s1)∈F2m
シンドロームsを以下の通り定める。
s=rHmT
また、シンドロームsに対して(s)2を以下の通り定める。
【数3】
JP0005999634B2_000005t.gif
そして、復号語Cを以下の通り定める。
【数4】
JP0005999634B2_000006t.gif
ここで、I(i=(s)2)は、iが(s)2に等しい場合には1となり、iが(s)2に等しくない場合には0となる。そのため(s)2が0ならば受信語rをそのまま復号語Cとし、(s)2が1以上n以下であるときは1箇所のエラー位置を推定して訂正する復号化処理が行われる。こうしたハミング符号におけるシンドローム復号法は、通信路が定常無記憶である2元対称通信路である場合には、最尤復号となる。

【0020】
以上説明した符号化処理及び復号化処理について、以下の検査行列H3
【数5】
JP0005999634B2_000007t.gif
で定義される(7,4)ハミング符号による並列符号化処理及びシンドローム復号法による並列復号化処理を例にとり、XOR演算回数を説明する。この例では、情報ビット列b及びそれに対応する符号語cは以下の通りになる。
b=(b1,b2,b3,b4)∈F24
c=(c1,c2,c3,c4,c5,c6,c7)∈F27
そして、c3、c5、c6及びc7のパリティビットを以下の通り定める。
3=b1
5=b2
6=b3
7=b4
この場合、残りのパリティビットは以下の通り定められる。
【数6】
JP0005999634B2_000008t.gif
こうして、4ビットの情報ビット列bの入力に対してパリティビットc1,c2及びc4を定める符号器の一部は、それぞれ右辺の項のXOR演算を処理する回路により実現することができる。

【0021】
図2は、並列符号化処理に用いる演算回路の例に関する概略構成図である。図2では、並列復号化処理を行う演算回路におけるXOR演算の順序を木構造で表記している。パリティビットciの演算処理の最後のXOR演算を根節点とし、ciの演算処理に用いたXOR演算を内節点とし、ciの演算処理に用いたbiの集合を葉節点の集合とし、これらの節点を樹枝状に連接して枝とするツリー図で表記しており、入力側である右側から出力側である左側に枝をたどることでXOR演算の順序が設定されるようになっている。

【0022】
図2(a)に示す例では、(7,4)ハミング符号における3ビットのパリティビットについて、それぞれ独立に2回のXOR演算を行っており、合計6回のXOR演算で各パリティビットを求めている。この場合、パリティビットを求める上記の演算式においてXOR演算は可換であることから、XOR演算の順序を変えることができる。上記の演算式では、c3及びc7、c5及びc7並びにc6及びc7のそれぞれのXOR演算が共通している。そのため、例えば、共通するc6及びc7のXOR演算を先に処理して、その演算結果を演算式に代入すれば、c2及びc4を3回のXOR演算で求めることができるため、3ビットのパリティビットを合計5回のXOR演算で求めることができる。図2(b)は、5回のXOR演算を行う場合の演算回路の概略構成図である。

【0023】
上記の演算式のようにパリティビットを求める2項演算において2項の対に共通のXOR演算が存在する場合は、XOR演算の回数を減らすことができる。以下の説明では、XORの2項演算において2項の対に存在する共通の対を「冗長な対」と称し、冗長な対に基づいてXOR演算を削減することを「冗長な対の削減」と称する。なお、上記の演算式では、c1、c2及びc4の3ビットのパリティビットを4回のXOR演算で求めることはできない。なぜなら、(c3,c7)、(c5,c7)及び(c6,c7)の3つの冗長な対のいずれかを削減した場合、2項の対には同じ対がなくすべて相異なっているため、冗長な対が存在しなくなってこれ以上XOR演算の回数を削減することはできなくなる。

【0024】
次に、(7,4)ハミング符号の並列復号化処理における、XOR演算に起因する遅延時間について説明する。例えば、上記の検査行列H3で定まる(7,4)ハミング符号の受信語r及びそれに対応するシンドロームs以下の通りになる。
r=(r1,r2,r3,r4,r5,r6,r7)∈F27
s=(s3,s2,s1)∈F23
そして、s3、s2及びs1は、以下の通り定まる。
【数7】
JP0005999634B2_000009t.gif

【0025】
図3は、並列復号化処理に用いる演算回路の例に関する概略構成図である。図3についても、図2と同様にツリー図により演算回路を表記している。上記のシンドロームビットの演算式においても冗長な対(r6,r7)、(r5,r7)及び(r3,r7)が存在する。そのため、冗長な対を削減することで、XOR演算の回数を削減することができる。図3(a)は、冗長な対(r6,r7)を削減した演算回路の例を示している。なお,図3(a)では、ri=0、i=1,2,4とすれば,上記の情報ビット列bに対応するパリティビットci、i=1,2,4を求める演算回路として使用することもできる。

【0026】
また、図3(b)は、XOR演算に起因する遅延時間の観点から構成した演算回路の例を示している。2入力1出力となる1回のXOR演算に起因する遅延時間をtとすると、図3(a)に示す例ではシンドロームビットsiを求める演算処理に演算開始から時間3tを要するが、図3(b)では演算開始から時間2tとなり、遅延時間を短縮することができる。節点及び枝で構成されるsiに関する木構造において、同時に演算処理されるXOR演算の段数を「木の深さ」とすれば、図3(a)に示す場合は木の深さが3となり、図3(b)に示す例では木の深さが2となる。siに対応させたグラフの木の深さをdiとすると、siのXOR演算に起因する遅延時間はditとなる。そして、並列復号化処理に用いる回路構成全体の遅延時間をdtとすれば、dは以下の通り定めることができる。
d=max{di,i=1,2,…,m}
すなわち、並列復号化処理に用いる各シンドロームビットの演算回路に対応する木構造の遅延時間のうち最も長い遅延時間が回路構成全体の遅延時間となる。

【0027】
次に、並列符号化処理及び並列復号化処理におけるXOR演算回数の下界について説明する。(2m-1,2m-m-1)ハミング符号の並列符号化処理においてmビットのパリティビットを求めるために必要とするXOR演算回数の最小値をNm,eと表記し、(2m-1,2m-m-1)ハミング符号の並列復号化処理においてmビットのシンドロームを求めるために必要とするXOR演算回数の最小値をNm,dと表記する。

【0028】
(2m-1,2m-m-1)ハミング符号の検査行列Hの各行は、それぞれ2m-1個の「1」の要素があり、符号化処理においてmビットのパリティビットの演算処理は、各パリティビットを独立して2m-1-2回のXOR演算により行う場合、XOR演算回数の合計は、m(2m-1-2)回となる。同様に、(2m-1,2m-m-1)ハミング符号の並列復号化処理においてmビットのシンドロームの演算処理は、各シンドロームビットを独立して2m-1-1回のXOR演算により行う場合、XOR演算回数の合計は、m(2m-1-1)回となる。

【0029】
mビットのパリティビット(又はシンドローム) の演算処理を各ビット毎に独立してXOR演算により行った場合に、冗長な対の削減可能なXOR演算回数をRmと表記し、Rmのある上界をRm(s)と表記する。この場合、最小値Nm,e及びNm,dは、m=2,3,…に対して以下の式を満たす。
m(2m-1-2)-Rm(s)≦Nm,e<m(2m-1-2)・・・・(1)
m(2m-1-1)-Rm(s)≦Nm,d<m(2m-1-1)・・・・(2)

【0030】
そして、Rmについては、以下の式を満たすようになる。
m≦(m-4)(2m-1+1)+6・・・・(3)
式(3)については、次のように証明することができる。(2m-1,2m-m-1)ハミング符号の検査行列Hのある2列の列番号を表すj1及びj2を1≦j1<j2≦2m-1とし、あるk個の行番号を表すi1,i2,…,ikを1≦i1<i2<…<ik≦mとする。検査行列Hのj1列目とj2列目において、i1,i2,…,ik行目の要素がすべて「1」であれば、冗長の対に対応するk回のXOR演算をまとめて1回のXOR演算で行うことで、k-1回のXOR演算が削除可能となる。

【0031】
(2m-1,2m-m-1)ハミング符号の検査行列Hは、すべての非零のm次元ベクトルを列として並べたm行2m-1列の行列である。検査行列Hの各列はすべて異なっており、「1」の要素がk1個であるj1列目と「1」の要素がk2個であるj2列目に対応するXOR演算をまとめて1回のXOR演算により行うことで、k1≠k2である場合にはmin{k1,k2}-1回までXOR演算の回数を削除可能であり、k1=k2である場合にはk1-2回までXOR演算の回数を削除可能である。したがって、以下の関係式が導かれる。
【数8】
JP0005999634B2_000010t.gif
以上のとおり式(3)が証明される。そして、式(3)を用いて式(1)及び式(2)は、以下の通り表記でき、XOR演算回数の下界が評価できる。
m+1-3m-2≦Nm,e・・・・(6)
m+1-2m-2≦Nm,d・・・・(7)
また、Rm(s)については、以後式(3)により以下の通り表記する。
m(s)=(m-4)(2m-1+1)+6・・・・(8)
図4は、Rm(s)をパスカルの三角形における最初の7段を用いた場合に関する説明図である。この場合、R2(s)=0となり、m≧3では、以下の漸化式を満たす。
m(s)=2Rm-1(s)+2m-1-m・・・・(9)
さらに、Rm(s)を係数とする以下の母関数
【数9】
JP0005999634B2_000011t.gif
は、式(5)により以下の式で与えられる(R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989)。
【数10】
JP0005999634B2_000012t.gif
m=2,3,…,12の場合のRm(s)の値を図5に示す。

【0032】
n+3(s),n=0,1,2,…は、次の2つのパターンで生成される数列に等しいことが知られている(N. J. A. Sloane, On-line Encyclopedia of Integer Sequences)。一つ目のパターンは、1からn+2までの整数の集合An={1,2,…,n+2}における空集合を除くすべての部分集合の径の和に等しい。ここで、集合Aの径は、集合Aに属する最大値から集合Aに属する最小値を引いた値として定義される。例えば、n=0ならばA0={1,2}であり、空集合を除くすべての部分集合{1},{2},{1,2}の径はそれぞれ0,0,1となってその合計は1となる。同様にn=1ならばA1={1,2,3}であり,空集合を除くすべての部分集合の径の和は6となる。

【0033】
二つ目のパターンは、以下の通り設定された、2のべき乗の部分和の列Bnに対する畳み込みと等しい。
【数11】
JP0005999634B2_000013t.gif
たとえば、B0=(1)、B1=(1,3)、B2=(1,3,7)に対して、畳み込みは、それぞれ以下の通りとなる。
0;1
1;1×3+3×1=6
2;1×7+3×3+7×1=23

【0034】
次に、上述のように求められたXOR演算回数の下界を下限とする回路構成について説明する。(2m-1,2m-m-1)ハミング符号を用いた並列符号化処理及び並列復号化処理におけるXOR演算回数の下限は、式(6)及び式(7)により以下の通り設定される。
m,e=2m+1-3m-2=2(2m-m-1)-m・・・・(10)
m,d=2m+1-2m-2=2(2m-m-1)・・・・(11)
ここでは、(2m-1,2m-m-1)ハミング符号の検査行列として上記の検査行列Hmを用い、2入力1出力となる1回のXOR演算に起因する遅延時間をtとして、XOR演算回数を下限に設定するとともに遅延時間(m-1)tとなる回路構成について述べる。まず、並列復号化処理における遅延時間が(m-1)tとなる回路構成について、m=2から順に再帰的にm=2,3,…を考える。シンドロームsにおけるsi,i=1,2,…,mの演算開始時刻を0とする。m=2の場合、s1及びs2は以下の通り設定される。
【数12】
JP0005999634B2_000014t.gif

【0035】
図6は、並列復号化処理における演算回路に関する表記例を示す説明図である。図6(a)では、s1及びs2を求める演算回路を図3と同様の表記方法で記載している。以後の説明を容易にするために、こうした演算回路の簡略表記の方法を次のように定める。簡略表記では、まず、以下の式を満たすjを設定する。
【数13】
JP0005999634B2_000015t.gif
そして、設定されたjに関する二進数表記(bm-1m-2…b02を用いてrjの代わりに単にbm-1m-2…b0と表記する。そして、以下の規則1から規則4に従って表記する。
<規則1>
左端の列に上から順にs1からsmを並べる。
<規則2>
m-1m-2…b0,bi ∈{0,1}について以下の値を求め、
【数14】
JP0005999634B2_000016t.gif
この値が小さい値1から大きい値mの順に右から左に列として分類し、各列ではj=(bm-1m-2…b02の小さい値から大きい値の順に上から下に配置する。
<規則3>
規則2で作成した配置図において、bm-1m-2…b0を値0か値1の1ビットを保持する節点とし、節点(bm-1m-2…b02又は節点j, j=(bm-1m-2…b02と表記する。節点jの保持する値をv(j)とし、時刻0での値v(j)を復号化処理ではrjとする。なお,符号化処理では時刻0での値v(j)は、j=2i-1,i=1,2,…,mを除きv(j)=cjとし、j=2i-1,i=2,…,mではv(j)=cj+1とし、v(1)=c3とする。
<規則4>
j<j’を満たす節点jと節点j’との間に、(i1δ(又は(i1,…,ikδ)とラベル付けされた線がある場合には、時刻(δ-1)t~δtの間にv(j)及びv(j’)のXOR演算を行い、時刻δtでの節点jの値を以下のXOR演算結果とする。
【数15】
JP0005999634B2_000017t.gif
この場合、ラベル(i1δ(又は(i1,…,ikδ)は時刻(δ-1)t~δtの間に行われたXOR演算結果がsi1(又は複数のsi1,…,sik)を求めるために用いられることを意味する。以後、ラベル(i1δ(又は(i1,…,ikδ)の表記において、ikをラベルにおけるk番目のインデックス又は単にインデックスと称し、δをラベルにおける下付の時刻δと称する。

【0036】
m=k-1におけるs1,s2,…,sk-1を求める演算回路を表す簡略表記を用いてm=kにおけるs1,s2,…,skを求める回路を表す簡略表記を定める手順を次に示す。なお、簡略表記において、時刻(m-1)tに節点j, j=2i-1,i=1,2,…,mが保持する値がsiの値となる。
<手順1>
次の2つの図を上記規則1及び2に従って1つの図にまとめる。
(1図)m=k-1での簡略表記で各節点(bk-2k-3…b02の先頭ビットに0を追加した節点(0bk-2k-3…b02に変更した図
(2図)m=k-1での簡略表記で各節点(bk-2k-3…b02の先頭ビットに1を追加した節点(1bk-2k-3…b02に変更し、s1,s2,…,sk-1を除いた図
<手順2>
手順1で作成された図において、節点2i-1と節点2i-1+2k-1とを結ぶ線を追加し、その線にラベルとして(i)k-1を付与する処理を、i=1,…,k-1としてk-1回行う。
<手順3>
手順2で作成された図において、skと節点2k-1を追加する。
<手順4>
手順3で作成された図において、次の(手順4-1)をα=1,…,k-1としてk-1回行う。
(手順4-1)
節点2k-1と節点j+2α-1とを結ぶ線を追加する。追加した線のラベルを(k)αに更新する。αが2以上であれば、(手順4-2)によりラベルにインデックスkの追加を再帰的に繰り返す。
(手順4-2)
更新したラベルにおける下付の時刻をβとする。更新したラベル(k)β,β=α又はkを含むすべてのラベル(・,k)βを付与された線で結ばれた右側の節点について、その節点から出ている線のラベルにおける下付の時刻γがγ<βを満たすすべてのラベル(・)γに対して、インデックスkを追加して(・,k)γとする処理を再帰的に繰り返す。

【0037】
図6(b)は、以上説明した手順により簡略表記した例を示している。m=2の場合にs1及びs2を求める図6(a)と同様の演算回路を簡略表記している。図6(b)に示すm=2の場合の簡略表記図を用いて,m=3の場合の簡略表記図を作成する手順の例を図7に示す。図7では、線のラベルが1つ前の手順におけるラベルと同じ場合にはその表記を省略している。手順1では、0を追加した節点(001)、(010)及び(011)に変更した図及び1を追加した節点(101)、(110)及び(111)に変更した図を1つの図にまとめて併記している。手順2では、節点(001)と(101)とを結ぶ線を追加してラベル(1)2を付与し、節点(010)と(110)とを結ぶ線を追加してラベル(2)2を付与している。手順3では、s3及び節点(100)を追加し、手順4-1では、節点(100)と(101)とを結ぶ線を追加してラベル(3)1を付与し、節点(100)と(110)とを結ぶ線を追加してラベル(3)2を付与している。手順4-2では、節点(110)と(111)とを結ぶ線のラベルを(2,3)1に更新している。この場合、XOR演算に起因する遅延時間は2tとなる。

【0038】
図8は、m=2,3,4,5の場合の簡略表記図をまとめて示している。図8では、m=4,5の図では、インデックスの要素数が1個の場合にラベル表示を省略している。図8に示すm=3の簡略表記図よりm=3におけるsiの算法を導き出すことができる。図9は、m=3におけるsiの算法(図9(a))及び算法に用いる値jの一覧(図9(b))を示す。値jは、以下の通り設定される。
【数16】
JP0005999634B2_000018t.gif
図10は、m=5におけるsiの算法(図10(a))及び算法に用いる値jの一覧(図10(b))を示す。値jは、図9に示す例と同様に設定される。図9(b)及び図10(b)では、同じw毎に区切りの横線を追加している。

【0039】
図9に示す算法及びそれに用いる値jに基づいて図3(b)に示す演算回路を得ることができる。すなわち、m=3の場合に手順1から手順4を適用することで、図3(b)に示す演算回路が設定される。手順2及び手順4-1により,簡略表記において節点jの右からk, k≦m-1本の線が出ている場合には、各線の左側の節点j’に対応する値j’の小さい順(図8では、k本の線の上からの順) に時刻0~t,t~2t,…,(k-1)t~kt毎にその線に対応するXOR演算が行われる。一般に、2以上の自然数mの場合に手順1~手順4を適用することで、並列復号化処理におけるs=(s1,s2,…,sm)=rHmTを満たすsi,i=1,2,…,mのある算法が定まり、(2m-1,2m-m-1)ハミング符号の並列復号化処理を行う演算回路を得ることができる。例えば、図8に示すm=5の簡略表記に基づいて、図10に示すm=5におけるsiの算法及び算法に用いる値が得られる。

【0040】
なお、mにおける算法に用いる値jが設定されていれば、ms≦mにおける値jを次の手順Aにより求めることができる。
【数17】
JP0005999634B2_000019t.gif
手順Aによりm=5における値jのリスト(図10(b))からm=2,3,4における値jのリストが得られる。そのため、m=kの簡略表記に対応する演算回路を用いて、mがkより小さい演算回路として利用することが可能となり、演算回路の共通化や演算回路の変更を容易に行うことができ、演算回路のコストダウン及びフレキシビリティを高めることができる。

【0041】
手順1~手順4のアルゴリズムにより得られる簡略表記においてラベルのインデックスの要素数がk,k≧2個のものは冗長な対のXOR演算に対応しており、対応するk回のXOR演算をまとめて1回のXOR演算で行うことで、k-1回のXOR演算を削除可能である。mにおけるsi,i=1,2,…,mのある算法を与える手順1~手順4のアルゴリズムにより得られる削減可能なXOR演算の回数Rm(a)は、図8に基づいて以下の通りとなる。
2(a)=0
3(a)=1
4(a)=6
5(a)=23

【0042】
検査行列Hmにおいて各行における要素が1の個数は2m-1個であり、siを独立して演算する場合に用いられるXOR演算の回数は2m-1-1回である。一方、mにおけるsi,i=1,2,…,mの算法を与える手順1~手順4では、手順4-1においてラベル(m)α,α=1,2,…,m-1が付与されて、インデックスmが追加される回数はm-1回であり、手順4-2においてインデックスmが追加される回数をSmとすると、手順1~手順4における再帰構造からS2=0であり、3≦n≦mにおいて以下の漸化式を満たす。
n=2Sn-1+n-2
この漸化式より、m≧2に対して、Sm=2m-1-mであり、mにおける簡略表記のラベルのインデックスmに基づく削除可能なXOR演算の回数はSm回であることがわかる。また、mにおけるsi,i=1,2,…,mの算法を与える手順1より、mにおける簡略表記から、ラベルのインデックスmに基づくもの以外で削除可能なXOR演算の回数は2Rm-1(a)回であることがわかる。そのため、m≧3において
m(a)=2Rm-1(a)+Sm=2Rm-1(a)+2m-1-m・・・・(12)
である。R2(a)=R2(s)=0、式(9)及び式(12)により、m≧2において
m(a)=Rm(s)=(m-4)(2m-1+1)+6
が成り立つ。

【0043】
以上のことより、(2m-1,2m-m-1)ハミング符号の並列復号化処理においてsi,i=1,2,…,mを求めるXOR演算回数が式(11)を満たすとともに遅延時間(m-1)tである演算回路を構成することができる。(2m-1,2m-m-1)ハミング符号の並列符号化処理においてmビットのパリティビット
【数18】
JP0005999634B2_000020t.gif
を求める演算回路の簡易表記は、mにおけるsi,i=1,2,…,mの算法を与える手順1~手順4で得られる簡易表記において、siを[数18]に示すパリティビットに変更し、節点1及び節点3を結ぶ線並びにi=1,2,…,mでの節点2i-1及び節点2i-1+1を結ぶ線とそれら線のラベル(i’)1,i’=1,2,…,mを削除することで得られる。こうして得られた簡易表記から[数18]に示すmビットのパリティビットを求める演算回路が定まり,そのXOR演算回数は式(10)を満たす。

【0044】
手順1~手順4で定まる(2m-1,2m-m-1)ハミング符号の並列復号化処理でシンドロームを求める演算回路は、2≦ms≦mを満たす(2ms-1,2ms-ms-1)ハミング符号の並列符号化処理でのパリティビットを求める演算回路や並列復号化処理でのシンドロームを求める演算回路に利用可能である。さらに、これらの演算回路は、1≦ks≦2ms-ms-1,2≦ms≦mを満たす(ks+ms,ks)ハミング符号の並列符号化処理でのパリティビットを求める演算回路や並列復号化処理でのシンドロームを求める演算回路に利用可能である。検査行列がHmでなく一般の検査行列H場合には、列の置換に対して演算回路への入力の配置をHの列に合わせて並び直せば、上述した手順を適用できる。そのため、検査行列がハミング符号の検査行列に分解できるBCH符号のシンドロームの演算にも適用可能である。

【0045】
手順1~手順4で得られるmにおける簡易表記は、m個の集合のベン図と関連付けることができ、集合{1,2,…,m}の空集合を除いたべき集合での包含の関係によるハッセ図においてある規則に従って線を除いた図と関連付けることもできる。
【符号の説明】
【0046】
1・・・符号化・復号化装置、10・・・符号化・復号化処理部、11・・・符号化データ生成部、12・・・誤り訂正処理部、20・・・記憶部
【先行技術文献】
【0047】

【特許文献1】米国特許第7,293,222号明細書
【0048】

【非特許文献1】F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9