JPH02260823A - 誤り訂正符号の復号方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野１ 本発明は、デジタルＶＴＲなどの大容量の磁気記録装置
や、デジタル通信で必須な誤り訂正符号の構成法と、そ
の復号方式および復号装置の構成に関するものである。

［発明の概要］ 本発明による、誤り訂正符号の復号方式は、３次元の直
方体の形状に構成したＲｅｅｄ−５ｏｌｏｍｏｎ符号を
対象とし、各軸方向の３通りの復号結果を総合的に判断
することにより、各軸方向の符号の訂正能力を最大限に
まで使用しながらも、誤訂正の発生を著しく低く押えつ
つ、全体として高い訂正能力を実現する復号方式である
。そのため、各軸方向には、パリティの数の少ない能力
の低い符号であっても、全体としての訂正能力は、符号
化率が等しく各軸方向にはより多くのパリティを持゛つ
２次元積符号よりも、高い訂正能力を実現することがで
きる。

［従来の技術１ 従来、この種の誤り訂正符号として、Ｉｌｅｅｄ−５ｏ
ｌｏｇ＋ｏｎ符号がよく用いられる。とりわけ、デジタ
ルＶＴＲなどの画像記録の分野では、ｎｅｅｄ−５ｏｌ
ｏｍｏｎ符号の２次元に構成した積符号の形で利用され
る。

Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号の構成原理と復号法につ
いて概略を説明する。

位数が２°である有限体をＧＦ　（２Ｄ）として、ＧＦ
　（２’）の元を係数とする不定光Ｘの多項式環を考え
る。

ＧＦ（２°）の任意の元をａｏ＋・・・＊　ａＫ−１と
し、これらを伝送すべき情報とする。ここで、 Ｉ　（Ｘ）−ａｏ”ａｔＸ”・＝◆ａ（−１Ｘ”１とす
る。αをＧＦ　（２Ｄ）の原始光として、多項式％式％
） を「符号生成多項式」と呼び、 Ｔ（Ｘ）＝Ｉ（Ｘ）・Ｘ２ｔ＋Ｉ（Ｘ）　ｍｏｄ　Ｇ（
Ｘ）を、情報ａＯ２””＊　ａＫ−１のｒ　Ｒｅｅｄ−
５ｏｌｏｍｏｎ符号」と呼ぶ。

Ｑ（Ｘ）（あるいはＩ（Ｘ）　ｍａｄ　Ｇ（Ｘ））（７
）第０次から第（２ｔ−１）次までの係数を、情報ａｏ
＋　”・−ａＫ−１の「パリティ」と呼ぶ。明らかにＴ
　（Ｘ）の第２を次から第（ｋ−１１次までの係数はａ
。、・・・、　ａＫ−１となる。

このようにして作ったＲｅｅｄ−５ｏｌｏｍｏｎ符号を
ＲＳ（ｋ◆２ｔ、に、２ｔ＋１） と書く０丁（Ｘ）のに÷２ｔｍの係数を「シンボルノと
呼ぶが、この符号はＴ　（Ｘ）に加算される最大を個ま
でのシンボル誤りを訂正する能力を持つ。

Ｔ（Ｘ）に誤りが加算された多項式をＹ（Ｘ）と書くと
、ｙ　（ｘ）から元のＴ　（Ｘ）を復元する操作を「誤
り訂正」と呼ぶ。誤り訂正は、次に定義する「シンドロ
ーム」と呼ぶ２を個のＧＦ（２°）の元を用いて行う。

Ｓｌ−Ｙ（α′）（ただし、ｉ−０，・・・、２ｔ−１
）詳細は略すが、全てのＳｌｌＪ＜ＧＦ（２Ｄ）のゼロ
元Ｏに等しいとき、Ｙ（Ｘ）には誤りはないとし、それ
以外の場合には、最大を個までの誤りの位置と値が、シ
ンドロームから計算できる。実際上は、誤りの数がｔ個
より多い場合もあり、この時には、なんらかの誤りの位
置と値が求まるか、誤りの位置と値が計算できないかの
いずれかである。前者の場合、求まった誤りの位置と値
は、真の誤りの位置と値に一致することはなく、「誤訂
正」と呼ばれる。後者の場合、ｙ　（ｘ）の誤りの位置
と値はわからないが、Ｙ（×）に誤りが含まれているこ
とがわかったという意味で、「誤り検出」できたと言う
。現′実には、符号Ｒ５（ｋ＋２ｔ、に、２ｔ＋１）の
使用に当たっては、最大能力ｔまで誤り訂正を行うこと
はなく、ある適当な自然数ｎを設定し、（ｔ−ｎ）個ま
での誤りの位置と値が求まったときに、結果を正しいも
のとして採用し、それ以外の場合には、誤り検出ができ
たとすることが一般的である。すなわち、訂正能力をｎ
だけ減少させて、その分を検出能力に振り分けているわ
けである。

また、受信した符号ｙ　（ｘ）とともに、ｒ　Ｙ　（Ｘ
）のこれこれの位置は誤りである可能性がある。」と主
張する情報（これを「消失」という）が与えられたとす
る。この時真の誤りが全てこの消失に含まれているとき
、 （消失の個数）≦２ｔ であれば、全ての誤りを訂正することができる。

この訂正を「消失訂正」という。

前述の２次元構成の積符号の復号においては、第１段階
として、ある１方向に「誤り訂正」を行い、訂正できな
い符号は消失として、次段に引き継ぐ、第２段階ではも
う一方の直交する方向に「消失訂正」を行うのが一般的
である。第１段階の方向の軸から見ると消失は１つの１
次元符号全体であるけれども、第２段階の軸から見ると
１つの１次元符号の中のいくつかの点にすぎない、それ
ゆえ消失訂正が有効に機能するわけである。

［発明が解決しようとする課題］ 従来、映像や音声のデジタル記録の分野では、Ｒｅｅｄ
−５ｏｌｏａ＋ｏｎ符号を２次元に構成した積符号の形
で利用しているが、記録の高密度化の要求に伴って、よ
り誤りの発生確率の高い領域でも実用になる、より訂正
能力の高い訂正符号が求められている。一般に符号の訂
正能力を上げるには、付加するパリティの数２ｔを大ぎ
くすればよいのであるが、そうすると、符号全体の中で
パリティの占める割合（符号化率）が増大するのみなら
ず、２ｔを大きくすればシンドロームから誤りの位置と
値を計算する手順が指数関数的に複雑になり、画像記録
などの高速なデータレートで実時間動作するハードウェ
アの実現が著しく困難になる。

本発明の目的は以上のような問題を解消した誤り訂正符
号の復号方式を提供することにある。

【０！題を解決するための手段］ 以上のような問題を解消するため、本発明は各辺の長さ
が各々Ｌ、Ｍ、Ｈの直方体の形で、長さしの辺に平行な
Ｍ×Ｎ個の単独な符号、長さＭの辺に平行なＬ×Ｎ個の
単独な符号、および長さＮの辺に平行なＬ×Ｍ個の単独
な符号により構成され、全体として３次元形状をなす符
号の復号において、個々に誤りの存在が検出された３個
の単独な符号が交差する点ＣＰを検出することを特徴と
する。

［作　用］ 本発明によれば、３次元に構成したｌ１ｅｅｄ−５ｏｌ
ｏｒｎｏｎ符号を主な対象とし、各軸方向の２通りの復
号結果を総合的に判断することにより、各軸方向の符号
の訂正能力を最大限にまで使用しながらも、誤訂正の発
生を著しく低く押えつつ、高い訂正能力を実現する。

そのため、各軸方向にパリティの数の少ない能力の低い
符号であっても、全体としての訂正能力は、符号化率が
著しく２つの各軸方向にはより多くのパリティを持つ２
次元積符号よりも、高い訂正能力を実現することができ
る。

このように、３次元を構成する各軸の符号は、従来の２
次元積符号の各軸の符号よりもパリティの少ない単純な
符号を採用できることから、単純な復号器の組合せで、
画像記録などの高速なデータレートで実時間動作する高
い訂正能力を持つ復号装置が構成できる。

Ｃ実施例］ 直方体形状の３次元的に構成した符号の、木方式による
復号の原理について、概略を述べる。

第１段階では、直方体形状の３次元的符号を構成する各
軸の方向の単独な符号について、個々の符号の持つ訂正
能力の大部分を誤り検出に使用し、誤り検出を主たる目
的に誤り訂正を行う（後述するが、各軸に２つのパリテ
ィを付けた符号では検出しか行わない）、直方体の全て
の単独な符号について訂正をおこなって、訂正できない
誤りが残りていると幹には、誤りの検出された３木の符
号の交差する点（これをＣＰと呼ぶ）がいくつか存在し
ている。各々の単独な符号で誤りの検出が正しく行われ
ていれば、残留している全ての誤りは、これらＣＰに含
まれていることになる。

第２段階では、第１段階よりも高い能力で、残留してい
る誤りの訂正を行うのであるが、そうすると誤訂正の危
険が増大する。この３次元的構成の符号では、直方体の
任意の点１つごとに３方向に交差する３つの単独な符号
が存在しているので、直方体の点各々に３通りの復号結
果が得られる。そこで、 （１）ある点での３通りの復号結果について、多数決判
定により正しいとする結果を採用する （すなわち、少なくとも２個の復号結果が一致していれ
ば正しいとする） ことで誤訂正の危険を減らすことかできる。（この判定
基準（１）は第１段階で用いることもできる） さらに、前述のｃｐを用いて、 （２）ある単独な符号の復号結果の誤りの位置が全てＣ
Ｐである 符号結果だけを、（１）の多数決判定の対象とすれば、
誤訂正の危険をさらに減らすことができる。

ところで、（１）の多数決判定には欠点もある。

すなわち、ある点に交差する３個の符号の復号結果のう
ちで、唯一つ正しいものがあり、他の２個は訂正できな
いかもしくは誤訂正であった場合には、この正しい結果
を採用することができない。

このような場合には、ある単独な符号の復号結果が（２
）を満たし、さらに （３）その符号上に存在するｃｐの個数が、訂正可能な
誤りの個数以下である場合には、（多数決判定によらず
）この復号結果を採用することにする。　（この判定基
準（３）の妥当性については後述する） こうして、（２）、（１）を満たす復号結果だけではな
く、（２）　、　（３）を満たす復号結果をも採用する
ことにすれば、さらに多くの誤りを訂正することができ
る。

ところで、前述したように「残留している全ての誤りは
ＣＰに含まれている」のであるから、第２段階では、直
方体の全ての点についてこのような訂正を行う必要はな
く、ＣＰについてのみ、訂正を行えばよい。

こうして、各々のＣＰについて訂正を行うとすると、あ
るＣＰに交差する符号の復号結果が、前述の判定基準に
より正しいと判定されたときには、そのＣＰの位置の誤
りを訂正するだけではなく、正しいと判定された復号の
復号結果全てを採用すれば、−度により多くの誤りを訂
正することができる。

このとき、このＣＰを消去する（以降の処理ではＣＰと
は見なさない）と共に、これらの符号上に存在する他の
ＣＰも消去することとする。

第３段階では、ｃｐを消失位置とする消失訂正を用いて
、第２段階で訂正できなかった誤りを訂正する。第２段
階と同様に、訂正に成功した符号上に存在するＣＰを消
失する。

直方体全体にわたる消失訂正を、ただ１回に限ることな
く、何度でも繰り返すことによって、次々に誤り訂正し
てゆくことができる。この繰り返しの効果は、２次元以
下の構成の符号には見られない、３次元的に構成した符
号の持つ特徴の１つである。

これらの手順の詳細を次に述べる。

第１図は３次元の直方体形状の符号の構成図である。

まず、位数が２°である有限体をＧ　Ｆ　（２’）とす
る（　Ｇ　Ｆ　（２Ｄ）の原始光をα、ゼロ元をＯと書
くことにする）。

Ｇ　Ｆ　（２°）の元Ｌ×Ｍ個からなる集合Ｖを考える
。Ｖの元金体を、各辺がり、Ｍ、Ｈの長さの直方体形状
に配置して、Ｖの任意の元ｖ（ｋ、ｉ。

ｊ）（ただしｋ　＝　Ｏ、、・・・、Ｌ−１，ｉ＝ｏ、
・・・Ｍ−１，ｊ＝ｏ、・・・、Ｎ−１）と表わすこと
にする。

直方体Ｖは２つの領域からなるものとする。

Ｕユニｒ２ｔＬ≦ｋ＜Ｌかつ、２ｔ、≦ｉ＜Ｍかつ、２
ｔＮ≦ｊ＜ＮＪなる座標（ｋ。

ｉ、ｊ）の領域で、ここではｖ　（ｋ。

ｉ、ｊ）の値が任意。

領域２：「０≦ｋ　＜　２　ｔ、もしくは、０≦ｉく２
ｔＭもしくは、０≦ｊ　＜　２　ｊＮＪなる座標（ｋ、
ｉ、ｊ）の領域で、ここでは ｖ　（ｋ、ｉ、ｊ）の値がＯｏ 領域１が伝送すべき情報を格納する領域、領域２がパリ
ティを格納する領域である。

さて、 （α’Ｉ「ｓＱ、・＋　、２Ｌｔ−１１ヲ根とすル２ｔ
Ｌ次の多項式をＧＬ（Ｘ）、 （ａ　’１ｒｓＯ，・・・、２ｔＭ−１）　を根とする
２ｔ、４次の多項式をＧ。（Ｘ）、 （ａ　’１ｒ−０，−・−，２ｔＮ−１）　を根とする
２ｔ、次の多項式をＧＮ（ｘ）、 とする。

さて、以下に述べる符号化手順Ｅ２　、ＥＹ。

Ｅ、に従い、領域２にパリティを設定して、符号を構成
する。

符号化手順Ｅ２ あるｉ、ｊを固定したときの集合Ｖの領域１の（Ｌ−２
ｔＬ）個の元 ｖ（２ｔＬ、ｉ、ｊ）、　ｖ（２ｔＬ＋１．ｉ、ｊ）、
　・−、ｖ（Ｌ−１，ｉ、ｊ）を係数とする多項式 ％式％）（ ただし、Ｋ−Ｌ−２ｔＬ−１で、ａｐ−ｖ（Ｆｔｔ◆ｐ
、ｉ、ｊ））に対して、（２ｔＬ−１）次の多項式 １式％（） の第に次の係数をｖ　（ｋ、ｉ、ｊ）とする。すなわち
、上述の領域１の（Ｌ　−２ｔｔ、）個の元に対して、
符号生成多項式ＧＬ（Ｘ）により生成される２ｔＬ個の
パリティを、領域２の元 ｖ（０，ｉ、ｊ）、　ｖ（１，ｉ、ｊ）、　−、ｖ（２
ｔＬ−１，ｉ、ｊ）とする。

この操作を０≦ｉ＜Ｍ、０≦ｊ　＜Ｎ、なる全てのｉ、
ｊについて行う、（手順終り） １１似１匪旦り 同様に、あるに、ｊを固定したときの集合Ｖの領域１の
（Ｍ−２を一個の元 ｖ（ｋ、２ｔｍｊ）、　Ｉ／（ｋ、２ｔＭ＋１．ｊ）、
　・・・、ｖ（ｋ、Ｍ−１，ｊ）に対して、符号生成多
項式Ｇ工（Ｘ）により生成される２ｔｗ個のパリティを
、領域２の元 ｖ（ｋ、０．ｊ）、　ｖ（ｋ、１．ｊ）、−、ｖ（ｋ、
２ｔＭ−１，ｊ）とする。

この操作を０≦ｋ＜Ｌ、Ｏ≦ｊ＜Ｎ、なる全てのに、ｊ
について行う、（手順終り） １ｉｉ玉肌且り 同様に、あるに、ｉを固定したときの集合Ｖの領域１の
（Ｎ−２ｔｓ）個の元 ｖ（ｋ、ｉ、２ｔ、）、　ｖ（ｋ、ｉ、２ｔＨ＋１）、
　−、ｖ（ｋ、ｉ、Ｎ−１）に対して、符号生成多項式
ＧＮ　（Ｘ）により生成される２ｔｓ個のパリティを、
領域２の元 ｖ（ｋ、ｉ、Ｏ）　、　ｖ（ｋ、ｉ、１）　、　”・、
ｖ（ｋ、ｉ、２ｔＨ−１）とする。

この操作を０≦ｋ＜Ｌ、Ｏ≦ｉ＜Ｍなる全てのに、ｉに
ついて行う。（手順終り） ｋの増加する方向を「Ｚ軸」、ｉの増加する方向を「Ｙ
軸」、ｊの増加する方向を「Ｘ軸Ｊ、Ｖの座標（０，０
，０）を「原点」と呼ぶことにする。

手順Ｅｚ、　　ｙ、Ｅｘを実行することによつて、直方
体Ｖは、 Ｚ軸方向のＭ×Ｎ本の符号Ｒ５（Ｌ、Ｌ−２ｔい２ｊＬ
＋１）Ｙ軸方向のＬ×Ｎ木の符号ＲＳ（Ｍ、Ｍ７２ｔｍ
、２ｔｖ＋１）Ｘ軸方向のＬ×Ｍ本の符号ＲＳ（Ｎ、Ｎ
−２ｔＮ、２ｔＮ＋１）を含んでいることになる。この
符号の構成を第１図に示す。

さて、直方体ＶのＬ×Ｍ×Ｎ個のシンボルは、適当な順
序で一列の系列に並べられ、順次伝送される。伝送路に
おいてシンボル誤りが加算されたこの系列を、受信側で
、各辺の長さがり、Ｍ、Ｎである直方体Ｖ′に再構成す
る。

各辺の長さがり１Ｍ、Ｎで３　ｂｉｔのセルＬｘＭ×Ｎ
個からなる直方体Ｆを用意しておき、直方体Ｖ′に対す
る復号を以下の手順により行う。（直方体ＦのＬ×Ｍ×
Ｎのセルは０００に初期化されているものとする。） まず、以下の復号化手順ＤＤｘ、ＤＤＹ。

ＤＤ２により第１段階の誤り訂正と、訂正できない誤り
の位置検出を行う。

１１監１」１以Ｌ Ｖ′の座ｍ（ｋ、ｉ、ｊ）におけるｘ軸方向ノＮ個の元 ｖ’（ｋ、ｉ、ｏ）　　、　＝−、ｖ’（ｋ、ｉ、Ｎ−
１）は、元の直方体Ｖの対応するＮ個の元 ｖ（ｋ、ｉ、０）　、−−−、ｖ　（ｋ、ｉ、Ｎ−１）
によって構成されるＲ５（Ｎ、Ｎ−２ｔＮ、２ｔｓ＋１
）符号に誤りが加算されているかもしれないものである
。

直方体Ｖ′中にＬ×Ｍ本存在する、この誤りがあるかも
しれない符号 ｌｌ５（Ｎ、Ｎ−２ｔＮ、２ｔＮ”１）に対して、あら
かじめ０＜ｎ、≦ｔ、４なる自然数ｎｘを設定し、０≦
ｋ＜Ｌ、Ｏ≦ｉ＜Ｍなる全てのｋ。

ｉについて％　　（ｔｔｔ−ｎｘ）個以下の誤り訂正を
Ｌ×Ｍ回試みる。

あるに、ｉにより指定された１つの符号の誤り訂正に成
功すれば、その符号の中の誤りのシンボルを訂正する。

「誤り訂正に成功する」とは、Ｒｅｅｄ−５ｏｌｏｍｏ
ｎ符号の復号における通常の意味において復号に成功す
る場合である。すなわち、あるに、ｉにより指定される
Ｖ′のＸ軸方向のＮ個の元 ｖ（ｋ、ｉ、Ｏ）　、・−、ｖ　（ｋ、ｉ、Ｎ−１）を
誤りがあるかもしれない符号 Ｒ５（Ｎ、Ｎ−２ｔＮ、２ｔＮ＋１） として、 １）２ｔＮ個のシンドロームが全て０ ２）　（ｔＮ−ｎＸ）個以下の誤りの位置と値が計算で
きた。

のどちらか一方が成り立つ場合を言う。

一方、誤り訂正ができない（すなわちりも２）も共に成
り立たない）場合、誤りが検出されたことになり、直方
体Ｆ上の、符号に該当する位置（ｋ、ｉ、Ｏ）、＝・、
（ｋ、ｉ、Ｎ−１）のＮ個のセルに、００１をｂｉｔ単
位にｍｏｄ２加算する。（手順終り） 復号化手順ＤＤＹ あらかじめ０〈ｎＹ≦ｔＹなる自然数ｎｙを設定し、０
≦ｋ＜Ｌ、Ｏ≦ｊ＜Ｎなる全てのに、ｊについて、Ｙ軸
方向のＬ×Ｎ木の符号 Ｒ５（Ｍ、Ｍ−２ｔＭ、２ｔＭ”１） に対して（ｔ、−ｎ、）個以下の誤り訂正を行う。

誤り訂正に成功すれば、該当するＶ′上のシンボルを訂
正する。

「誤り訂正に成功する」とは、 １）２ｔＭ個のシンドロームが全て０ ２）　（ｔｖ−ｎｙ）個以下の誤りの位置と値が計算で
きた。

のどちらか一方が成り立つ場合を言う。

誤り訂正ができない（誤りが検出された）場合には、直
方体Ｆ上の符号に該当する位置のＭ個のセルに、０１０
をｂｉｔ単位にｍｏｄ２加算する。（手順終り） 復号化手順ＤＤ！ あらかじめ０くｎ２≦ｔＬなる自然数１２を設定し、Ｏ
≦ｉ＜Ｍ、Ｏ≦ｊ＜Ｎなる全てのｉ、ｊについて、Ｚ軸
方向のＭ×Ｎ木の符号 Ｒ５（Ｌ、Ｌ−２ｔＬ、２ｔＬ÷１） に対して（ｔＬ−ｎｚ）個以下の誤り訂正を行う。

誤り訂正に成功すれば、該当するＶ′上のシンボルを訂
正する。

「誤り訂正に成功する」とは、 １）２ｔＬ個のシンドロームが全て０ ２）　（ｔＬ−ｎｚ）個以下の誤りの位置と値が計算で
きた。

のどちらか一方が成り立つ場合を言う。

誤り訂正ができない（誤りが検出された）場合には、符
号に該当する直方体Ｆ上のＬ個のセルに１００をｂｉｔ
単位にｍｏｄ２加算する。（手順終り）さて、 「復号化手順ＤＤＫ　、ＤＤｙ　、ＤＤｚの各段階にお
いて、訂正不能の誤りが全て検出された」と仮定する。

（これを「仮定１）と呼ぶことにする。） これにより、 ［残っている任意の誤りの位置を（ｋ、ｉ。

ｊ）とすると、対応する直方体Ｆのセル（ｋ。

ｉ、ｊ）の値は必ず１１１である」 ことになる。（これを「命題１」と呼ぶことにする） 一方、直方体Ｆのセル（ｋ、ｉ、ｊ）の値が１１１であ
るからといって、Ｖ′の座標（ｋ、ｉ。

ｊ）が誤りとは限らない。

Ｆのセルの値が１１１である位置（ｋ、ｉ。

ｊ）を「交差点Ｊ　（（：ｒｏｓｓ　Ｐｏ１ｎｔ、略し
てｃｐ）と呼ぶことにする。これより命題１は、次のよ
うになる。

「残フている任意の誤りは、全てＣＰである」 次に、以下の復号化手順ｏｃｘｙｚにより、第１段階の
誤り訂正で訂正できなかりだ誤りの訂正を行う。

復号化手順ＤＣｘｙｚ 全ての交差点ＣＰについて、ＣＰ１つ毎にＸ。

Ｙ、Ｚの各軸方向の３通りの誤り訂正を試みる。

ただし、 Ｘ軸方向には、ｔａ、＜　ｎ、なるＩｌｘを用いた（ｔ
ｓ−冒Ｘ）個以下の誤り訂正、 Ｙ軸方向には、ｍｙ＜　ｎｙなるＩＹを用いた（ｔｉｔ
−口Ｙ）個以下の誤り訂正、 Ｚ軸方向には、１１２＜ｎｚなるｍｚを用いたＤｔ、−
ｍｚ）個以下の誤り訂正 を各々行うものとする。これは手順ＤＤｘ。

ＤＤ、、ＤＤ、よりも、より高い能力で訂正を行うこと
を意味する。

あるＣＰの座標を（ｋ、ｉ、ｊ）とすると、それに交差
するｘ、ｙ、ｚの各軸方向の３通りの訂正結果のうち、
少なくとも２つの方向において、訂正に成功し、各々の
結果が合理的で、結果が一致する場合に、一致した結果
を正しいものと見なして採用し、ＣＰ　（ｋ、ｉ、ｊ）
に対応するＶ′の値を修正すると同時に、結果が一致し
た少なくとも２つの軸上に存在する全てのＣＰの値を０
００とする（すなわちＣＰを消去する）。

この［２つの方向において、訂正に成功し、各々の結果
が合理的で、結果が一致する」の定義は次の通り。

「訂正に成功」するとは前述と同様にＣＰ（ｋ、ｉ、ｊ
）より指定されるＶ′のＸ軸方向のＮ個の元 ｖ’（ｋ、ｉ、０）　、　・−、ｖ’（ｋ、ｉ、Ｎ−１
）を、誤りがある（かもしれない）符号 Ｒ５（Ｎ、Ｎ−２ｔＮ、２ｔＮ◆１） とみなして、 １）２ｔ、個のシンドロームが全て０ ２）　（ｔＨ−ａｘ）個以下の誤りの位置と値が計算で
きた。

のどちらか一方が成り立つ場合を言う、Ｙ、Ｚ軸方向に
ついても同様である。

「結果が合理的」とは、 ３）訂正に成功して２）であったとき、計算された通り
の位置が全てＣＰである。

場合を言う、また、シンドロームが全てＯである１）の
場合は無条件に「結果が合理的」とする。

この判定は、命題１の対偶 「ＣＰではない位置には誤りは存在しない」により、Ｃ
Ｐではない位置に誤りが検出された場合には、その誤り
訂正は誤訂正であると見なして採用しないことを意味す
る。また、１）の場合は、その軸上に誤りはない、とい
う主張であり、軸上にＣＰがあっても命題１に矛盾しな
い。

「２つの方向において結果が一致する」とは、（ｋ、ｉ
、ｊ）において、Ｘ軸とＹ軸の２つの方向について「誤
り訂正に成功」し、かつ共に「結果が合理的」であった
とする。

Ｘ軸の復号結果を Ｘ（ｋ、ｉ、０）　、＋＋＋、　Ｘ（ｋ、ｉ、ｊ）、　
−、Ｘ（ｋ、ｉ、Ｎ−１）Ｙ軸の復号結果を Ｙ（ｋ、ｉ、ｏ）　、・・・、　Ｙ（ｋ、ｉ、ｊ）、・
・・、Ｙ（ｋ、Ｍ−１，ｊ）とする、この時Ｘ軸とＹ軸
の２つの軸が交差する唯一つの座ｍ（ｋ、ｉ、ｊ）にお
いて復号値が一致する場合、すなわち、 ４）　Ｘ（ｋ、ｉｊ）　−Ｙ（ｋ、ｉ、ｊ）の場合を「
結果が一致する」と言う。

あるｃｐの座標（ｋ、　　ｉ、ｊ）において、「少なく
とも２つの方向において誤り訂正に成功し、かつ共に結
果が合理的で、結果が一致する」軸の組合せは次の４通
りでありうる。

（ｘ、ｙ） （ｙ、ｚ） （Ｚ、Ｘ） （ｘ、ｙ、ｚ） 最初の組は、結果が一致するのがＸ＠とＹ軸だけの場合
で、２番目と３番目も同様である。４番目の組はＸ軸、
Ｙ軸、２軸全ての結果が一致する場合である。

この時、各々の組合せにおいて、 Ｘ軸とＹ軸の誤りの訂正とＣＰの消去 Ｙ＠とＺ釉の誤りの訂正とＣＰの消去 ＺＭとＸ軸の誤りの訂正とＣＰの消去 ＸｉとＹ軸とＸ軸の誤りの訂正とＣＰの消去を行う。（
手順路り） この手順ｏ　ｃ　ｘｙｚで、あるｃｐの座標（ｋ。

ｉ、ｊ）において２つの方向について「誤り訂正に成功
し、かつ共に結果が合理的」であるにもかかわらず、「
結果が一致しない」場合とは、例えば、Ｘ軸については
１）が成立ち、Ｙ軸については２）が成立して誤り訂正
の位置が（ｋ、ｉ、ｊ）そのものである、とする場合で
ある。

このとき、Ｘ軸復号ではシンドロームが０ゆえ、 Ｘ（ｋ、ｉ、ｊ）　　＝ｖ’　（ｋ、ｉ、ｊ）であり、
Ｙ軸復号ではｖ”　（ｋ、ｉ、ｊ）　、が誤りゆえ、Ｙ
（ｋ、ｉ、ｊ）　　≠ｖ’　（ｋ、ｉ、ｊ）となり、４
）は成立しない。

このような場合は、Ｘ軸もしくはＹ軸の復号の、少なく
ともどちらか一方が、誤訂正であるときに起こりつる。

この手順ＤＣＸＹ２の特徴は、多数決による判定論理を
採用している点にある。前述のように手順Ｄ　ＤＸ　、
　Ｄ　Ｄｖ　、　Ｄ　Ｄｚよりも訂正能力を高めている
ので、その分だけ誤訂正の危険が増大している。その危
険を多数決判定により減少せしめているわけである。

また、この手順ＤＣＸＹ２は、単に誤り訂正だけではな
く、手順ＤＤｘ　、ＤＤｙ　、ＤＤｚによって発生した
ＣＰを減少させていることが、以下の手順の有効性に大
きく寄与していることを注意しておく。

４号化　順ＤＥｘＹ□ Ｘ軸方向の符号Ｒ５（Ｎ　、　Ｎ−２ｔＨ、２ｔｓ”　
１）は最大２ｔＮ個までの消失訂正、 Ｙ軸方向の符号Ｒ５（Ｍ　、　Ｍ−２ｔＭ、　２　ｔＭ
”　１）は最大２ｔＭ個までの消失訂正、 Ｚ・軸方向の符号Ｒ５（Ｌ、Ｌ−２ｔい２ｔＬ◆１）は
最大２ｔＬ個までの消失訂正、 の能力を持っている。そこでＦに残フているＣＰを「消
去位置」と見なして、交差するｘ、ｙ、ｚ方向のいずれ
かの軸上にＣＰが存在する全ての座標（ｋ、ｉ、ｊ＞に
つい°〔、Ｘ、Ｙ、Ｚ軸の各方向に、各々最大２ｔｓ、
　２ｔＭ、　２ｔＬ個までの消失訂正を行い、訂正を行
った位置のｃｐも消去する。

この消去訂正をＶ′全全体ついて、単に１回に限ること
なく何回か繰り返すことにより、ＣＰを次々に減らして
ゆくことができる。繰り返しの停止条件は、 Ｓｔ）　　交差するｘ、ｙ、ｚ方向のどれかの軸上にＣ
Ｐが存在する、Ｆの全ての座標（ｋ。

ｉ、ｊ）において、各軸上に各々２１．＋１゜２ｔｗ”
ｌ、　２ｔＬ◆１個以上のｃｐが存在している。

もしくは、 Ｓ２）　　　Ｆの中にＣＰが存在していない。

の一方が成り立つ場合とする。（手順終り）以上の複数
の手順は、上述した順序に行うだけではなく、様々な変
形が考えられる１例えば、ＤＣｘｙｚを何回か繰り返す あるいは ＤＣｘｙｚを省略して、い鈴なりＤＥＸＹＺを行う あるいは （Ｄ　ＣＸＹ！　＝Ｄ　Ｅｘ−ｙｚ　）を何回か繰り返
すなどである。

ここで、手順ＤＣｘｙｚを拡張した手順について述べる
。

手順ＤＣｘｙ□においては、あるＣＰの座標（ｋ、ｉ、
ｊ）にて、少なくとも２軸方向にて結果が一致すること
を、結果の採用の条件としていた。あるｃｐの座標（ｋ
、ｉ、ｊ）にて、ｒ誤り訂正に成功し、かつ結果が合理
的」である軸かただ１つしかない場合を考える。このと
き、仮にその軸の復号結果が正しかったとしても、同様
な軸が他に存在しないために、その復号結果を捨てざる
を得ない、このような単一軸を救済するのが次の手順Ｄ
ＣＸＹｚ−Ａである。

手順ＤＣｘＹ□−八 手順ＤＣｘｙｚにおいて、「誤り訂正に成功し、かつ結
果が合理的」である軸がただ１つしかない場合、その軸
上のＣＰの個数が、その軸の符号の訂正可能な誤りの個
数以下であれば、復号結果を正しいものとして採用する
。

すなわち、あるｃｐの座標（ｋ、ｉ、ｊ）にて、 Ｘ軸がそのような軸であった場合には、ＳＸ）　　＜Ｘ
Ｈ上のｃｐの数）≦ｔＨ−＋＊ＸＹ軸がそのような軸で
あった場合には、ｓｙ）　　（ｙ軸上のＣＰの数）≦ｔ
Ｍ−ｍｙＺ軸がそのような軸であった場合には、５□）
（Ｚ軸上のｃｐの数）≦１．−吋が成り立てば、各々の
場合、復号結果を正しいものとして採用する。（手順終
り） この手順Ｄ　ＣＸＹＺ−Ａの妥当性は、命題１から明ら
かである。すなわち、ある軸上のＣＰの数をＮＣＰとす
ると、命題ｌはその軸上の誤りの個数がＮＣＰ以下であ
ることを保証している。ゆえに、ＮＣＰがその軸の符号
の訂正可能な誤り個数以下であれば、誤訂正することな
く誤り訂正を行える。

このように、本復号方式が誤訂正を起こさないためには
、ひとえに、命題１ひいては仮定１の成立に大きく依存
している。いうまでもなく、仮定ｌはあくまで仮定であ
って、手順ＤＤ、。

ＤＤＹ　、ＤＤｚの各段階において、訂正不能の誤りが
見逃され、この誤りが交点ＣＰではない場合も、現実に
は起こり得る。この見逃しの確率をできるだけ小さくす
る必要があり、そのためにはｎｘ＋　’Ｙ　、ｎＺを大
ぎくするとよい。見逃し確率が最小になるのは、 ｊＨ”ｎｘ　＋　ｊＭ”ｎｙ　＊Ｌ、、−ｎｚの場合、
すなわち手順Ｄ　Ｄｘ　、　Ｄ　Ｄｙ　、　Ｄ　Ｄｚの
各段階では、訂正は行わず誤りの検出のみ（具体的には
、シンドロームが０かどうかの判定のみ）を行う場合で
ある。ところがこの場合にはＤＤｘ　、ＤＤｙ　、ＤＤ
ｚの各段階で訂正できるはずの誤りがそのまま放置され
るのみならず、発生するＣＰが著しく多くなるので、消
失訂正手順ＤＥｘｙｚの効果が期待できなくなる。よっ
てｎＸ、ｎＹ、ｎ、は適度の値であることが望まれる。

このように、誤りが見逃され、交点ＣＰではない位置に
誤りが存在することがあり得る。このとき復号化手順Ｄ
Ｅｘｙｚを実行すると、誤訂正による新たな誤りが発生
してしまう。このため、手順ＤＣｘｙｚで行ったのと同
様の交差点における復号値の一致検定を導入することに
より、消失訂正における誤訂正の検出を行うことが考え
られる。こうして拡張したのが次の手順Ｄ　Ｅ　ｘｙｚ
”’Ａである。

号化手順Ｄ　Ｅ　ＸＹＺ−Ａ 手順ＤＥｘｙｚにおいて、あるｃｐの座標（ｋ。

ｉ、ｊ）で交差する３軸の消失訂正の復号結果のうちで
、少なくとも２軸の方向について、そのＣＰの座標（ｋ
、ｉ、ｊ）における復号値が一致する場合、これら一致
した少なくとも２軸の方向の復号結果を採用する、（い
うまでもなく、消去すべきＣＰはこれら一致した軸上の
ものに限る。

また、この場合、これらの軸の交点であるＣＰ（ｋ、ｉ
、ｊ）も消去される。）この手順をＶ′全全体ついて何
回が繰り返す場合の停止条件は、 ５ｌ−Ａ）　Ｖ’全全体ついて消去できたＣＰの個数が
０である。

もしくは ５２）　　　Ｆの中にＣＰが存在しない。

の一方が成り立つ場合とする。（手順路り）本方°式に
よる具体的な符号と復号手順及び復号装置の構成の一例
を示す。

Ｌ＝３６．　　Ｍ＝３４．　　Ｎ±３２とし、ＧＬ（Ｘ
）＝（Ｘ　　ａ　’）　・（Ｘ　−ａつＧＭ　（Ｘ）　
−（Ｘ−ａ　’）　・（Ｘ−ａ　’）ＧＮ（Ｘ）−（Ｘ
　−ａ　０）　・（Ｘ　−ａ　’）とする。このとき、
ｔＬ＝ｔ、＝ｔ、＝１で、直方体Ｖは３６Ｘ　３４Ｘ　
３２の大きさで、Ｚ軸方向には　３４Ｘ３２木の符号Ｒ
５（３Ｂ、　３４．３）Ｙ軸方向には　３６Ｘ３２木の
符号Ｒ５（３４，３２，３）Ｘ軸方向には　３６Ｘ３４
本の符号Ｒ５（３２，３０，３）が構成される。各軸の
符号は、最大１個までの誤り訂正、もしくは最大２個ま
での消失訂正の能力を持つ。

この符号の総シンボル数は、 ３ｆｉ　ｘ　３４　ｘ　３２−３９１６８シンボル転送
できる情報量は、 ３４　ｘ　３２　ｘ　３０−３２６４０シンボル符号化
率（符号全体に対してパリティのシンボルの占める比率
）は、 １−（３２６４０／３９１６８）　＃０．１６７である
。

伝送路を通して誤りを加算された３９１８８個のシンボ
ルの復号な実行する復号装置の構成例を第２図に示す。

人力のシンボル系列Ｓは、順次、３次元メモリＶ′　に
書き込まれる。

Ｖ′は３８ｘ　３４ｘ　３２ｂｙｔｅの大きさの３次元
メモリで、Ｚ軸の座標にとＹ軸の座標ｉを指定すること
によって、Ｘ軸方向の３２ｂｙｔｅのデータｖ’　（ｋ
、ｆ、Ｏ）　ｓ＝　、ｖ’　（ｋ、ｉ、３１）がアクセ
スでき、同様に、Ｚ軸とＸ軸の座標ｋ。

ｊを指定することでＹ軸方向の３４ｂｙｔｅのデータｖ
’　（ｋ、ｏ、ｊ）　、・＝　、ｖ’　（ｋ、３３．ｊ
）がアクセスでき、同様に、Ｙ軸とＸ軸の座標ｉ。

ｊを指定することでＸ軸方向の３６ｂｙｔｅのデータｖ
’　（０，ｉ、ｊ）　、・−・、ｖ’　（３５，ｉ、ｊ
）がアクセスできるものとする。

ＣＰを格納する３　ｂｉｔのセルからなる直方体Ｆも３
６　ｘ　３４　ｘ　３２ｂｙｔｅの大台さの３次元メモ
リで、同様なアクセスができるものとする。

誤り検出器ＤＤｘは、ｔＨ＝ｎＸ＝１とし、誤り訂正は
行わず検出のみ行う。

０≦ｋ＜Ｌ、Ｏ≦ｉ＜Ｍなる全てのに、ｉについて、Ｘ
軸方向の符号ＲＳ　（３２，３０，３）の３２ｂｙｔｅ
のデータ ｖ’　（ｋ、ｉ、０）　、−−−、ｖ’　（ｉ、ｉ、３
１）を■′から読み出し、これに対して、Ｘ軸方向の符
号生成多項式Ｇ　Ｌ　（Ｘ）の値α０．α１を用いたシ
ンドロームＳ。ＸＩ　ｓｔｚを計算し、Ｓｏ、ｌ≠０ま
たはＳＩＸ≠０ であれば、直方体Ｆの座標 （ｋ、ｉ、０）、・・・、（ｋ、ｆ、３１）のセルに０
０１をｂｉｔ車位にｍｏｄ２加算する。

誤り検出ＤＤＹでも同様に、ｔ、＝ｎＹ＝１とし、０≦
ｋ＜Ｌ、０≦ｉ＜Ｎなる全てのに、ｉについて、Ｙ軸方
向の符号ＲＳ　（３４，３２，３）のシンドロームＳ。

７．Ｓ１アのどちらか一方が０でなければ、直方体Ｆの
座標 （ｋ、ｏ、ｊ）、・・・、（ｋ、３３．ｊ）のセルに０
１０をｂｉｔ単位にｚｏｄ２加算する。

誤り検出ＤＤｚでも同様に、ｔＬ＝ｌ’１２＝１とし、
０≦ｉ＜Ｍ、０≦ｊ＜Ｎなる全てのｉ、ｊについて、Ｘ
軸方向の符号ＲＳ　（３［ｉ、３４．３）のシンドロー
ムＳ。ｚ、　ｓｔｚのどちらか一方がＯでなければ、直
方体Ｆの座標 （０，ｉ、ｊ）、・・・、（３５，ｉ、ｊ）のセルに１
００をｂｉｔ単位にｍｏｄ２加算する。

ｖ′およびＦを構成するメモリ素子が十分に高速であれ
ば、誤り検出器ＤＤＫ　、ＤＤｙ　、ＤＤｚを並列に動
作させることができる。

誤り訂正器ＤＣＸＹ２ではｍ×＝ｍｙ　＝ｍｚ　＝０と
し、全てのＣＰの座標（ｋ、ｉ、ｊ）について、Ｘ、Ｙ
、Ｚの各軸方向に単一誤り訂正を行う。いうまでもなく
、「少なくとも２つの方向において誤り訂正に成功し、
かつ共に結果が合理的で、結果が一致する」場合に、そ
の結果を正しいものとして採用し、そのときには、Ｖ′
の誤り訂正とＦのＣＰの消去を行う。

前述の手順Ｄ　ＣｘＹ２−Ａを用いるとすれば、「誤り
訂正に成功し、かつ結果が合理的」である軸がただ１つ
しかない場合、その軸上のＣＰの個数が０か１であれば
、その軸の結果を正しいものとして採用する。

誤り訂正器ＤＣｘｙｚは％Ｆの全てのセルを順次走査し
て、そのセルがＣＰであれば、ＣＰの座標（ｋ、ｉ、ｊ
）に対応するＶ′の座標（ｋ、ｔ。

ｊ）で交差する３軸のデータ （３６−１）”　（３４−１）　＋３２−１００ｂｙｔ
ｅをＶ′から読み出し、各軸の符号を構成して、３通り
の単一誤り訂正を試みる。その結果によって、訂正が正
しく行われたと判断される軸について、Ｖ′に訂正結果
を書き込み、Ｆに００００データを書き込む。

前述のように、各軸の符号は最大２個までの消失訂正の
能力を持つ。そこで消失訂正器ＤＥｘｙｚは、Ｆの全て
のセルを順次走査して、そのセルがｃｐであれば、ｃｐ
の座標（ｋ、ｉ、ｊ）に対応するｖ′の座標（ｋ、ｉ、
ｊ）で交差する３ＩＩＩｌのデータ （３５−１）＋　（３４−１）　◆３２−１００ｂｙｔ
ｅをＶ′から読み出し、各軸の符号を構成して、ＣＰの
個数が２以下である軸について消失訂正を行い、その結
果を書き込む。消失訂正をＶ′全全体ついて、何回か繰
り返す場合には、下記の停止条件を満たせば終了する。

Ｓ１）　　交差するＸ、Ｙ、Ｚ方向のどれかの軸上にＣ
Ｐが存在する、Ｆの全ての座標 （ｋ、ｉ、ｊ）において、各軸上に３個以上のＰＣが存
在している。

もしくは Ｓ２）　　　Ｆの中にｃｐが存在しない。

［発明の効果］ ３次元に構成したＲｅｅｄ−５ｏｌｏｍｏｎ符号に対し
て、本発明復号方式を用いると、各軸方向には、パリテ
ィの数の少ない能力の低い符号を用いて、全体としては
、符号化率が等しく２つの各軸方向にはより多くのパリ
ティを持つ２次元積杆号よりも、高い訂正能力を実現す
ることができる。

例えば、実施例でのべた、各軸方向がＲｅｅｄ−５ｏｌ
ａｍｏｎ符号として最小のパリティ個数２で構成した３
次元符号 Ｒ５（３６，３４，３）　、Ｒ５（３４，３２，３）　
、Ｒ５（３２，３０，３）ですら、本復号方式を用いる
ことで、符号化率の等しい２次元積杆号で、パリティを
６個づつ付けた Ｒ５（６９，６３，７）、Ｒ５（６９，８３，７）や、
パリティを８個づつ付けた Ｒ５（９２，８４，９）　、Ｒ５（９２，８４，９）よ
りも訂正能力の高いことが確認されている。

また、本復号方式は、各軸方向のパリティが２以上とし
て、３次元に構成したＲｅｅｄ−５ｏｌｏｍｏｎ符号の
復号に通用できることは、実７ｉ籠例の説明により明ら
かであり、また、各軸を構成する符号が、Ｒｅｅｄ−５
ｏｌｏｍｏｎ符号以外の符号であっても適用できる。

【図面の簡単な説明】

第１図は、３次元の直方体形状の符号の構成図、 第２図は、復号装置の構成例を示す図である。

Claims (1)

1. 【特許請求の範囲】 １）各辺の長さが各々Ｌ、Ｍ、Ｎの直方体の形で、 長さＬの辺に平行なＭ×Ｎ個の単独な符号、長さＭの辺
   に平行なＬ×Ｎ個の単独な符号、および長さＮの辺に平
   行なＬ×Ｍ個の単独な符号 により構成され、全体として３次元形状をなす符号の復
   号において、 個々に誤りの存在が検出された３個の単独な符号が交差
   する点ＣＰを検出することを特徴とする誤り訂正符号の
   復号方式。 ２）各辺の長さが各々Ｌ、Ｍ、Ｎの直方体の形長さＬの
   辺に平行なＭ×Ｎ個の単独な符号、長さＭの辺に平行な
   Ｌ×Ｎ個の単独な符号、および長さＮの辺に平行なＬ×
   Ｍ個の単独な符号 により構成され、全体として３次元形状をなす符号にお
   いて、 ある点に交差する３方向の単独な符号の復号結果のうち
   で、少なくとも２つの復号結果については、個々には正
   しいと判断されるとき、これら少なくとも２方向の復号
   結果の交差する点における値が一致するならば、これら
   少なくとも２方向の復号結果の全体もしくは一部を正し
   いものとして採用することを特徴とする誤り訂正符号の
   復号方式。 ３）前記３次元形状の符号を構成するある単独な符号の
   復号を行った結果について、得られた誤りの位置が前記
   交点ＣＰのいずれかであるとき、復号結果を正しいもの
   とすることを特徴とする請求項１記載の誤り訂正符号の
   復号方式。 ４）前記３次元形状の符号を構成するある単独な符号の
   復号を行った結果について、得られた誤りの位置が前記
   交点ＣＰのいずれかであるとき復号結果を正しいものと
   する方式において、正しいとされるある単独な符号の復
   号結果について、さらに、この単独な符号上に存在する
   交点ＣＰの個数があらかじめ設定したある数値以下であ
   ることをもって、前記単独な符号の復号結果を正しいも
   のとすることを特徴とする請求項３記載の誤り訂正符号
   の復号方式。 ５）前記交点ＣＰにて交差する３方向の単独な符号につ
   いて、個々に復号を行い、 得られた３通りの復号結果について、 前記請求項２および３に記載の方式における意味で正し
   いとする少なくとも２方向の復号結果、 もしくは、 前記請求項４に記載の方式における意味で正しいとする
   ただ１つの復号結果、 のどちらか一方が存在するとき、 前記復号結果を前記直方体の該当位置に書き込むことを
   特徴とする請求項１記載の誤り訂正符号の復号方式。 ６）請求項１〜５のいずれかの方式において、正しいと
   判断してある単独な符号の復号結果を採用し、その復号
   結果を前記直方体の該当位置に書き込んだのちは、この
   単独な符号上に存在した交点ＣＰは、以降の復号では交
   点ＣＰではないとすることを特徴とする誤り訂正符号の
   復号方式。 ７）請求項１〜６のいずれかの方式の復号結果に対して
   、交点ＣＰを消失位置とみなし、個々の単独な符号に対
   して消失訂正を行うことを特徴とする誤り訂正符号の復
   号方式。 ８）請求項７の方式において、消失訂正に成功したある
   単独な符号上に存在した交点ＣＰは、以降の他の単独な
   符号に対する消失訂正では交点ＣＰではないとすること
   を特徴とする誤り訂正符号の復号方式。 ９）請求項７または８の方式において、前記直方体の全
   体にわたる消失訂正を繰り返すことを特徴とする誤り訂
   正符号の復号方式。 １０）請求項１〜９のいずれかの方式において、前記直
   方体の各辺の長さＬ、Ｍ、Ｎを等しくした符号を構成す
   ることを特徴とする誤り訂正符号の復号方式。