JPH01256228A - 誤り訂正符号化装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は誤り訂正符号の符号化装置に関する。

（従来の技術） 一定の有限体ＧＦ（２ｍＸｍは自然数）上の誤り訂正符
号をブロック符号として構成する場合、従来、−般には
Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号が用いられ
てきた。（詳しくは宮７１１．岩垂、今井による著書「
符号理論」（昭晃堂）に説明しである。） （発明が解決しようとする問題点） Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号はＧＦ（２ｍ）上の符号
長が高々２ｍ＋１までのＭＤＳ符号（最大分離符号）で
あり、従って、この符号長の範囲においては、他のいか
なる代数的線形ブロック符号よりも、一定の誤り訂正能
力を保証した上で、符号化比率を最大にするという意味
において、最良である。しかしながら、符号長が２ｍ＋
１を越える場合には、ＢＣＨ符号が用いられるが、その
場合の符号はＭＤＳ符号ではなく、符号長が長くなるに
つれて、一定の誤り訂正能力を満たすためには、付加す
べき冗長シンボルの割合を大きくしなければならないと
いう欠点を有していた。従って、長い符号長において、
ＢＣＨ符号の性能を上回る新しい符号の構成が必要であ
った。

（問題点を解決するための手段） 本発明ではＧＦ（２）上の符号を扱う場合とＧＦ（２ｍ
Ｘｍは２以上の整数）上の符号を扱う場合につき、符号
化装置の実現を与える。

本発明に従えば、以上の問題点を解決するためのＧＦ（
２ｍＸｍは２以上の整数）上の誤り訂正符号化装置は、
次のような特徴を有する装置によって実現できる（以下
、「発明１１）。すなわち、有限体ＧＦ（２ｍＸｍは２
以上の整数）上の情報シンボル列［ａｌ、ａ２゜８９１
０．、ａｋｌを入力として、該シンボル列と、後記ＧＦ
（２ｍ）上のｋ×ｎ個のシンボルを２次元的に記憶して
いる記憶装置から供給される、記憶領域内の縦方向の各
シンボル列ｒ１＝Ｅ世）１２戸）２．・・２戸）、］（
ｉ＝１．・＋　ｎ）との積和演算を行う回路と、該積和
演算回路からの出力シンボル列［ｃ、１．・・ｃｎｌｌ
の各シンボルに対し、前もって定められたＧＦ（２ｍ）
上の定数ｂ１．ｂ２．・・、ｂｎをそれぞれ掛ける掛け
算回路とから構成され、該骨は算回路の出力［ｂｌｃｌ
”　ｂ２ｃ２’ｔ　”””・ｐ　ｂｎＣｎ’］をＧＦ（
２ｍ）上のｎ桁の符号語として出力し、前記記憶装置に
おいては、記憶装置内の記憶領域がｋ×ｎの行列の形の
２次元配置の形をしており、しかも、該配列内の部分配
列として、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号の生成行列及
び各行がＲｅｅｄ−Ｓｏｌｏｍｏｎ符号の２つの生成行
列の行ベクトル同士のテンソル積を定数倍したものであ
る行列が含まれていることを特徴とする誤り訂正符号化
装置として実現される。

更に本発明に従えば、以上の問題点を解決するためのＧ
Ｆ（２）上の誤り訂正符号化装置は、次の特徴を有する
装置によって実現できる（以下、［発明２］）。すなわ
ち、第１及び第２の誤り訂正符号化回路を縦属し、第１
の誤り訂正符号化回路の出力を第２の誤り訂正回路で符
号化した結果を符号語として出力する誤り訂正符号化装
置において、第１の符号化回路は、有限体ＧＦ（２ｍＸ
ｍは２以上の整数）上の情報シンボル列［ａｌ、　ａ２
．・・、ａ、１を入力として、該シンボル列と、後記Ｇ
Ｆ（２ｍ）上のｋ×ｎ個のシンボルを２次元的に記憶し
ている記憶装置から供給される、記憶領域内の縦方向の
各シンボル列ξ＝［ｐｉ）１、　ｐｉ）２．・・。

ｆ”ｈ］（ｉ＝１．・・・、ｎ）との積和演算を行う回
路と、該積和演算回路からの出力シンボル列［ｃｌｏ、
・・、ｃｎ″］の各シンボルに対し、前もって定められ
たＧＦ（２ｍ）上の定数ｂ１．ｂ２．・・ｌｂｎをそれ
ぞれ掛ける掛け算回路とから構成され、骸骨は算回路の
出力［ｂｌｃ、’、　ｂ２ｃ２’ｌ・・。

ｂｎｃｎ’］をＧＦ（２ｍ）上のｎ桁の符号語として出
力し、前記記憶装置においては、記憶装置内の記憶領域
がｋ×ｎの行列の形の２次元配置の形をしており、しか
も、該配列内の部分配列として、Ｒｅｅｄ−Ｓｏｌｏｍ
ｏｎ符号の生成行列及び各行がＲｅｅｄ−Ｓｏｌｏｍｏ
ｎ符号の２つの生成行列の行ベクトル同士のテンソル積
を定数倍したものである行列が含まれていることを特徴
とする誤り訂正符号化回路であり、第２の符号化回路は
、線形誤り訂正符号の符号化回路であることを特徴とす
る、誤り訂正符号化装置によって実現される。

（作用） １本発明の符号化装置によって、ＢＣＨ符号の性能を上
回る符号が生成できることを見るために、本発明の符号
の発生原理について触れる。以下では、符号を定義する
体をＦ−ＧＦ（２ｍ）とし、正の整数ｅは（２ｍ／２＋
１）を割り切るものとし、ｔ＝　（２ｍ　−１）／ｅと
する。今、２次元射影空間（比の値が意味を持つ３変数
の空間、即ち、（ｘ：ｙ：ｚ）と（ａｘ：ａｙ：ａｚ）
（ａ≠０）は同じ点を表すものと見なす空間）の中に埋
め込まれたＦｅｒｍａｔ型の曲線 Ｘ、＝（（ｘ：ｙ：ｚ）；ｘ’＋ｙ’＋ｚ’＝０）　　
　　　　　　　　（１）を固定する。このときのＸ汁特
ｉ教付る幾何学的特徴量である種類ｇは以下で与えられ
る。

ｇ＝（ｅ−ＩＸｔ’−２）／２　　　　　　　　　　　
　　　（２）また、Ｘ、上の点の中で、その座標が全て
Ｆの元で表される点（Ｘ、のＦ−有理点とよぶ）は有限
個存在し、αをＦの原始根であるとすると、それらは次
のような座標値をもった点として与えられる。（全部で
ｎ＋１１固とする） Ｑ＝（１：Ｏ：１） Ｐ□＝（０：ａ＝”ｔ：１）　　（ｉ＝１．−・−、ｅ
）Ｐ１＝Ｃａ（’−１）”：Ｏ：１）　　（ｉ＝ｅ＋１
．・、２ｅ−１）Ｐ、＝（１：ａ（ｉ−２ｆｆｌｔ：Ｏ
）　（ｉ＝２ｅ、−，３ｅ−１）１２ｐ＋ｔＨ＋に−ｔ
２＋２ｔ＝（”Ｈ十０−１）”：Ｑ’ｐ”ｋｌ）ｔ：ｌ
）　　　　　（３）（：）＝１．−、ｅ、に＝１．・、
ｅ、ｙ＝１．−、ＩＵ（、，１（γｐ＋　８．）　（Ｉ
ｎｄ　Ｕ（ｒｒ１、）但し、Ｉｎｄ　Ｕ（ｍ１、＝（（
名ｘ）：（δ１α勺（Ｕ（ｍ、　Ｚ））Ｕ（ｍ、　り　
＝　（（ξ＋　ｒｌ）＝Ｆ、”Ｑ’＝’　Ｅ＋　ｒｌ（
（α＋　”’＋　αｔ−”）、）であるとする。以下、
Ｘ、の各Ｆ−有理点は（４）のように順番付けられてい
るものとする。この中の一点Ｑ＝（１：０：１）を取り
出して、 Ｌ（δＱ）　＝　（Ｑで高々δ位の極をもつＸ、上の有
理関数）を定義すると、これは、基底が以下のように考
えられるＦ上のに＝δ−ｇ＋１次元の線形空間である。

δ＝８１ｅ＋６２（δ１．δ２（Ｎ、　０≦８２≦１！
−ＩＸＮは自然数）とおき、δ１≧ｔを仮定すると （δ２＝０の場合） Ｓ０＝（ＸａｙｂｚＣ：０≦ａ、ｂ≦δ０，０≦Ｃ≦ｅ
−１゜ａ＋ｂ＋ｃ＝８１） Ｓｏ＼（２δ１）＝（φ１−　”＝−勉−Ｊ　　　　　
　　　　　　　（５）Φ。＝　（ｘ　＋　ｚ）δｌ とすると、 ψｏ＝１．ψ１＝Φ、／Φ０．・・、甲に一１＝Φ、・
１１Φｏ（６）Φｏ＝　（ｘ　＋　ｚ）δ１ がＬ（δＱ）のＦ−基底である。

（１≦６２≦ｅ−１の場合） Ｓ、　＝　（ｘ”ｙｂｚＣ：０≦ａ、ｂ≦δ１，０≦Ｃ
≦ｅ−１，ａ＋ｂ＋ｃ＝８１）Ｓ２＝（ｘａｙｂ：ｅ−
δ２≦ｂ≦ｅ−１，ａ＋ｂ＝６１＋１）８１＼（２δ１
）＝（Φ１．　＋＋＋−＋、Φｌ５ＩＩ−１）’　５２
＝（φｌｓ＋ｌｔ　・・”’＋φｈ−ｔ）　　　（７）
φｏ＝（Ｘ十ｚ）６１．Φｏ＋＝φ。（ｘ＋ｚ）とする
と、 甲０”’ｌ’Ｆ１”ΦｌｌΦＯ＋　”””ｔ　ＷＩＳｌ
ｌ−１＝Φｌｓ＋ｌ−１’Φ０ＶｌＳ、ｌ＝φｌｓ＋ｌ
’φ。、”・・、更、・１＝φ、・１７φ。′（８）が
Ｌ（δＱ）の基底をなす。

そこで、Ｌ（δＱ）の元に対して、（３）の座標をもつ
点（Ｐｌ、　Ｐ２．６．、　Ｐｏ）の値をそれぞれ代入
してｎタプルのＦの元の組を対応させる写像 φ：Ｌ（δＱ）−べＦ）ｎ ｕｌ　　　　　　　　ｕＪ　　　　　　　　　　　（９
）ｆ・縁ｆ（Ｐｌ）、　・・、ｆ（Ｐｎ））・符号語の
像を符号語すると、０くδくｎの下では上の写像甲は線
形かつ１対１であるがら、甲の像ＩｍψはＦ上の線形符
号の空間をなし、この符号空間の基底は、φ呻。）、・
・、Φ（甲、　、）　　　　　　　　　　　　　（１０
）で与えられるので、これらを並べて出来る生成行列は Ｍ＝［Φ（甲。）Ｔ、・・、Φ（も・、）Ｔ］Ｔ　　　
　　　　　　　　　（１１）の形で書ける（Ｔは転置を
表す）。また、Ｍは次のような２つの行列の積に分解さ
れる。

Ｍ＝ＡｘＢ　　　　　　　　　　　　　　　　　（１２
）但し、Ａは第１図（ａ）、（ｂ）に示すような（行列
の上半分を第１図（ａ）、下半分を第１図（ｂ）に表示
した）ような簡単な一般形をもつｋ×ｎ行列であり、形
式的には、符号長がｅのＲｅｅｄ−Ｓｏｌｏｍｏｎ符号
の生成行列及びこの行列から符号長の短縮にともなって
列ベクトルを削除したもの、及びこの行列から最初の６
１−ｅ＋１本と最後のｅ−６２−１本を除いたもの、及
びその行ベクトルのテンソル積を行列要素として部分的
に含むことを特徴とする。行列Ｂは、第１番目の対角要
素す、（ｉ＝１．・・、ｎ）が次のような値をとるｎ×
ｎの対角行列である。

ｂ、＝　１／Φｏ（Ｐｌ）（ｉ＝１．・・、ｎ）（１４
）また第１図の記号において、 Φｏ＝　（ｘ　＋　ｚ）６１　　Φｇ’＝（ｘ＋ｚ）８
１＋ｔψＱ　”　’ｒ　ＸＰｌ　＝　Ｘ’１／Φ０．ψ
２＝Ｙ５１／Φ０．ψ＝−１／ΦＯＷ、：　（ｙｂｚｃ
／Φｏ：ｂ＋ｃ＝δ１．　ｂ、　ｃは整数、ｂ＞ｏ。

０＜ｃ≦ｅ−１） ＶＢ＝　（Ｘ”Ｚｃ／Φｏ：ａ＋Ｃ＝δ１．ａ、Ｃは整
数、ａ＞０゜０＜ｃ≦ｅ−１） Ｗｃ　＝　（ｘａｙｂ／Φ。：ａ　＋　ｂ　＝δ１．　
ａ、　ｂは整数、　ａ＞０．　ｂ＞０）ＶＤ　＝　（ｘ
ａｙｂ／Φ６’：ａ　＋　ｂ　＝δ、＋１．ａ、ｂは整
数、ａ＞０．ｂｏｏ）ψＢ＝（ｘａｙ５ｚｃｌΦｏ：ａ
　＋　ｂ　＋　ｃ　＝δ１．　ａ、　ｂ、　ｃは整数。

ａ＞Ｏ，ｂ＞０．０＜ｃ≦ｅ−１） ａ＝［１，ａａｔ、　””’、　ａ’ζ−ｔ）ａｔｌ（
（ＧＦ（２ｍ））’””［Ｌ　αｂｔ＋　・・’ｐ　α
（’・”ｂｔ］（（ＧＦ（２ｍ））’ａ１３１ｂ＝＝　
［１，ｑｂｔ、　１、１、１、　（１（ｅ　−１）ｂｔ
、　ａａｔ［ｌ　、　ｑｂｔ、　１、１、１、　ｑ（ｒ
　　１）町。

、・１、１、　α（Ｃ−１）ａｔ（１，ａｂｔ、　１、
・・、　ａ（ｅ−１１ｂ用（（ＧＦ（２ｍ））’ｔ＝（
２ｍ−１）／ｅ、　ａはＧＦ（２ｍ）（７）原始根Ｕ＜
ｍ、ｔ＋　＝　（伍＋　Ｑ）：ξＣ＋ｒＩＣ＝１ξ＋　
Ｑ（（α＋　”””ｔ　”　’）ｙ　）ＩｎｄＵ（１、
、）＝（（λ、１１）：（αλ、α）Ｉ）”（ｍ、０）
’ＰＡＩ　ＷＢ＋　ｔＩ／。＋　ＷＤＩ　’ＦＢの各元
は添え字ａ、　ｂ、　ｃの順に辞書式順序で並べられて
いるとする。第１図の一番左側の列は生成行列の各行ベ
クトルがＬ（δＱ）のどの基底に対応しているかを示し
ている。但し、δ２＝ｏの場合には甲。に対応する行が
全て削除される。また、最上段は生成行列の各列ベクト
ルがＰ・曲１＋　　　　＋ Ｐ　（（３）参照）の中のどの点に対応しているかを示
している。第１行の要素であるΦ。は各列に対し、Φ。

（Ｐ４Ｘｉ＝１．・・、ｎ）の意味である。また、第１
図において、［０］は要素が全て０の行列を表し、［Ｑ
ｔｌ゛、　［αＬ１・・。

などは、第１０図に示されたとおりである。

また第１０図において、（Ａ、　Ｂ１Ｘ１＝１．・・、
　Ｎｘ）はＩｎｃｂｐ、＝　（（ａ、　ｂ）：ｘ”ｙｂ
ｚＣ／Φｏ（ｙ、）（ｘ　＝Ａ＋　Ｂｔ　Ｃ＊　Ｄ＋　
Ｅ）の元全体を動く数の組とする。（Ｎｘ＝　１Ｉｎｄ
ψｘ１．Ｘ＝Ａ、Ｂ、Ｃ９Ｄ。

Ｅ） また、（λ１、ｐ、）（ｉ＝ｌ、・・、　５＝ｌＩｎｄ
Ｕ（、，１）（ＩｎａＵ（１、とする。本発明は、上述
のような符号を具体的に発生させる装置の実現を示した
ものである。こうして生成される符号（Ｆｅｒｍａｔ型
の曲線より生成されるので、以下、Ｆｅｒｍａｔ型の符
号とよぶ）のパラメータは代数幾何学におけるＲｉｅｍ
ａｎｎ　−Ｒｏｃｈの定理から次のように導かれる。

符号長　ｎ　＝２ｍ＋（ｆｆ−ＩＯｆｆ−２）・２ｍ／
２情報記号数　ｋ＝δｅ−Ｃｅ−ＩＸ（−２）／２＋　
１最小距離　ｄ≧ｎ−δ　　　　　　　　　　　　（１
５）本発明１はかくなる性能を有するＦｅｒｍａｔ型の
符号を実際に生成する装置を具体的に与えているところ
に新規性があり、後述するように、こうして生成された
符号が実際にＢＣＨ符号の性能を上回ることを保証する
ものであるところに進歩性がある。

また、符号長が（１５）と異なる場合、即ち、（３）で
示されている座標をもつＸｅのＦ−有理点の中で、符号
の位置を指定するのに用いられない点が存在する場合に
は、Ａの行列の列から用いられないＦ−有理点に対応す
る列を除くことによって上と同様な議論が成立する。こ
の場合には、符号長は短縮されて（１５）の値よりも少
なくなり、その値を改めてｎとする。

Ｆｅｒｍａｔ型の符号の具体的なパラメータの値を（１
５）から導き出すと、例えば、ｍ＝６．（＝９．δ＝３
８２とすると、（符号長、情報記号数、最小距離）＝（
５１２，３５５゜１３０）であり、この場合、３５５１
５１２＝０．６１５２の符号化率が達成されるのに対し
て、ＢＣＨ符号では同一符号長と最小距離に対して情報
記号数＝２６０であるがら、符号化率は２６０１５１２
＝０．５０７８であり、Ｆｅｒｍａｔ型の符号の方が同
一の誤り訂正能力の下でより高い符号化率を得ているこ
とが分かる。Ｆｅｒｍａｔ型の符号としてかくなる高性
能符号を生成できる理由は、ＢＣＨ符号ではＧＦ（２ｍ
）を定義体とするときに、２ｍ＋１の符号長しか獲得出
来ないのに対して、（１５）に示されているようにＦｅ
ｒｍａｔ型の符号ではＧＦ（２ｍ）を定義体として最大
２ｍ＋（ｅ−ＩＸｅ−２）−２ｍ／２だけの符号長を獲
得できることに依る。

次に、以上に述べた符号化を実現する回路を第１の符号
化回路として、この回路の出力である、ＧＦ（２ｍ）上
のＦｅｒｍａｔ型の符号の符号語（ｃＩｔ　”ｌｔ　”
””ｅｃｎ）の各シンボルｃｉ（ｉ＝１．・・、ｎ）を
２進ｍ桁展開し、ｃ、（ｉ＝１．・・、ｎ）の各２進ｍ
桁展開をｃ、＝［ｖ（ｉ）１．・・、　ｖＱ）ｍ］　　
（ｉ＝ａ、・・、ｎ）　　　　　　　（１６）とすると
き、これらに前もって用意された２元線形符号のｍ　Ｘ
　ｈ（ｈはｍより大きな正の整数）の生成行列Ｗを左か
ら掛けることに相当する符号化回路を第２の符号化回路
として、この符号化回路の出力としての２元符号語をｗ
ｉ（ｉ＝１．・・、ｎ）とし、各要素をｗ（′）、（ｊ
：＝：　１　＋・・、ｈ）とかくことにする。

ｗｉ＝　［ｗ”１．　・・、　ｗ（ｉ）ｈ］　＝　［ｖ
”１．　・・、　ｖ（ｉ）ｍＩＷ（ｉ＝１．・・、ｎ）
　　（１７） そこで、Ｗｌ、　ｗ２．　’・・、　ｗｎ’Ｇ：この順
に並べて得られる、符号長がｎｈの２元符号語 ［ｗｌ、ｗ２．・・、ｗｎ］ ＝［ｗ”１１．・、ｗ（１）１、・・、ｗ（”）１．・
、ｗ（ｎ）ｈ］　　　（１８）を作ると、Ｗを生成行列
とする２元符号が符号長＝ｈ 情報記号数；ｍ 最小距離＝ｄ　　　　　　　　　　　　　　　（１９）
であるときに、（１８）の形で得られる２元符号のパラ
メータは、（１５）と（１９）が 符号長　Ｎ　＝　ｎｈ 情報記号数　Ｋ＝ｋｍ 最小距離　Ｄ≧（ｎ−に−ｇ＋１）ｄ　　　　　　　　
（２０）で与えられる。発明２は、（１８）の形で得ら
れる符号を具体的に発生させる装置の実現を示したもの
である。発明２は（２０）の性能を有する２元符号をＦ
ｅｒｍａｔ型の符号を発生する上述の第１符号化回路と
第２の符号化回路を用いて実際に生成する装置を具体的
に与えているところに新規性があり、後述するように、
こうして生成された符号が実際に２元ＢＣＨ符号の性能
を上回ることを保証するものであるところに進歩性があ
る。

例えば、上の議論において、外部符号の構成に際し、定
義体をＦ＝ＧＦ（２６）、発生の底とする代数曲線をＦ
ｅｒｍａｔ曲線Ｘ、（（＝９．　ｇ＝２８）に選ぶと、
Ｘ、のＦの有理点の総数は、５１３であるが、その中の
任意の４００点を符号の位置を指定する為に用いること
にして、さらにδ＝１９４であるように定めると、第１
回路によって出力されるＦｅｒｍａｔ型の符号について
（符号長、情報記号数、最小距離）＝　（４００，２３
３，１４０）であることが保証される。

これに以下の生成行列を有する（７．６．２）符号を先
に述べた方法によって連接して得られる２元符号の性能
は、（２０）から、（符号長、情報記号数、最小距離）
＝（２８００，１４０２，２８０）であることが保証さ
れる。

従って、この場合の検査記号数は ２８００−１４９２　：１３０８であるが、同じ符号長
と最小距離を有するＢＣＨ符号の検査記号数は１４９３
であり、本発明による符号の方が同一の符号長と誤り訂
正能力の下で付加すべき冗長ビット数が少ないという意
味で、優れた性能を有することがわかる。

（実施例） 発明１の符号化を実現する回路の例を示したのが、第２
図、第３図、第４図である。ＧＦ（２ｍ）上の情報シン
ボル列［ａｌ、　Ｃ２，・・ｐ　ａＪに（１３）の生成
行列Ｍを左から掛けることによってＧＦ（２ｍ）上の符
号語ＥＣ□、ｃ２．・・。

ｃｎ］を作る過程を、（１３）の分解に応じて、［Ｃ１
’Ｉ　Ｃ２’？　””’ｌ　Ｃｎ’ｌ　＝　［ａｌ　ｒ
　Ｃ２’＋　””’ｓ　ａＪＡ　　　　　　　　（２２
）［ｃｘｃ２．　・・、　ｃｎ］　＝　［ｃ１’、　ｃ
２’、・・、Ｃｎ１１Ｂ”　［ｂｔｃｔ’、　ｂ２ｍ２
’ｌ　”””ｐ　ｂｎｃｎ’］　　　　　（２３）のよ
うに２つの過程に分割して行うものとする。第２図は（
２２）を実現する第１の符号化回路と（２３）を実現す
る第２符号化回路からなることを示している。第３図は
（２２）を実現する第１符号化回路である。第１符号化
回路は、情報記号列ｆａ１．　Ｃ２，・・、ａ、１をａ
１、ａ２、　”００．の順に入る入力として、該入力列
と、制御信号の指示に従って、記憶装置からｆ工、ｆ２
．・・’）ｆｎの順に送り出されるＧＦ（２ｍ）上のベ
クトルミニ囮１．・・凌）、］　（ｉ＝Ｌ・・、ｎ）　
　　　　　　（２４）との積和 ｃｆ’＝ａ１ｆ”１＋・・＋ａ、ｆ（Ｄ、　　（ｉ＝１
．・・、ｎ）　　　　　（２５）を積和回路で計算して
、ｃ、１．　Ｃ２１，・・・ｃ、１の順に出力する。こ
こに、積和回路には通常よく知られているＧＦ（２ｍ）
上の乗算器と加算器がそれぞれに個と（ｋ−１）個備え
られているものとする。但し、記憶装置にはＧＦ（２ｍ
）上の元が図１のように行列の形で２次元的に配列され
ており、ξは図１のＡの第１列目の列ベクトルを転置し
たものである。本発明では、該記憶装置における要素の
配列が第１図に示されているように、符号長がｅのＲｅ
ｅｄ−Ｓｏｌｏｍｏｎ符号の生成行列 及びこの行列から符号長の短縮にともなって列ベクトル
を削除したもの、及びこの行列から最初の８１−／＋１
本と最後のｅ−８２−１本を除いたもの、及びその行ベ
クトルのテンソル積を行列要素として部分的に含むとい
う特徴を有する。第４図は（２３）を実現する回路であ
る。Ｃ１’、　Ｃ２ｍ、・・をこの順の入力として、制
御信号により作動するスイッチによって切り替えながら
ｎ個の乗算器を用いて、Ｃ１＝ｂ１ｃ１’。

Ｃ２＝ｂ２ｃ２’、　＋＋＋を計算し、該骨は算結果を
０１＋０２．”’＋Ｃｎ１７）順に出力する。

発明２の符号化を実現する回路の例を示したのが、第５
図から第９図である。第５図は回路の全体が、ＧＦ（２
ｍ）上のＦｅｒｍａｔ型の符号を出力するとすることを
特徴とする第１の符号化回路と２元線形符号化回路であ
ることを特徴とする第２の符号化回路からなることを示
している。全長がｍｋビットの２元情報記号列［ａｌｔ
ａ２＋・・、ａｍｋｌを全体の回路に対する入力として
、第１の符号化回路はこれをｍ個毎に区切って、 ｒａｌｌ　８２．　””’ｊ　ａｍｋｌ　＝　［ａｌ’
）　Ｃ２’ｌ　”・・”ｌ　ａｋ’１ａｊ’＝（ａリ−
１）ｍ＋１＋　ａ（ｊ−１）ｍ＋２ｊ　””’ｔ　ａ（
ｉ−１）ｍ＋ｍ１ｑ＝１．・・、　ｋ）　　　（２７） とし、各ａ３’（１）＝１ｔ・・、ｋ）をＧＦ（２ｍ）
の前もって設定された多項式基底に関する２進ｍ桁展開
と見なすことにより、ＧＦ（２ｍ）上の元として捉え、
従って、ＧＦ（２ｍ）上のに次元ベクトル（ａｌｔ、　
Ｃ２１，１、１、１、ａ、Ｉ］を改めて第１の符号化回
路の入力として、これをｎ桁のＧＦ（２ｍ）上の符号語
［ｃ１、Ｃ２，・・、　ｃｎ］に変換する。第２の符号
化回路は、［ｃｌ、Ｃ２，・・、Ｃｎ］の各シンボルｃ
、（ｉ＝１．・・、ｎ）を（２７）の展開に用いた基底
に関して２進ｍ桁展開し、ｃｉ（ｉ＝１．・・、ｎ）の
各２進ｍ桁展開をｃ、＝［ｖ”１．・・、ｖ（ｉ）ｍ］
　　（ｉ＝１．・・、Ｈ）　　　　　　　（２８）とす
るとき、これらをｃｌ、Ｃ２，・・の順に入力として、
それぞれｈ桁の２元符号語ｗ、＝［ｗ（Ｄｏ、・・。

Ｗ（ｉ）ｈ］（ｉ＝１．・・、ｎ）に変換し、ｗ１、　
ｗ２．・・、Ｗｎをこの順に出力する。その結果、符号
長がｎｈの２元連接符号語［Ｗｌ、Ｗ２．・１、、　ｗ
ｎ］＝［ｗ（１）１．　、・・、Ｗ（１）ｈ、・・・、
Ｗ（ｎ）１．・・。

ｗ（ｎ）、］を回路全体の出力とする。第６図は、上述
の（２６）、　（２７）で与えられるようなＧＦ（２）
上のｍｋ桁の情報記号列をＧＦ（２ｍ）上のに桁の情報
記号列に変換する回路（変換装置）と、ＧＦ（２ｍ）上
の入力情報シンボル列［ａｌｔ、　Ｃ２１，１、・・１
、　ａ、ｌ］に、（１３）の生成行列Ｍの分解に応じて
、 ［Ｃ１’ｐ　Ｃ２１，・・’ｐ　ａｋ’］Ａ　”　［ｅ
ｌ’＋　Ｃ２’）”’・ｇ　ｅｎ’］　　　　　　（２
９）を実現してＧＦ（２ｍ）上の［ｃｌ’）　０２’ｓ
　’”・・・ｔ　ｃｎ’］を算出する第３の符号化回路
と、 ［ｃ１、　Ｃ２，・・、　ｃｎ］　＝　［Ｃ１’、　Ｃ
２’、・・、　ｃｎ’ＩＢ”［ｂｌｃ１’＋　ｂ２ｃ２
’、　・・”＋　ｂｎｃｎ”　　　　（３０）を実現し
てＧＦ（２ｍ）上の［ｃ１、Ｃ２，・・、　ｃｎ］を算
出する第４の符号化回路からなることを示している。第
７図は、第３の符号化回路を示している。第３符号化回
路は、情報記号列［ａ□、Ｃ２，・・、ａＪをａｌ、Ｃ
２，・曲の順に入る入力として、該入力列と、制御信号
の指示に従って、記憶装置からｆｌ、ｆ２．・・ｌ　ｆ
ｎの順に送り出されるＧＦ（２ｍ）上のベクトル ｆ１＝［ｆＣｌ）１．・・２戸）ｋ］（ｉ＝１．・・、
ｎ）（３１）との積和 Ｃ討ａ１「ｉ）１＋・・＋ａｋｆｔｉ）ｋ（ｉ＝１．・
・、ｎ）（３２）を計算して、この順に出力する。但し
、記憶装置にはＧＦ（２ｍ）上の元が第１図のように行
列の形で２次元的に配列されており、ｆｌは第１図のＡ
の第１列目の列ベクトルである。本発明では、該記憶装
置における要素の配列が第１図に示されているように、
符号長がｅのＲｅｅｄ−Ｓｏｌｏｍｏｎ符号の生成行列
及びこの行列から符号長の短縮にともなって列ベクトル
を削除したもの、及びこの行列から最初の６１−ｅ＋ｉ
本と最後のｅ−８２−１本を除いたもの、及びその行ベ
クトルのテンソル積を行列要素として部分的に含むとい
う特徴を有する。第８図は第４の回路を示している。ｃ
、１．　ｃ２１．・・・０．をこの順の入力として、制
御信号により作動するスイッチによって切り替えながら
ｎ個の乗算器を用いて、ｃ１＝ｂ１ｃ、’、　（２＝ｌ
）２（２’、・・を計算し、該骨は算結果をこの順に出
力する。第９図は第２の符号化回路が、上述の（２８）
で示したように、ｃ、（ｉ＝１．・・、ｎ）の各２進ｍ
桁展開をｃ、＝［ｖ（ｉ）１．・、ｖｃＤｍｌ（ｉ＝１
．・・＋ｎ＞　　　　　　（３３）と表したとき、ｃｌ
に左からｍＸｈの２元符号の生成行列を掛けて、ｈ桁の
２元符号語を作ることに相当する回路からなることを示
している。後者の回路においては、各ｃ、（ｉ＝１．・
・、ｎ）について、制御信号により作動するスイッチに
よって、記憶装置からｇｌ＋ｇ２＋・・５ｇｈの順に送
り出されるＧＦ（２）上のベクトルｇｊ＝［ｇψ１．”
”’、ｇ”ｍ］　　（ｊ＝１．＝・、ｈ）　　　　　　
　（３４）との積和 ｗ（ｉ）ｊ＝び：）１ｇｏ）１＋・・＋ｖ（ｉ）。ｇＧ
）。

θ＝１．・・、ｈ）　　　　（３５） を制御信号の指令によって作動する積和回路で計算して
、Ｗ（ｉ）Ｗ（ｉ）・・・、Ｗ（ｉ）ｈのｊ頃に出力す
る。ここ１２　　２ツ に、積和回路には通常よく知られているＧＦ（２）上の
乗算器と加算器がそれぞれｍ個と（ｍ−１）個備えられ
ているものとする。但し、記憶装置にはＧＦ（２）の元
が２元線形符号の生成行列の形で２次元的に配列されて
いるものとし、ｇ、は該２次元配列の第３列目の列ベク
トルを転置したものに相当する（例（２１））。以上の
演算は制御信号によって作動するスイッチによってレジ
スタの出力がｃｌ、ｃ２．・・の順に切り替えられなが
ら進行し、各ｉに対する出力を ｗ、＝［ｗ（Ｄｌ、・・、ｗ（ｉ）、］　　（ｉ＝１．
・・、ｎ）　　　　　（３６）とするとき、Ｗ□２ｗ２
２０００１１ｗｎはこの順に第２の符号化回路から出力
され、結局、［ｗ（１）１．・・２ｗ（１）ｈ、・・・
。

ｗ”ｌｏ、・・、Ｗ（ｎ）、］が筋桁の２元符号語とし
て出力される。

（発明の効果） 発明ｌによって与えられるＦｅｒｍａｔ型の符号の持つ
性能を調べ、それを従来用いられてきたＢＣＨ符号の性
能と比較した結果を以下に示す。

表１はＦ＝ＧＦ（２ｍ）（ｍ＝４．６．８．１０．１２
）の上に構成されるＢＣＨ符号及び本発明によるＦｅｒ
ｍａｔ型の符号のパラメータを比較したものである。ｑ
は符号の属する体の大きさ、ｎは符号長、ｄは最小距離
、ｒｌはＢＣＨ符号に関する検査記号数、ｒ２はＦｅｒ
ｍａｔ型の符号に関する検査記号数、ｅは符号発生の底
となる（１）で定義されるｐｅｒｍａｔ曲線の次数を表
す。−７−４゜（以及塗白） 表１１発明１の符号とＢＣＨ符号の性能比較表から分か
るように、ＧＦ（２４）上の符号で、２４＋１＝１７を
越えた符号長ｎ＝６４を有する符号を構成する際に、一
定の誤り訂正能力（７シンボル訂正、最小距離＝６４）
の下ではＢＣＨ符号を用いると、冗長シンボルを２９シ
ンボル付加しなければならないのに対し、本発明による
Ｆｅｒｍａｔ型の符号を用いた場合は、冗長シンボルを
２１シンボル付加するだけで済む。よって、この場合、
本発明によるＦｅｒｍａｔ型の符号の方が、ＢＣＨ符号
よりも優れた性能を示していることがわかる。この事情
は、表中の他のパラメータに対しても言える。

発明２の装置によって与えられる２元符号の持つ性能を
調べ、それを、従来一般的に用いられてきたＢＣＨ符号
の性能と比較した結果を以下に示す。

表２はＢＣＨ符号のパラメータと本発明による符号のパ
ラメータを比較したものである。Ｎは符号長、Ｄは最小
距離、ｒｌはＢＣＨ符号の検査記号数、ｒ２は本発明で
与えられる２元符号の検査記号数を表す。

ｍは本発明の第１符号化を行うときの定義体をＧＦ（２
ｍ）とするときのｍ、ｈは同じく第２の符号化の符号長
、ｄは第２の符号化の最小距離、ｅは第１の符号表２０
発明２の符号とＢＣＨ符号の性能比較表から分かるよう
に、符号長が２８００の２元符号を作る際に、一定の誤
り訂正能力（１４９ビツト訂正、最小距離＝３００）の
下では、ＢＣＨ符号を用いると、検査記号数が１６０１
ビツト必要で、このときの符号化比率が（２８００−１
６０１）／２８００　＝　０゜４２８１であるのに対し
、本発明による２元符号を構成するのに必要な検査記号
数は１４６２ビツトであり、 （２８００−１４６２）／２８００　＝　０．４７７９
の符号化率が達成される。従って、この場合にはＢＣＨ
符号よりも、本発明によって構成される２元符号の方が
優れた性能を有することがわかる。この事情は同表の別
のパラメータに関しても言えることが出来て、２１００
以上の長い符号長の下では、本発明によって生成される
２元符号の性能はＢＣＨ符号のそれを大幅に改善してい
る。

表２のパラメータを与える連接符号については、いずれ
も内部符号として（符号長、情報記号数、最小距離）＝
（７，６，２）の２元符号を用いている。該内部符号は
（２１）の形の生成行列を有子る符号として実現できる
。表に与えたパラメータの値以外の値に対しても、本発
明の２元連接符号によって、ＢＣＨ符号の性能を上回る
ものが構成できることに留意する。

【図面の簡単な説明】

第１図はＦｅｒｍａｔ型の符号の生成行列Ｍを（１２）
のように分解した場合の行列Ａの一般形を示し、本発明
にかかわる記憶装置の要素の配列を示している。 第２図は本発明１の符号化装置の全体図、第３図は発明
１の符号化装置の中の第１の符号化回路を示す図、第４
図は発明１の符号化装置の中の第２の符号化回路を示す
図、第５図は発明２の符号化装置の全体図を示す図、第
６図は発明２の符号化装置の中の第１の符号化回路を示
す図、第７図は発明２の符号化装置の中の第３の符号化
回路を示す図、第８図は発明２の符号化装置の中の第１
の符号化回路を示す図、第９図は発明２の符号化装置の
中の第１の符号化回路を示す図、第１０図は、第１図の
詳細を示すための図である。

Claims (1)

1. 【特許請求の範囲】 １、有限体ＧＦ（２＾ｍ）（ｍは２以上の整数）上の情
   報シンボル列［ａ＿１、ａ＿２、・・、ａ＿ｋ］を入力
   として、該シンボル列と、後記ＧＦ（２＾ｍ）上のｋ×
   ｎ個のシンボルを２次元的に記憶している記憶装置から
   供給される、記憶領域内の縦方向の各シンボル列ｆ＿ｉ
   ＝［ｆ＾（＾ｉ＾）＿１、ｆ＾（＾ｉ＾）＿２、・・、
   ｆ＾（＾ｉ＾）＿ｋ］（ｉ＝１、・、ｎ）との積和演算
   を行う回路と、該積和演算回路からの出力シンボル列［
   ｃ＿１′、・・、ｃ＿ｎ′］の各シンボルに対し、前も
   って定められた ＧＦ（２＾ｍ）上の定数ｂ＿１、ｂ＿２、・・、ｂ＿ｎ
   をそれぞれ掛ける掛け算回路とから構成され、該掛け算
   回路の出力［ｂ＿１ｃ＿１′、ｂ＿２ｃ＿２′、・・、
   ｂ＿ｎｃ＿ｎ′］をＧＦ（２＾ｍ）上のｎ桁の符号語と
   して出力し、前記記憶装置においては、記憶装置内の記
   憶領域がｋ×ｎの行列の形の２次元配置の形をしており
   、しかも、該配列内の部分配列として、Ｒｅｅｄ・Ｓｏ
   ｌｏｍｏｎ符号の生成行列及び各行がＲｅｅｄ・Ｓｏｌ
   ｏｍｏｎ符号の２つの生成行列の行ベクトル同士のテン
   ソル積を定数倍したものである行列が含まれていること
   を特徴とする誤り訂正符号化装置。 ２、第１及び第２の誤り訂正符号化回路を縦属し、第１
   の誤り訂正符号化回路の出力を第２の誤り訂正回路で符
   号化した結果を符号語として出力する誤り訂正符号化装
   置において、第１の符号化回路は、有限体ＧＦ（２＾ｍ
   ）（ｍは２以上の整数）上の情報シンボル列［ａ＿１、
   ａ＿２、・・、ａ＿ｋ］を入力として、該シンボル列と
   、後記ＧＦ（２＾ｍ）上のｋ×ｎ個のシンボルを２次元
   的に記憶している記憶装置から供給される、記憶領域内
   の縦方向の各シンボル列ｆ＾（＾ｉ＾）＿１、ｆ＾（＾
   ｉ＾）＿２、・・、ｆ＾（＾ｉ＾）＿ｋ］（ｉ＝１、・
   、ｎ）との積和演算を行う回路と、該積和演算回路から
   の出力シンボル列 ［ｃ＿１′、・・、ｃ＿ｎ′］の各シンボルに対し、前
   もって定められたＧＦ（２＾ｍ）上の定数ｂ＿１、ｂ＿
   ２、・・、ｂ＿ｎをそれぞれ掛ける掛け算回路とから構
   成され、該掛け算回路の出力［ｂ＿１ｃ＿１′、ｂ＿２
   ｃ＿２′、・・、ｂ＿ｎｃ＿ｎ′］をＧＦ（２＾ｍ）上
   のｎ桁の符号語として出力し、前記記憶装置においては
   、記憶装置内の記憶領域がｋ×ｎの行列の形の２次元配
   置の形をしており、しかも、該配列内の部分配列として
   、Ｒｅｅｄ・Ｓｏｌｏｍｏｎ符号の生成行列及び各行が
   Ｒｅｅｄ・Ｓｏｌｏｍｏｎ符号の２つの生成行列の行ベ
   クトル同士のテンソル積を定数倍したものである行列が
   含まれていることを特徴とする誤り訂正符号化回路であ
   り、第２の符号化回路は、線形誤り訂正符号の符号化回
   路であることを特徴とする、誤り訂正符号化装置。