JPH09162753A - 符号語の復号方式 - Google Patents
符号語の復号方式Info
- Publication number
- JPH09162753A JPH09162753A JP7316206A JP31620695A JPH09162753A JP H09162753 A JPH09162753 A JP H09162753A JP 7316206 A JP7316206 A JP 7316206A JP 31620695 A JP31620695 A JP 31620695A JP H09162753 A JPH09162753 A JP H09162753A
- Authority
- JP
- Japan
- Prior art keywords
- partial
- error
- syndrome
- circuit
- symbol
- 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.)
- Pending
Links
Landscapes
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
Abstract
(57)【要約】
【課題】例えば拡張ガロア体GF(28)上の元である８ビッ
ト構成のシンボルが255個並んだ系列としてなるｔ重誤
りを訂正可能な符号語を復号する際にそれに関するシン
ドロームS0,S1,Sp(p=0〜2t-1) の演算に要する時間を短
縮する。 【解決手段】符号語のシンボル系列から所定の個数, 例
えば２個ごとに抽出したシンボルからなる部分系列を２
個作り、部分系列ごとに部分演算手段10を設けてそれら
に各部分系列に関する部分シンドロームを同時に並行し
て演算させ、統合演算手段20により２個の部分シンドロ
ームを組み合わせて符号語に関するシンドロームSpに統
合することにより、従来は 255回の繰り返し演算が必要
であったに対し 128回で済ませてシンドローム演算時間
を２分の１に短縮する。
ト構成のシンボルが255個並んだ系列としてなるｔ重誤
りを訂正可能な符号語を復号する際にそれに関するシン
ドロームS0,S1,Sp(p=0〜2t-1) の演算に要する時間を短
縮する。 【解決手段】符号語のシンボル系列から所定の個数, 例
えば２個ごとに抽出したシンボルからなる部分系列を２
個作り、部分系列ごとに部分演算手段10を設けてそれら
に各部分系列に関する部分シンドロームを同時に並行し
て演算させ、統合演算手段20により２個の部分シンドロ
ームを組み合わせて符号語に関するシンドロームSpに統
合することにより、従来は 255回の繰り返し演算が必要
であったに対し 128回で済ませてシンドローム演算時間
を２分の１に短縮する。
Description
【０００１】
【発明の属する技術分野】本発明は誤り訂正符号を含む
シンボル系列としてなる符号語，とくにいわゆるリード
・ソロモン符号（以下，ＲＳ符号と呼ぶ）を用いる符号
語を復号ないしはデコードするに際して，誤りの有無を
検出した上で必要に応じて誤りを訂正するための符号語
の復号方式に関する。
シンボル系列としてなる符号語，とくにいわゆるリード
・ソロモン符号（以下，ＲＳ符号と呼ぶ）を用いる符号
語を復号ないしはデコードするに際して，誤りの有無を
検出した上で必要に応じて誤りを訂正するための符号語
の復号方式に関する。
【０００２】
【従来の技術】ディジタルな情報ないしデータを取り扱
う種々な分野では、周知のようにその伝送時や記憶媒体
からの読み取り時に発生しやすい誤りを検出しかつ訂正
をするため情報に情報理論に基づいた誤り訂正符号を付
加して両者を含む符号語の形に符号化しておき、伝送後
や読み取り後にそれを復号する際にも常にこの符号語を
単位として取り扱うのが一般的である。例えば前述のＲ
Ｓ符号を用いる符号語はいわゆる拡張ガロア体 GF
(２m ) 上の元としてのｍビット構成のシンボルをｎ個
(n＝2 m −1)並べた系列であり、ふつうｍ＝８として８
ビット構成のシンボル,すなわち各１バイトのデータが
255個並んだシンボル系列とする。
う種々な分野では、周知のようにその伝送時や記憶媒体
からの読み取り時に発生しやすい誤りを検出しかつ訂正
をするため情報に情報理論に基づいた誤り訂正符号を付
加して両者を含む符号語の形に符号化しておき、伝送後
や読み取り後にそれを復号する際にも常にこの符号語を
単位として取り扱うのが一般的である。例えば前述のＲ
Ｓ符号を用いる符号語はいわゆる拡張ガロア体 GF
(２m ) 上の元としてのｍビット構成のシンボルをｎ個
(n＝2 m −1)並べた系列であり、ふつうｍ＝８として８
ビット構成のシンボル,すなわち各１バイトのデータが
255個並んだシンボル系列とする。
【０００３】このＲＳ符号を用いる符号語において、ｔ
重の誤りをバイト単位で訂正可能とするにはｎ個のシン
ボルの内の2t個を誤り訂正符号に割り当てて符号語内の
正味情報量をn-2t個のバイト分とする。その符号化の際
は拡張ガロア体 GF(２m ) の原始元をαとしてαp (p=
0,1〜2t-1) で表される2t個の根を有する生成多項式を
用い、符号語多項式W(x)＝ΣWiｘi がこの生成多項式で
割り切れるようにする。ただし、Σは変数ｉについての
i=n-1〜0 の範囲内の加算を示し、Wiは符号語のｉ番目
のシンボル, ｘは見せ掛けの変数である。
重の誤りをバイト単位で訂正可能とするにはｎ個のシン
ボルの内の2t個を誤り訂正符号に割り当てて符号語内の
正味情報量をn-2t個のバイト分とする。その符号化の際
は拡張ガロア体 GF(２m ) の原始元をαとしてαp (p=
0,1〜2t-1) で表される2t個の根を有する生成多項式を
用い、符号語多項式W(x)＝ΣWiｘi がこの生成多項式で
割り切れるようにする。ただし、Σは変数ｉについての
i=n-1〜0 の範囲内の加算を示し、Wiは符号語のｉ番目
のシンボル, ｘは見せ掛けの変数である。
【０００４】この符号語を受信して復号する際は符号語
多項式W(x)の変数ｘにαp を入れることによりまず受信
した符号語の一種の病状を示すシンドロームSp＝W
(αp ) を求める。符号化したときの符号語の多項式W
(x)が根αp をもつ生成多項式で割り切れるのであるか
ら、受信符号語に誤りがなけれはシンドロームSiは０で
あり、そうでない場合は誤りが発生していることがわか
る。図３にかかるシンドロームSp＝W(αp ) ＝ΣWiαpi
を求める従来の要領を示す。
多項式W(x)の変数ｘにαp を入れることによりまず受信
した符号語の一種の病状を示すシンドロームSp＝W
(αp ) を求める。符号化したときの符号語の多項式W
(x)が根αp をもつ生成多項式で割り切れるのであるか
ら、受信符号語に誤りがなけれはシンドロームSiは０で
あり、そうでない場合は誤りが発生していることがわか
る。図３にかかるシンドロームSp＝W(αp ) ＝ΣWiαpi
を求める従来の要領を示す。
【０００５】図３の左上部に示すメモリ１は受信した符
号語を構成するｎ個のシンボルWiを記憶しており、アド
レス指定回路２からパルスDPに応じ逐次デクリメントさ
れるアドレスADを受けて８ビットのバス３上に i=n-1か
ら始まるシンボルWiを順次に乗せる。このバス３からシ
ンボルWiを順次に受けてシンドロームS0, S1〜Sp等を求
めるためシンドローム演算回路４がそれぞれ設けられ
る。前述のｔ重の誤りを検出かつ訂正する場合は、これ
らシンドローム演算手段４は p=0〜2t-1の範囲のシンド
ロームSpを求めるために2t個設けられる。
号語を構成するｎ個のシンボルWiを記憶しており、アド
レス指定回路２からパルスDPに応じ逐次デクリメントさ
れるアドレスADを受けて８ビットのバス３上に i=n-1か
ら始まるシンボルWiを順次に乗せる。このバス３からシ
ンボルWiを順次に受けてシンドロームS0, S1〜Sp等を求
めるためシンドローム演算回路４がそれぞれ設けられ
る。前述のｔ重の誤りを検出かつ訂正する場合は、これ
らシンドローム演算手段４は p=0〜2t-1の範囲のシンド
ロームSpを求めるために2t個設けられる。
【０００６】シンドロームS0用の演算手段４は各８ビッ
ト構成の加算回路５とレジスタ６とからなり、加算回路
５はバス４から８ビットのシンボルWiを受けたつどにそ
れをレジスタ６の８ビットの記憶内容にビットごとに加
えて行くが、加算が２を法とするMod2なので８個のイク
スクルーシブオアゲートで構成される。レジスタ６は演
算回路４の動作開始時にクリアされ、前述のデクリメン
トパルスDPに同期したラッチパルスLPに応じて加算回路
５から加算結果を読み取る。シンドロームSOはシンボル
Wiの単純な和ΣWiであるから、最後のシンボルW0の加算
が完了した後にレジスタ６からこれを取り出せばよいこ
とになる。
ト構成の加算回路５とレジスタ６とからなり、加算回路
５はバス４から８ビットのシンボルWiを受けたつどにそ
れをレジスタ６の８ビットの記憶内容にビットごとに加
えて行くが、加算が２を法とするMod2なので８個のイク
スクルーシブオアゲートで構成される。レジスタ６は演
算回路４の動作開始時にクリアされ、前述のデクリメン
トパルスDPに同期したラッチパルスLPに応じて加算回路
５から加算結果を読み取る。シンドロームSOはシンボル
Wiの単純な和ΣWiであるから、最後のシンボルW0の加算
が完了した後にレジスタ６からこれを取り出せばよいこ
とになる。
【０００７】シンドロームS1以降用の演算手段４には加
算回路５とレジスタ６のほかに乗算回路７を組み込み、
レジスタ６の記憶内容にシンドロームS1の場合は原始元
α,シンドロームSpの場合はαp を乗算して加算回路５
に出力させる。演算手段４の動作をシンドロームSpにつ
いて説明すると、レジスタ６の記憶内容のクリア後に最
初のシンボル Wn-1 を受けたときラッチパルスLPに応じ
てレジスタ６内にこのシンボルＷn-1 が読み込まれる。
次のシンボルＷn-2 を受けたとき加算回路５はそれに乗
算回路７の出力αp Ｗn-1 を加算するから、レジスタ６
はαp Ｗn-1 ＋Ｗn-2 を記憶する。以降は同様にして最
後のＷ0 を受けた後のレジスタ６の記憶内容はαp(n-1)
Ｗn-1+αp(n-2)Ｗn-2 〜αＷ1+Ｗ0 ＝ΣWiαpi＝Spにな
るから、これをｐ次のシンドロームとして取り出せばよ
いことになる。
算回路５とレジスタ６のほかに乗算回路７を組み込み、
レジスタ６の記憶内容にシンドロームS1の場合は原始元
α,シンドロームSpの場合はαp を乗算して加算回路５
に出力させる。演算手段４の動作をシンドロームSpにつ
いて説明すると、レジスタ６の記憶内容のクリア後に最
初のシンボル Wn-1 を受けたときラッチパルスLPに応じ
てレジスタ６内にこのシンボルＷn-1 が読み込まれる。
次のシンボルＷn-2 を受けたとき加算回路５はそれに乗
算回路７の出力αp Ｗn-1 を加算するから、レジスタ６
はαp Ｗn-1 ＋Ｗn-2 を記憶する。以降は同様にして最
後のＷ0 を受けた後のレジスタ６の記憶内容はαp(n-1)
Ｗn-1+αp(n-2)Ｗn-2 〜αＷ1+Ｗ0 ＝ΣWiαpi＝Spにな
るから、これをｐ次のシンドロームとして取り出せばよ
いことになる。
【０００８】2t個のシンドロームSp(p=0〜2t-1) がすべ
て０であれば誤りはないが、そうでない場合は誤りを訂
正する必要があり、そのためにはまず誤り位置と誤りの
値をこれらシンドロームSpから求める。このため, 誤り
があるシンボルの符号語内の番号をｊ(j=0〜t-1)として
誤り位置を誤りロケータαj で表し、その逆数α-jを根
とするｔ次の誤り位置多項式を作る。次に、誤りの値が
Ejである誤り多項式をE(x)＝ΣEjｘj とすると、シンド
ロームはSp＝E(αp ) ＝ΣEjαpjであることを利用して
ピーターソン法, バーレンカンプ・マッツィ法, ユーク
リッド法として知られている手法により誤り位置多項式
を０と置いた方程式を解くことによって誤りロケータα
j を求め, 次に誤りの値Ejを求める。かかる誤りロケー
タαj と誤りの値Ejの判明後はｊ番目のシンボルWjの誤
りを誤りの値Ejを加算することにより訂正し、これで符
号語の復号が完了する。
て０であれば誤りはないが、そうでない場合は誤りを訂
正する必要があり、そのためにはまず誤り位置と誤りの
値をこれらシンドロームSpから求める。このため, 誤り
があるシンボルの符号語内の番号をｊ(j=0〜t-1)として
誤り位置を誤りロケータαj で表し、その逆数α-jを根
とするｔ次の誤り位置多項式を作る。次に、誤りの値が
Ejである誤り多項式をE(x)＝ΣEjｘj とすると、シンド
ロームはSp＝E(αp ) ＝ΣEjαpjであることを利用して
ピーターソン法, バーレンカンプ・マッツィ法, ユーク
リッド法として知られている手法により誤り位置多項式
を０と置いた方程式を解くことによって誤りロケータα
j を求め, 次に誤りの値Ejを求める。かかる誤りロケー
タαj と誤りの値Ejの判明後はｊ番目のシンボルWjの誤
りを誤りの値Ejを加算することにより訂正し、これで符
号語の復号が完了する。
【０００９】
【発明が解決しようとする課題】以上に説明した符号語
の復号を種々な用途に容易に適用できるようにするには
復号機能を集積回路装置に組み込むのが望ましいが、実
際には演算規模が非常に大きくなるのでVLSIとする必要
があり、その構成を簡単化するためシストニックアルゴ
リズムを用いてパイプライン処理をすることが考えられ
ている (例えば、Trans. on Computers, Vol. C-34, N
o.5, May 1985, p.383-403 や電子通信学会論文誌, 198
6/3, Vol.J69-A, No.3, p.420-428を参照) 。しかし、
従来技術ではその復号動作のための演算, とくにシンド
ロームの演算にかなりの時間を要する点がその実用面で
の最大の問題点になっている。
の復号を種々な用途に容易に適用できるようにするには
復号機能を集積回路装置に組み込むのが望ましいが、実
際には演算規模が非常に大きくなるのでVLSIとする必要
があり、その構成を簡単化するためシストニックアルゴ
リズムを用いてパイプライン処理をすることが考えられ
ている (例えば、Trans. on Computers, Vol. C-34, N
o.5, May 1985, p.383-403 や電子通信学会論文誌, 198
6/3, Vol.J69-A, No.3, p.420-428を参照) 。しかし、
従来技術ではその復号動作のための演算, とくにシンド
ロームの演算にかなりの時間を要する点がその実用面で
の最大の問題点になっている。
【００１０】例えば図３のような従来方式では、符号語
が８ビットの 255個のシンボルからなる場合のシンドロ
ームSp用の演算手段４は乗算回路７によりレジスタ６の
記憶内容にαp を乗算しかつ加算回路５により乗算結果
にシンボルWiを加算して行く積和の演算を255 回も繰り
返す必要があるため、演算手段４を図のように複数個設
けて並行して動作させてもシンドロームの演算だけにか
なりの時間が掛かってしまう。また、シンドロームの演
算は前述のように復号のための一連の動作中の最初のス
テップなのでパイプライン処理に不適であり、図３のメ
モリ１内に受信符号語を一旦取り込んだ上でそのシンボ
ルWiを１個ずつ取り出して演算手段４に与えねばならな
いので、メモリ１に対する多数回のアクセスに必要な時
間が復号速度を高める上での障害になっているのが実情
である。
が８ビットの 255個のシンボルからなる場合のシンドロ
ームSp用の演算手段４は乗算回路７によりレジスタ６の
記憶内容にαp を乗算しかつ加算回路５により乗算結果
にシンボルWiを加算して行く積和の演算を255 回も繰り
返す必要があるため、演算手段４を図のように複数個設
けて並行して動作させてもシンドロームの演算だけにか
なりの時間が掛かってしまう。また、シンドロームの演
算は前述のように復号のための一連の動作中の最初のス
テップなのでパイプライン処理に不適であり、図３のメ
モリ１内に受信符号語を一旦取り込んだ上でそのシンボ
ルWiを１個ずつ取り出して演算手段４に与えねばならな
いので、メモリ１に対する多数回のアクセスに必要な時
間が復号速度を高める上での障害になっているのが実情
である。
【００１１】かかる事情に鑑み、本発明の目的は符号語
を復号する際のシンドローム演算に要する時間を短縮す
ることにある。
を復号する際のシンドローム演算に要する時間を短縮す
ることにある。
【００１２】
【課題を解決するための手段】本発明によれば上記の目
的は、シンボル系列としてなる符号語の復号に際して系
列から所定個数ごとにシンボルを抽出してシンボルの部
分系列を作って各部分系列ごとに部分演算手段を設け、
これらの部分演算手段により複数の部分系列に関するシ
ンドロームの部分演算を同時に進行させ、複数個の部分
演算結果を統合演算手段により組み合わせて符号語に関
するシンドロームを演算することにより達成される。こ
の本発明の復号方式は符号語にＲＳ符号を用い，そのシ
ンボルが拡張ガロア体上の例えば８ビットの元である場
合にとくに適する。
的は、シンボル系列としてなる符号語の復号に際して系
列から所定個数ごとにシンボルを抽出してシンボルの部
分系列を作って各部分系列ごとに部分演算手段を設け、
これらの部分演算手段により複数の部分系列に関するシ
ンドロームの部分演算を同時に進行させ、複数個の部分
演算結果を統合演算手段により組み合わせて符号語に関
するシンドロームを演算することにより達成される。こ
の本発明の復号方式は符号語にＲＳ符号を用い，そのシ
ンボルが拡張ガロア体上の例えば８ビットの元である場
合にとくに適する。
【００１３】本発明方式を実施する際は、復号すべき符
号語がメモリから乗せられるバスにシンボル系列のシン
ボルを部分演算手段に対応する個数ずつ同時に乗せ、各
部分演算手段にこれらのシンボルをバスから並列に読み
込むのがメモリへのアクセス時間を短縮する上で非常に
有利である。例えば、16ビットのバスに各８ビットのシ
ンボルを２個同時に乗せ、これに対応して部分演算手段
を２個設けてそれらにシンボル系列中の偶数番目のシン
ボルと奇数番目のシンボルからなる部分系列に関するシ
ンドロームの部分演算を分担させるのがよい。
号語がメモリから乗せられるバスにシンボル系列のシン
ボルを部分演算手段に対応する個数ずつ同時に乗せ、各
部分演算手段にこれらのシンボルをバスから並列に読み
込むのがメモリへのアクセス時間を短縮する上で非常に
有利である。例えば、16ビットのバスに各８ビットのシ
ンボルを２個同時に乗せ、これに対応して部分演算手段
を２個設けてそれらにシンボル系列中の偶数番目のシン
ボルと奇数番目のシンボルからなる部分系列に関するシ
ンドロームの部分演算を分担させるのがよい。
【００１４】本発明で用いる部分演算手段にはシンボル
の加算回路とその加算結果に対する乗算回路を用い、乗
算回路の乗算結果に加算回路により部分系列の各シンボ
ルを繰り返し加算して行くことでよく、複数の部分演算
手段はすべて同じ構成とするのが有利である。また、統
合演算手段としては部分演算手段の演算結果に対する乗
算回路とその乗算結果に対する加算回路とを用い、かつ
乗算回路の方は特定の１個を除く部分演算手段に対応し
て設け、その乗算結果と特定の部分演算手段による演算
結果を加算して符号語のシンドロームに統合することで
よい。さらに、これらの部分演算手段と統合演算手段に
用いる乗算回路には線状フィードバックシフトレジスタ
を用い、その乗算動作のためのシフト動作回数を符号語
に関して求めるべきシンドロームの次数に応じて設定す
るのが有利であり、この態様では乗算回路が元々不要な
０次のシンドローム用は別として部分演算手段や統合演
算手段をすべて同じ回路構成とすることができる。
の加算回路とその加算結果に対する乗算回路を用い、乗
算回路の乗算結果に加算回路により部分系列の各シンボ
ルを繰り返し加算して行くことでよく、複数の部分演算
手段はすべて同じ構成とするのが有利である。また、統
合演算手段としては部分演算手段の演算結果に対する乗
算回路とその乗算結果に対する加算回路とを用い、かつ
乗算回路の方は特定の１個を除く部分演算手段に対応し
て設け、その乗算結果と特定の部分演算手段による演算
結果を加算して符号語のシンドロームに統合することで
よい。さらに、これらの部分演算手段と統合演算手段に
用いる乗算回路には線状フィードバックシフトレジスタ
を用い、その乗算動作のためのシフト動作回数を符号語
に関して求めるべきシンドロームの次数に応じて設定す
るのが有利であり、この態様では乗算回路が元々不要な
０次のシンドローム用は別として部分演算手段や統合演
算手段をすべて同じ回路構成とすることができる。
【００１５】本発明方式は誤りの訂正段階にも適用でき
る。この場合は誤り訂正手段を２個設けてシンドローム
から求めた誤り位置と誤りの値に基づいて誤りの値を与
えるべき誤り訂正手段を誤り位置に応じて選択しなが
ら、誤りが発生したシンボルに誤りの値を加算して訂正
するのがよい。かかる誤り訂正手段としては選択回路と
加算回路とその加算結果を記憶するレジスタを用い、選
択回路により加算回路に誤りの値とシンボルの値を切り
換えながら順次与えて、そのつどレジスタの記憶内容に
加算させた上でレジスタから訂正済みのシンボルを取り
出すことでよい。また、誤り位置と誤りの値を受ける切
換手段を用い、誤り位置が示す符号語内の誤りが発生し
たシンボルの番号が偶数か奇数かに応じ誤りの値を与え
るべき誤り訂正手段を切り換えないし選択させるのがよ
い。
る。この場合は誤り訂正手段を２個設けてシンドローム
から求めた誤り位置と誤りの値に基づいて誤りの値を与
えるべき誤り訂正手段を誤り位置に応じて選択しなが
ら、誤りが発生したシンボルに誤りの値を加算して訂正
するのがよい。かかる誤り訂正手段としては選択回路と
加算回路とその加算結果を記憶するレジスタを用い、選
択回路により加算回路に誤りの値とシンボルの値を切り
換えながら順次与えて、そのつどレジスタの記憶内容に
加算させた上でレジスタから訂正済みのシンボルを取り
出すことでよい。また、誤り位置と誤りの値を受ける切
換手段を用い、誤り位置が示す符号語内の誤りが発生し
たシンボルの番号が偶数か奇数かに応じ誤りの値を与え
るべき誤り訂正手段を切り換えないし選択させるのがよ
い。
【００１６】本発明はシンドロームが従来技術の項で述
べたような多項式，すなわち複数の項の和の形や積の項
の和の形で表され、和の結果は項の加算順序を組み換え
ても同じである点に着目して、シンボル系列を複数個の
部分系列に分割してそれらに関する部分演算を並列ない
し同時に進行させることによりシンドロームの演算に要
する時間を短縮するとともに、これらの部分系列を符号
語のシンボル系列から所定個数ごとにシンボルを抽出し
て作ることにより、すべての部分系列に関する部分演算
をシンボルのメモリからの読み出しに同期して円滑にか
つ同様な要領で進め得るようにしたものである。なお、
符号語のシンボル数が部分系列の個数で割り切れない場
合は内容が０のシンボルを適宜追加して部分系列のシン
ボル数を揃えることにより部分演算を円滑にかつ正確に
進めることができる。これをより具体的に述べると次の
とおりである。
べたような多項式，すなわち複数の項の和の形や積の項
の和の形で表され、和の結果は項の加算順序を組み換え
ても同じである点に着目して、シンボル系列を複数個の
部分系列に分割してそれらに関する部分演算を並列ない
し同時に進行させることによりシンドロームの演算に要
する時間を短縮するとともに、これらの部分系列を符号
語のシンボル系列から所定個数ごとにシンボルを抽出し
て作ることにより、すべての部分系列に関する部分演算
をシンボルのメモリからの読み出しに同期して円滑にか
つ同様な要領で進め得るようにしたものである。なお、
符号語のシンボル数が部分系列の個数で割り切れない場
合は内容が０のシンボルを適宜追加して部分系列のシン
ボル数を揃えることにより部分演算を円滑にかつ正確に
進めることができる。これをより具体的に述べると次の
とおりである。
【００１７】従来技術の項で述べたようにシンドローム
Spは一般には積の和の多項式であるSp＝ΣαipＷi (i=0
〜n-1)で表され、本発明では符号語のｎ個のシンボルＷ
i の系列からシンボルを所定個数ごとに抽出してｒ個の
部分系列に分割し、部分演算手段によって各部分系列に
関する部分シンドロームSpj (j=0〜r-1)を上と同様な形
の Spj＝Σr αpiＷi+j の多項式で演算する。ただし,
Σr は変数ｉをｒずつ0,r,2r・・・imのように変化させ
たときの和を示す。また、変数ｉの最大値imは符号語の
シンボル数ｎが部分系列の個数ｒで割り切れる場合には
n-rとするが、そうでない場合には n-r+1とし, かつ添
字 i+jが n-1を越えるシンボルＷi+j を０とおくものと
する。本発明ではこれら部分シンドロームSpj をｒ個の
部分演算手段により前述のように並行して同時に演算す
る。
Spは一般には積の和の多項式であるSp＝ΣαipＷi (i=0
〜n-1)で表され、本発明では符号語のｎ個のシンボルＷ
i の系列からシンボルを所定個数ごとに抽出してｒ個の
部分系列に分割し、部分演算手段によって各部分系列に
関する部分シンドロームSpj (j=0〜r-1)を上と同様な形
の Spj＝Σr αpiＷi+j の多項式で演算する。ただし,
Σr は変数ｉをｒずつ0,r,2r・・・imのように変化させ
たときの和を示す。また、変数ｉの最大値imは符号語の
シンボル数ｎが部分系列の個数ｒで割り切れる場合には
n-rとするが、そうでない場合には n-r+1とし, かつ添
字 i+jが n-1を越えるシンボルＷi+j を０とおくものと
する。本発明ではこれら部分シンドロームSpj をｒ個の
部分演算手段により前述のように並行して同時に演算す
る。
【００１８】部分系列に関するシンドロームSpj の演算
後は、統合演算手段により符号語に関するシンドローム
Spに統合する。符号語のシンボル系列から一定の個数ご
とにシンボルを抽出して部分系列としたので、部分シン
ドロームSpj から上と同様な積の和の形をもつ多項式Sp
＝ΣαjpSpj によりシンドロームSpを簡単に短時間で演
算できる。従って、本発明では部分シンドロームSpj の
並列演算によりシンドロームSpの演算時間を従来のほぼ
ｒ分の１に短縮でき、かつ複数個のシンボルの並列読み
出しによりメモリアクセス時間もｒ分の１に短縮でき
る。
後は、統合演算手段により符号語に関するシンドローム
Spに統合する。符号語のシンボル系列から一定の個数ご
とにシンボルを抽出して部分系列としたので、部分シン
ドロームSpj から上と同様な積の和の形をもつ多項式Sp
＝ΣαjpSpj によりシンドロームSpを簡単に短時間で演
算できる。従って、本発明では部分シンドロームSpj の
並列演算によりシンドロームSpの演算時間を従来のほぼ
ｒ分の１に短縮でき、かつ複数個のシンボルの並列読み
出しによりメモリアクセス時間もｒ分の１に短縮でき
る。
【００１９】
【発明の実施の形態】図を参照しながら本発明による符
号語の復号方式の実施例を説明する。図１に本発明をシ
ンドロームの演算に適用した実施例を，図２に誤りの訂
正に適用した実施例をそれぞれ示す。これらの実施例で
は符号語は拡張ガロア体 GF(２8 ) の元である８ビット
のシンボルがｎ=255個並んだ多項式Ｗ(x)=Σｘi Ｗi
(ただしΣはｉ=0〜n-1 の和を示す) で表されるｔ重の
誤りを訂正可能なＲＳ符号によるシンボルＷi の系列と
し、シンドロームSp(p=0〜2t-1) を演算する際はシンボ
ル系列をそれから１個おきに抽出されたシンボル, すな
わち偶数番目と奇数番目のシンボルからなる２個の部分
系列に分けるものとする。
号語の復号方式の実施例を説明する。図１に本発明をシ
ンドロームの演算に適用した実施例を，図２に誤りの訂
正に適用した実施例をそれぞれ示す。これらの実施例で
は符号語は拡張ガロア体 GF(２8 ) の元である８ビット
のシンボルがｎ=255個並んだ多項式Ｗ(x)=Σｘi Ｗi
(ただしΣはｉ=0〜n-1 の和を示す) で表されるｔ重の
誤りを訂正可能なＲＳ符号によるシンボルＷi の系列と
し、シンドロームSp(p=0〜2t-1) を演算する際はシンボ
ル系列をそれから１個おきに抽出されたシンボル, すな
わち偶数番目と奇数番目のシンボルからなる２個の部分
系列に分けるものとする。
【００２０】図１の左上部に示すメモリ１は受信した符
号語Ｗ(x) のシンボルＷi の系列を記憶しており、アド
レス指定回路２からデクリメントパルスDPに応じて逐次
切り換わるアドレスADで指定されたシンボルがこれから
バス３に乗せられるが、この実施例ではシンボル系列を
２個の部分系列に分けるのに対応してバス３を同時に２
個の８ビットのシンボルを乗せ得る16ビットのバスと
し、シンボル対(W0 W1),(W2 W3) 等を乗せるようにす
る。なお、 Wn-1 を含むシンボル対はｎが 255より小さ
い偶数, 例えば 254のときは(Wn-2 W n-1)とし, この実
施例のように奇数のときは(Wn-1 0)とすることでよい。
号語Ｗ(x) のシンボルＷi の系列を記憶しており、アド
レス指定回路２からデクリメントパルスDPに応じて逐次
切り換わるアドレスADで指定されたシンボルがこれから
バス３に乗せられるが、この実施例ではシンボル系列を
２個の部分系列に分けるのに対応してバス３を同時に２
個の８ビットのシンボルを乗せ得る16ビットのバスと
し、シンボル対(W0 W1),(W2 W3) 等を乗せるようにす
る。なお、 Wn-1 を含むシンボル対はｎが 255より小さ
い偶数, 例えば 254のときは(Wn-2 W n-1)とし, この実
施例のように奇数のときは(Wn-1 0)とすることでよい。
【００２１】図にはかかるシンボル対をバス３から受け
るシンドロームS0とS1とSp用の部分演算手段10と統合演
算手段20とを一点鎖線で囲んで示す。部分演算手段10の
方は各シンドロームごとに１対設け、その内の図の上側
と下側にそれぞれ偶数番目と奇数番目のシンボルを含む
部分系列を与える。さて、シンドロームSpは符号語の多
項式Ｗ(x) ＝Σｘi Ｗi の変数ｘにαp を入れればよい
からSp＝ΣαpiＷi となり、これを偶数番目と奇数番目
のシンボルに分けて整理すると、 Sp＝Σ2 αpiＷi ＋αp Σ2 αpiＷi+1 となる。Σ2 は変数ｉを0, 2, 4 のように２ずつ変化さ
せた和を表し、第１項は偶数番目, 第２項は奇数番目の
シンボルに関する。そこで Spe＝Σ2 αpiＷi ,Spo＝Σ
2 αpiＷi+1 と置くと上式はSp＝ Spe＋αp Spo とな
る。上側と下側の部分演算手段10はこれら部分シンドロ
ーム Speと Spoの演算用であり、これらは統合演算手段
20によりシンドロームSpに統合される。
るシンドロームS0とS1とSp用の部分演算手段10と統合演
算手段20とを一点鎖線で囲んで示す。部分演算手段10の
方は各シンドロームごとに１対設け、その内の図の上側
と下側にそれぞれ偶数番目と奇数番目のシンボルを含む
部分系列を与える。さて、シンドロームSpは符号語の多
項式Ｗ(x) ＝Σｘi Ｗi の変数ｘにαp を入れればよい
からSp＝ΣαpiＷi となり、これを偶数番目と奇数番目
のシンボルに分けて整理すると、 Sp＝Σ2 αpiＷi ＋αp Σ2 αpiＷi+1 となる。Σ2 は変数ｉを0, 2, 4 のように２ずつ変化さ
せた和を表し、第１項は偶数番目, 第２項は奇数番目の
シンボルに関する。そこで Spe＝Σ2 αpiＷi ,Spo＝Σ
2 αpiＷi+1 と置くと上式はSp＝ Spe＋αp Spo とな
る。上側と下側の部分演算手段10はこれら部分シンドロ
ーム Speと Spoの演算用であり、これらは統合演算手段
20によりシンドロームSpに統合される。
【００２２】このように部分シンドローム Speと Spoは
シンボルが偶数番目か奇数番目かが異なるだけで同形の
式で表されるので、２個の部分演算手段10を同じ構成と
することができる。符号語のシンボル系列からシンボル
を所定の個数ごとに抽出する限り任意のｒ個の部分系列
に分ける場合も同じである。シンドロームS0の場合の部
分演算手段10は演算すべき部分シンドロームSpe, Spoが
それぞれ非常に簡単なΣ2 Ｗi とΣ2 Ｗi+1 の形になる
ので加算回路11とレジスタ12だけで構成して、バス３か
ら受けるシンボルを加算回路11によりレジスタ12の記憶
内容に加算し、レジスタ12にラッチ指令LP1 を与えてこ
の加算結果を記憶させる。この実施例のレジスタ12は８
ビットレジスタであり、加算は２を法とする Mod２の加
算なので加算回路は８個のイクスクルーシブオアゲート
で構成される。
シンボルが偶数番目か奇数番目かが異なるだけで同形の
式で表されるので、２個の部分演算手段10を同じ構成と
することができる。符号語のシンボル系列からシンボル
を所定の個数ごとに抽出する限り任意のｒ個の部分系列
に分ける場合も同じである。シンドロームS0の場合の部
分演算手段10は演算すべき部分シンドロームSpe, Spoが
それぞれ非常に簡単なΣ2 Ｗi とΣ2 Ｗi+1 の形になる
ので加算回路11とレジスタ12だけで構成して、バス３か
ら受けるシンボルを加算回路11によりレジスタ12の記憶
内容に加算し、レジスタ12にラッチ指令LP1 を与えてこ
の加算結果を記憶させる。この実施例のレジスタ12は８
ビットレジスタであり、加算は２を法とする Mod２の加
算なので加算回路は８個のイクスクルーシブオアゲート
で構成される。
【００２３】ｐが０以外のシンドロームSp用の場合は部
分演算手段10に上述の加算回路11とレジスタ12のほかに
乗算回路13を組み込み、レジスタ12の記憶内容に対しα
2pを乗算した上で加算回路11に与えさせる。前述のΣ2
αpiＷi やΣ2 αpiＷi+1 のΣ2 では変数ｉが２ずつ変
化するから、乗算回路13によるこのα2pの乗算により部
分シンドローム Speや Spoを演算することができる。こ
の乗算回路13には線状フィードバックシフトレジスタ
（以下LFSRという) を用い、読取指令RP１に応じレジス
タ12の記憶内容を読み込んだ上でクロックに応じその内
容をシフトさせて原始元αを乗算できるようにするのが
有利である。
分演算手段10に上述の加算回路11とレジスタ12のほかに
乗算回路13を組み込み、レジスタ12の記憶内容に対しα
2pを乗算した上で加算回路11に与えさせる。前述のΣ2
αpiＷi やΣ2 αpiＷi+1 のΣ2 では変数ｉが２ずつ変
化するから、乗算回路13によるこのα2pの乗算により部
分シンドローム Speや Spoを演算することができる。こ
の乗算回路13には線状フィードバックシフトレジスタ
（以下LFSRという) を用い、読取指令RP１に応じレジス
タ12の記憶内容を読み込んだ上でクロックに応じその内
容をシフトさせて原始元αを乗算できるようにするのが
有利である。
【００２４】よく知られているように、このLFSRはこの
実施例では８段のシフトレジスタの各段の記憶内容を通
常のようにクロックに応じてシフトさせると同時に、終
段の記憶内容を所定の原始多項式に対応する段の内容に
加算する形でフィードバックすることにより、αを乗算
すると同時に乗算結果の多項式を原始多項式で除した剰
余が自動的に得られるようにするものである。図１の実
施例ではかかるLFSRを乗算回路13に用い、シンドローム
S1用の場合はそれに２個のクロックC2を与えてα2 を乗
算させ, シンドロームSp用の場合はそれに2p個のクロッ
クC2p を与えてα2pを乗算させるようになっている。こ
のようにして図１の実施例では、求めるシンドロームSp
の次数ｐが１以上の場合は、部分演算回路10として乗算
回路13に用いるLFSRに与えるべきクロックの個数が次数
ｐに応じて異なるだけで同じ回路構成のものを用いるこ
とができる。
実施例では８段のシフトレジスタの各段の記憶内容を通
常のようにクロックに応じてシフトさせると同時に、終
段の記憶内容を所定の原始多項式に対応する段の内容に
加算する形でフィードバックすることにより、αを乗算
すると同時に乗算結果の多項式を原始多項式で除した剰
余が自動的に得られるようにするものである。図１の実
施例ではかかるLFSRを乗算回路13に用い、シンドローム
S1用の場合はそれに２個のクロックC2を与えてα2 を乗
算させ, シンドロームSp用の場合はそれに2p個のクロッ
クC2p を与えてα2pを乗算させるようになっている。こ
のようにして図１の実施例では、求めるシンドロームSp
の次数ｐが１以上の場合は、部分演算回路10として乗算
回路13に用いるLFSRに与えるべきクロックの個数が次数
ｐに応じて異なるだけで同じ回路構成のものを用いるこ
とができる。
【００２５】統合演算手段20は部分演算手段10の演算結
果であるこの実施例では２個の部分シンドローム Speと
Spoを加算を含む演算によってシンドロームSpに統合す
る。０次のシンドロームS0の場合はこれらを単に加算す
ればよいから、８個のイクスクルーシブオアゲートから
なる加算回路21により前述のΣ2 Ｗi とΣ2 Ｗi+1 を加
算した上でレジスタ22にラッチ指令LP２を与えてその結
果をシンドロームS0として記憶させる。１次以上のシン
ドロームSpの場合は、統合演算手段20内に乗算回路23を
設けて部分シンドローム Spoを読取指令RP２に応じて読
み込んでαp を乗算させ、加算回路21にその乗算結果に
部分シンドローム Speを加算させた上でレジスタ22に記
憶させる。乗算回路23もLFSRとするのがよく、シンドロ
ームSpの場合はこれにｐ個のクロックCpを与えてαp を
乗算させる。これにより、０次を除くシンドロームの統
合演算手段20は同じ回路構成になる。
果であるこの実施例では２個の部分シンドローム Speと
Spoを加算を含む演算によってシンドロームSpに統合す
る。０次のシンドロームS0の場合はこれらを単に加算す
ればよいから、８個のイクスクルーシブオアゲートから
なる加算回路21により前述のΣ2 Ｗi とΣ2 Ｗi+1 を加
算した上でレジスタ22にラッチ指令LP２を与えてその結
果をシンドロームS0として記憶させる。１次以上のシン
ドロームSpの場合は、統合演算手段20内に乗算回路23を
設けて部分シンドローム Spoを読取指令RP２に応じて読
み込んでαp を乗算させ、加算回路21にその乗算結果に
部分シンドローム Speを加算させた上でレジスタ22に記
憶させる。乗算回路23もLFSRとするのがよく、シンドロ
ームSpの場合はこれにｐ個のクロックCpを与えてαp を
乗算させる。これにより、０次を除くシンドロームの統
合演算手段20は同じ回路構成になる。
【００２６】以上のように構成された図１の実施例で
は、部分演算手段10内のレジスタ12と統合演算手段20内
のレジスタ22をまずクリアした後に、メモリ１から16ビ
ットのバス３に復号をすべき符号語Ｗ(x) ＝Σｘi Ｗi
の各８ビットのシンボルＷi の系列中の例えば最後の W
n-1 を含むシンボル対から始めて１対ずつ乗せながら、
これを順次受ける各シンドロームSp用の２個の部分演算
手段10を並行動作させて部分シンドローム Speと Spoを
同時に演算させ、さらに統合演算手段20もすべて同時に
動作させて各２個の部分シンドローム Speと Spoをシン
ドロームSpに統合演算させる。なお、この演算結果とし
てのシンドロームSpは各統合演算手段20のレジスタ22か
ら随時読み出すことができる。
は、部分演算手段10内のレジスタ12と統合演算手段20内
のレジスタ22をまずクリアした後に、メモリ１から16ビ
ットのバス３に復号をすべき符号語Ｗ(x) ＝Σｘi Ｗi
の各８ビットのシンボルＷi の系列中の例えば最後の W
n-1 を含むシンボル対から始めて１対ずつ乗せながら、
これを順次受ける各シンドロームSp用の２個の部分演算
手段10を並行動作させて部分シンドローム Speと Spoを
同時に演算させ、さらに統合演算手段20もすべて同時に
動作させて各２個の部分シンドローム Speと Spoをシン
ドロームSpに統合演算させる。なお、この演算結果とし
てのシンドロームSpは各統合演算手段20のレジスタ22か
ら随時読み出すことができる。
【００２７】このように本発明方式では符号語のシンボ
ル系列を２個, 一般にはｒ個の部分系列に分け、それら
に関する部分シンドロームの演算を複数の部分演算手段
10に分担させて同時に演算させる。複数の部分シンドロ
ームは統合演算手段20により符号語に関するシンドロー
ムに統合する必要はあるが、それに要する演算時間は部
分演算手段10に比べるとずっと短くてよいので、本発明
によりシンドロームの演算に必要な時間を短縮して従来
のほぼ２分の１, 一般にはｒ分の１で済ませることがで
きる。さらにメモリ１から２個, 一般にはｒ個のシンボ
ルを纏めて読み出すことができるので、本発明方式では
メモリアクセス時間も従来の２分の１,一般にはｒ分の
１に短縮することができる。
ル系列を２個, 一般にはｒ個の部分系列に分け、それら
に関する部分シンドロームの演算を複数の部分演算手段
10に分担させて同時に演算させる。複数の部分シンドロ
ームは統合演算手段20により符号語に関するシンドロー
ムに統合する必要はあるが、それに要する演算時間は部
分演算手段10に比べるとずっと短くてよいので、本発明
によりシンドロームの演算に必要な時間を短縮して従来
のほぼ２分の１, 一般にはｒ分の１で済ませることがで
きる。さらにメモリ１から２個, 一般にはｒ個のシンボ
ルを纏めて読み出すことができるので、本発明方式では
メモリアクセス時間も従来の２分の１,一般にはｒ分の
１に短縮することができる。
【００２８】なお、シンボル系列をｒが３以上の個数の
部分系列に分ける場合は、統合演算手段20により r-1個
の部分シンドロームに乗算を施しかつ r-1回の加算を施
して符号語に関するシンドロームに統合する必要はある
が、乗算は同時に施せるので複数の乗算に要する時間は
１個分の乗算時間と大差がなく, 加算回数は増えてもイ
クスクルーシブオアゲートを用いる各加算時間が短いの
で、統合演算手段20の演算時間の僅かな増加は部分演算
手段10の動作時間の短縮効果で充分に補える。メモリア
クセス時間はｒが大きいほど短くなり、ｒを４とすれば
32ビットバスを利用してアクセス時間を４分の１に短縮
できる。
部分系列に分ける場合は、統合演算手段20により r-1個
の部分シンドロームに乗算を施しかつ r-1回の加算を施
して符号語に関するシンドロームに統合する必要はある
が、乗算は同時に施せるので複数の乗算に要する時間は
１個分の乗算時間と大差がなく, 加算回数は増えてもイ
クスクルーシブオアゲートを用いる各加算時間が短いの
で、統合演算手段20の演算時間の僅かな増加は部分演算
手段10の動作時間の短縮効果で充分に補える。メモリア
クセス時間はｒが大きいほど短くなり、ｒを４とすれば
32ビットバスを利用してアクセス時間を４分の１に短縮
できる。
【００２９】また、図１の実施例では部分演算手段10や
統合演算手段20の回路構成をシンドロームSpの０以外の
次数ｐに関せず同じとするためにそれらの乗算回路13や
23にLFSRを用いたが、前述のように繰り返しクロックを
受けて動作するLFSRではその順序制御にまだ余分に時間
がかかるので、回路構成を次数ｐに応じ変える必要はあ
るが乗算回路13や23を論理ゲートだけで構成すれば、演
算に必要な時間を一層大幅に短縮することができる。な
お、この場合の乗算回路13や23は複数段構成になるが、
例えばイクスクルーシブオアゲートによる加算要素だけ
で構成できる。
統合演算手段20の回路構成をシンドロームSpの０以外の
次数ｐに関せず同じとするためにそれらの乗算回路13や
23にLFSRを用いたが、前述のように繰り返しクロックを
受けて動作するLFSRではその順序制御にまだ余分に時間
がかかるので、回路構成を次数ｐに応じ変える必要はあ
るが乗算回路13や23を論理ゲートだけで構成すれば、演
算に必要な時間を一層大幅に短縮することができる。な
お、この場合の乗算回路13や23は複数段構成になるが、
例えばイクスクルーシブオアゲートによる加算要素だけ
で構成できる。
【００３０】図２に示す実施例では本発明を受信符号語
のシンボルに発生した誤りの訂正に適用する。図１で説
明したようにして求められたシンドロームSp(p=0〜2t-
1) に基づき前述のピーターソン法やバーレンカンプ・
マッツィ法やユークリッド法を利用して誤り位置, すな
わちシンボル系列中の誤りが発生したｔ個のシンボルの
番号ｉとその誤りの値Eiが求められ、図の右上部に示す
メモリ1a内に記憶されているものとする。メモリ1aは図
の右下部に示すメモリ１と同じであってよいが、図示の
都合上分けて示されており、これから16ビットのバス3a
を介してレジスタ3bと3cにそれぞれ誤り位置ｉと誤りの
値Eiが一つずつ取り出される。
のシンボルに発生した誤りの訂正に適用する。図１で説
明したようにして求められたシンドロームSp(p=0〜2t-
1) に基づき前述のピーターソン法やバーレンカンプ・
マッツィ法やユークリッド法を利用して誤り位置, すな
わちシンボル系列中の誤りが発生したｔ個のシンボルの
番号ｉとその誤りの値Eiが求められ、図の右上部に示す
メモリ1a内に記憶されているものとする。メモリ1aは図
の右下部に示すメモリ１と同じであってよいが、図示の
都合上分けて示されており、これから16ビットのバス3a
を介してレジスタ3bと3cにそれぞれ誤り位置ｉと誤りの
値Eiが一つずつ取り出される。
【００３１】この図２の実施例では誤り訂正手段30を１
対設けてそれぞれ選択回路31と加算回路32とレジスタ33
とバッファ回路34とから構成し、誤り位置ｉが偶数の場
合は右側の, 奇数の場合は左側の誤り訂正手段30を用い
る。その上側に示された切換手段40はレジスタ3b内に記
憶されている誤り位置ｉに応じ誤り訂正動作をさせるべ
き左右の誤り訂正手段30を選択するものである。
対設けてそれぞれ選択回路31と加算回路32とレジスタ33
とバッファ回路34とから構成し、誤り位置ｉが偶数の場
合は右側の, 奇数の場合は左側の誤り訂正手段30を用い
る。その上側に示された切換手段40はレジスタ3b内に記
憶されている誤り位置ｉに応じ誤り訂正動作をさせるべ
き左右の誤り訂正手段30を選択するものである。
【００３２】また、符号語のシンボル系列を受信時の状
態のままで記憶しているメモリ１に付随してアドレス指
定回路２と補助指定回路2aを設け、レジスタ3bから補助
指定回路2aに誤り位置ｉを指定してメモリ１の相対アド
レスADｒに換算させ、これを受けるアドレス指定回路２
にさらに絶対アドレスADに換算させた上でメモリ１に与
えるようにする。これに応じてメモリ１から誤りが発生
したシンボルWiを含むシンボル対が16ビットのバス３に
乗せられる。
態のままで記憶しているメモリ１に付随してアドレス指
定回路２と補助指定回路2aを設け、レジスタ3bから補助
指定回路2aに誤り位置ｉを指定してメモリ１の相対アド
レスADｒに換算させ、これを受けるアドレス指定回路２
にさらに絶対アドレスADに換算させた上でメモリ１に与
えるようにする。これに応じてメモリ１から誤りが発生
したシンボルWiを含むシンボル対が16ビットのバス３に
乗せられる。
【００３３】切換手段40は例えば図示のようにアンドゲ
ートで構成され、その枠内に簡略に示す右側と左側のア
ンドゲート41と42には各８個のアンドゲートが用いられ
る。この切換手段40はレジスタ3bから８ビットの誤り位
置ｉの最下位ビットを受け、誤り位置ｉが偶数でその最
下位ビットが０の場合には右側のアンドゲート群41をイ
ネーブルしてレジスタ3cから８ビットの誤りの値Eiを右
側の誤り訂正手段30に与え、逆に誤り位置ｉが奇数の場
合は左側のアンドゲート群42をイネーブルして誤りの値
Eiを左側の誤り訂正手段30に与えるようになっている。
また、誤り訂正手段30の選択回路31はこの切換手段40か
ら受ける誤りの値Eiとバス３から受けるシンボルのいず
れかを選択指令Scの論理値による指定に応じ選択してそ
の下側の加算回路32に与えるもので、右側と左側の選択
回路31はバス３上のシンボル対の内のそれぞれ偶数番目
と奇数番目のシンボルを受ける。
ートで構成され、その枠内に簡略に示す右側と左側のア
ンドゲート41と42には各８個のアンドゲートが用いられ
る。この切換手段40はレジスタ3bから８ビットの誤り位
置ｉの最下位ビットを受け、誤り位置ｉが偶数でその最
下位ビットが０の場合には右側のアンドゲート群41をイ
ネーブルしてレジスタ3cから８ビットの誤りの値Eiを右
側の誤り訂正手段30に与え、逆に誤り位置ｉが奇数の場
合は左側のアンドゲート群42をイネーブルして誤りの値
Eiを左側の誤り訂正手段30に与えるようになっている。
また、誤り訂正手段30の選択回路31はこの切換手段40か
ら受ける誤りの値Eiとバス３から受けるシンボルのいず
れかを選択指令Scの論理値による指定に応じ選択してそ
の下側の加算回路32に与えるもので、右側と左側の選択
回路31はバス３上のシンボル対の内のそれぞれ偶数番目
と奇数番目のシンボルを受ける。
【００３４】誤りの訂正に際してはまず誤り訂正手段30
のレジスタ33をクリアした後、選択指令Scにより選択回
路31に例えば誤りの値Eiの方を選択させる。これにより
誤り位置ｉが偶数か奇数かに応じ選択回路31から誤りの
値Eiが右側または左側の加算回路32に与えられるので、
レジスタ32にラッチ指令LP３を与えて加算回路32からそ
れを読み取って記憶させる。誤りの値Eiを受けなかった
方の誤り訂正手段30のレジスタ33にはもちろん０が記憶
される。次に選択指令Scの論理値を切り換えてバス３上
のシンボルを選択回路31を介して加算回路32に与え、レ
ジスタ33の記憶内容に加算させ、さらにレジスタ33にラ
ッチ指令LP３を与えてこの加算の結果を記憶させる。こ
れにより、レジスタ33には誤りの値Eiを受けた方ではそ
の加算により訂正されたシンボルが記憶され、そうでな
い方では元のシンボルがそのまま記憶されているので、
例えばバスドライバであるバッファ回路34を介してそれ
をバス３に乗せてメモリ１に読み取らせる。
のレジスタ33をクリアした後、選択指令Scにより選択回
路31に例えば誤りの値Eiの方を選択させる。これにより
誤り位置ｉが偶数か奇数かに応じ選択回路31から誤りの
値Eiが右側または左側の加算回路32に与えられるので、
レジスタ32にラッチ指令LP３を与えて加算回路32からそ
れを読み取って記憶させる。誤りの値Eiを受けなかった
方の誤り訂正手段30のレジスタ33にはもちろん０が記憶
される。次に選択指令Scの論理値を切り換えてバス３上
のシンボルを選択回路31を介して加算回路32に与え、レ
ジスタ33の記憶内容に加算させ、さらにレジスタ33にラ
ッチ指令LP３を与えてこの加算の結果を記憶させる。こ
れにより、レジスタ33には誤りの値Eiを受けた方ではそ
の加算により訂正されたシンボルが記憶され、そうでな
い方では元のシンボルがそのまま記憶されているので、
例えばバスドライバであるバッファ回路34を介してそれ
をバス３に乗せてメモリ１に読み取らせる。
【００３５】以上説明した実施例に限らず本発明は種々
な態様で実施をすることができる。例えば、実施例では
符号語をすべてＲＳ符号によるとしたが本発明はこれと
密に関連するＢＣＨ符号（Bose-Chaudhuri-Hocquenghem
code)等を用いる符号語にも演算すべきシンドロームの
次数が若干変わってくるが同様に適用できる。また、シ
ンボルはすべて８ビットとしたがそれが任意の複数ビッ
トあるいは単一ビット構成であっても本発明を適用でき
る。
な態様で実施をすることができる。例えば、実施例では
符号語をすべてＲＳ符号によるとしたが本発明はこれと
密に関連するＢＣＨ符号（Bose-Chaudhuri-Hocquenghem
code)等を用いる符号語にも演算すべきシンドロームの
次数が若干変わってくるが同様に適用できる。また、シ
ンボルはすべて８ビットとしたがそれが任意の複数ビッ
トあるいは単一ビット構成であっても本発明を適用でき
る。
【００３６】
【発明の効果】以上説明したとおり本発明の復号方式で
は、符号語のシンドロームが複数項の和や積の和の形の
多項式で表され, 項の加算順序を組み換えてもシンドロ
ームの演算結果は変わらない点に着目して、シンボルの
系列としてなる符号語の復号に際して系列から所定個数
ごとにシンボルを抽出して部分系列を作り、各部分系列
ごとに部分演算手段を設けて複数の部分系列に関する部
分シンドロームの演算を同時に進行させ、統合演算手段
により複数個の部分シンドロームを組み合わせて符号語
に関するシンドロームに統合することにより、以下に述
べる効果を挙げることができる。
は、符号語のシンドロームが複数項の和や積の和の形の
多項式で表され, 項の加算順序を組み換えてもシンドロ
ームの演算結果は変わらない点に着目して、シンボルの
系列としてなる符号語の復号に際して系列から所定個数
ごとにシンボルを抽出して部分系列を作り、各部分系列
ごとに部分演算手段を設けて複数の部分系列に関する部
分シンドロームの演算を同時に進行させ、統合演算手段
により複数個の部分シンドロームを組み合わせて符号語
に関するシンドロームに統合することにより、以下に述
べる効果を挙げることができる。
【００３７】(a) 符号語のシンボル系列を２個, 一般に
はｒ個の部分系列に分割して、部分系列ごとに設けた部
分演算手段によりそれらに関する部分シンドロームの演
算を並行して進行させ, 各部分演算に要する繰り返し演
算の回数を減少させることにより、シンドロームの演算
に要する時間を従来のほぼ２分の１, 一般にはｒ分の１
に短縮することができる。
はｒ個の部分系列に分割して、部分系列ごとに設けた部
分演算手段によりそれらに関する部分シンドロームの演
算を並行して進行させ, 各部分演算に要する繰り返し演
算の回数を減少させることにより、シンドロームの演算
に要する時間を従来のほぼ２分の１, 一般にはｒ分の１
に短縮することができる。
【００３８】(b) 符号語のシンボル系列から所定個数ご
とにシンボルを抽出して部分系列を作り、メモリからの
シンボルの読み出しに同期して複数の部分系列に関する
部分演算を同時に進行させることにより、メモリへのア
クセスに要する時間を従来の２分の１, 一般にはｒ分の
１に短縮することができ、さらには複数の部分シンドロ
ームの演算をすべて同じ要領で進め, かつ統合演算手段
により容易に符号語のシンドロームに統合できるように
なる。
とにシンボルを抽出して部分系列を作り、メモリからの
シンボルの読み出しに同期して複数の部分系列に関する
部分演算を同時に進行させることにより、メモリへのア
クセスに要する時間を従来の２分の１, 一般にはｒ分の
１に短縮することができ、さらには複数の部分シンドロ
ームの演算をすべて同じ要領で進め, かつ統合演算手段
により容易に符号語のシンドロームに統合できるように
なる。
【００３９】このように、本発明方式はシンドロームの
演算とメモリへのアクセスに時間を要する従来からの問
題を簡単な構成で解決して、符号語の復号に用いる集積
回路装置等の実用性を大幅に高める貢献を果たし得るも
のである。なお、リード・ソロモン符号による符号語の
構成シンボルを拡張ガロア体上の８ビットの元とする態
様は実用上最も利用価値が高い本発明の適用形態であ
り、シンボル系列を偶数番目と奇数番目のシンボルから
なる２個の部分系列に分ける態様は最も容易に実施でき
る利点がある。復号すべき符号語用のバスにシンボル系
列中のシンボルを部分系列数に対応する個数ずつ乗せて
部分演算手段に並列に読み込む態様は、上述のアクセス
時間の短縮効果のほかにプロセッサ等の例えば16ビット
の内部バスをそのまま利用して符号語を復号できる利点
がある。
演算とメモリへのアクセスに時間を要する従来からの問
題を簡単な構成で解決して、符号語の復号に用いる集積
回路装置等の実用性を大幅に高める貢献を果たし得るも
のである。なお、リード・ソロモン符号による符号語の
構成シンボルを拡張ガロア体上の８ビットの元とする態
様は実用上最も利用価値が高い本発明の適用形態であ
り、シンボル系列を偶数番目と奇数番目のシンボルから
なる２個の部分系列に分ける態様は最も容易に実施でき
る利点がある。復号すべき符号語用のバスにシンボル系
列中のシンボルを部分系列数に対応する個数ずつ乗せて
部分演算手段に並列に読み込む態様は、上述のアクセス
時間の短縮効果のほかにプロセッサ等の例えば16ビット
の内部バスをそのまま利用して符号語を復号できる利点
がある。
【００４０】さらに、複数の部分演算手段を同じ回路構
成とする実施態様, および部分演算手段と統合演算手段
に組み込む乗算回路に線状フィードバックシフトレジス
タを用い, 乗算動作時のそのシフト回数をシンドローム
の次数に応じ設定して０次のシンドローム用以外の部分
演算手段や統合演算手段をすべて同じ回路構成とする実
施態様はシンドロームの演算回路を簡単に構成できる効
果を有する。
成とする実施態様, および部分演算手段と統合演算手段
に組み込む乗算回路に線状フィードバックシフトレジス
タを用い, 乗算動作時のそのシフト回数をシンドローム
の次数に応じ設定して０次のシンドローム用以外の部分
演算手段や統合演算手段をすべて同じ回路構成とする実
施態様はシンドロームの演算回路を簡単に構成できる効
果を有する。
【００４１】本発明を誤りの訂正に適用する際に、誤り
訂正手段を１対設けてシンドロームから求められた誤り
を含むシンボルの符号語内の位置と誤りの値に基づき誤
りの値を受ける誤り訂正手段を誤り位置に応じ切り換え
ながら, 誤りの値を加算して訂正する態様は、マイクロ
プロセッサ等の内部バスを利用して誤りの訂正を能率よ
く進め得る利点があり、各誤り訂正手段内に選択回路を
組み込んで加算回路に誤りの値と誤りを含むシンボルを
順次与えながら訂正を進める態様、および誤り位置と誤
りの値を受ける切換手段を用い, 誤りを含むシンボルが
偶数番目か奇数番目かに応じて誤りの値を与える誤り訂
正手段を選択する態様は、いずれも誤り訂正手段の回路
構成を簡易化する効果を有する。
訂正手段を１対設けてシンドロームから求められた誤り
を含むシンボルの符号語内の位置と誤りの値に基づき誤
りの値を受ける誤り訂正手段を誤り位置に応じ切り換え
ながら, 誤りの値を加算して訂正する態様は、マイクロ
プロセッサ等の内部バスを利用して誤りの訂正を能率よ
く進め得る利点があり、各誤り訂正手段内に選択回路を
組み込んで加算回路に誤りの値と誤りを含むシンボルを
順次与えながら訂正を進める態様、および誤り位置と誤
りの値を受ける切換手段を用い, 誤りを含むシンボルが
偶数番目か奇数番目かに応じて誤りの値を与える誤り訂
正手段を選択する態様は、いずれも誤り訂正手段の回路
構成を簡易化する効果を有する。
【図１】本発明による符号語の復号方式をシンドローム
の演算に適用した実施例を示す回路図である。
の演算に適用した実施例を示す回路図である。
【図２】本発明方式を誤りの訂正に適用した実施例を示
す回路図である。
す回路図である。
【図３】従来の復号方式におけるシンドローム演算回路
の回路図である。
の回路図である。
１ 受信符号語のシンボル系列を記憶するメモリ 1a 誤り位置と誤りの値を記憶するメモリ ２ メモリに対するアドレス指定回路 2a メモリに対するアドレスの補助指定回路 3,3a バス 3b 誤り位置を記憶するレジスタ 3c 誤りの値を記憶するレジスタ 10 部分演算手段 11 部分演算手段用の加算回路 12 部分演算手段用のレジスタ 13 部分演算手段用の乗算回路 20 統合演算手段 21 統合演算手段用の加算回路 22 統合演算手段用のレジスタ 23 統合演算手段用の乗算回路 30 誤り訂正手段 31 誤り訂正手段用の選択回路 32 誤り訂正手段用の加算回路 33 誤り訂正手段用のレジスタ 34 誤り訂正手段用のバッファ回路 40 誤り訂正用の切換回路 41,42 切換回路用のアンドゲート S0 ０次のシンドローム S1 １次のシンドローム Sp ｐ次のシンドローム
Claims (12)
- 【請求項１】シンボルが並んだ系列としてなる符号語を
復号するためそれに関するシンドロームを求める際に、
シンボル系列から所定個数ごとに抽出されたシンボルか
らなる複数の部分系列ごとに部分演算手段を設けて部分
系列に関するシンドロームの部分演算を同時に進行させ
た上で、統合演算手段により複数個の部分演算結果を組
み合わせて符号語に関するシンドロームを演算するよう
にしたことを特徴とする符号語の復号方式。 - 【請求項２】請求項１に記載の方式において、復号すべ
き符号語用のバスにシンボル系列のシンボルを部分演算
手段に対応する個数ずつ同時に乗せ、各部分演算手段に
これらのシンボルをバスから並列に読み込むようにした
ことを特徴とする符号語の復号方式。 - 【請求項３】請求項１に記載の方式において、各部分演
算手段がシンボルの加算回路とその加算結果に対する乗
算回路とを含み、加算回路により乗算回路の乗算結果に
対して部分系列内の各シンボルを順次繰り返して加算し
て行くことにより、各部分系列に関するシンドロームを
演算するようにしたことを特徴とする符号語の復号方
式。 - 【請求項４】請求項３に記載の方式において、複数の部
分演算手段をすべて同じ回路構成とするようにしたこと
を特徴とする符号語の復号方式。 - 【請求項５】請求項１に記載の方式において、統合演算
手段として部分演算手段の演算結果に対する乗算回路お
よびその乗算結果に対する加算回路を用い、１個を除く
部分演算手段に対し乗算回路を設けてその乗算結果と１
個の部分演算手段による演算結果を加算することにより
符号語のシンドロームを求めるようにしたことを特徴と
する符号語の復号方式。 - 【請求項６】請求項３または５に記載の方式において、
乗算回路として線状フィードバックシフトレジスタを用
い、その乗算動作のためのシフト動作回数を符号語に関
し求めるべきシンドロームの次数に応じて設定するよう
にしたことを特徴とする符号語の復号方式。 - 【請求項７】請求項６に記載の方式において、０次のシ
ンドローム以外用の部分演算手段および統合演算手段を
同じ回路構成とするようにしたことを特徴とする符号語
の復号方式。 - 【請求項８】請求項１に記載の方式において、２個の部
分演算手段を設けてシンボル系列の偶数番目および奇数
番目のシンボルに対する部分演算をそれぞれ分担させる
ようにしたことを特徴とする符号語の復号方式。 - 【請求項９】請求項１に記載の方式において、符号語に
はリード・ソロモン符号が用いられ、符号語を構成する
シンボルが拡張ガロア体上の８ビット構成の元であるこ
とを特徴とする符号語の復号方式。 - 【請求項１０】請求項１に記載の方式において、誤り訂
正手段を２個設けてシンドロームから求められた誤りを
含むシンボルの符号語内の位置と誤りの値に基づき誤り
の値を与えるべき誤り訂正手段を誤り位置に応じて切り
換えながら、誤りを含むシンボルを誤りの値を加算する
ことにより訂正するようにしたことを特徴とする符号語
の復号方式。 - 【請求項１１】請求項１０に記載の方式において、誤り
訂正手段として選択回路と加算回路とその加算結果を記
憶するレジスタを用い、選択回路により加算回路に誤り
の値とシンボルの値を切り換えて順次与えながらそのつ
どレジスタの記憶内容に加算させた上で、レジスタから
訂正済みのシンボルを取り出すようにしたことを特徴と
する符号語の復号方式。 - 【請求項１２】請求項１０に記載の方式において、誤り
位置と誤りの値とを受ける切換手段を用い、誤り位置が
示す符号語内の誤りがあるシンボルの番号が偶数か奇数
かに応じて誤りの値を与えるべき誤り訂正手段を選択す
るようにしたことを特徴とする符号語の復号方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7316206A JPH09162753A (ja) | 1995-12-05 | 1995-12-05 | 符号語の復号方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7316206A JPH09162753A (ja) | 1995-12-05 | 1995-12-05 | 符号語の復号方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH09162753A true JPH09162753A (ja) | 1997-06-20 |
Family
ID=18074488
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7316206A Pending JPH09162753A (ja) | 1995-12-05 | 1995-12-05 | 符号語の復号方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH09162753A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008226300A (ja) * | 2007-03-09 | 2008-09-25 | Nec Electronics Corp | 復号方法及び復号回路 |
| US7458007B2 (en) * | 2000-02-18 | 2008-11-25 | Texas Instruments Incorporated | Error correction structures and methods |
| US7644342B2 (en) | 2001-11-21 | 2010-01-05 | Kabushiki Kaisha Toshiba | Semiconductor memory device |
-
1995
- 1995-12-05 JP JP7316206A patent/JPH09162753A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7458007B2 (en) * | 2000-02-18 | 2008-11-25 | Texas Instruments Incorporated | Error correction structures and methods |
| US7644342B2 (en) | 2001-11-21 | 2010-01-05 | Kabushiki Kaisha Toshiba | Semiconductor memory device |
| JP2008226300A (ja) * | 2007-03-09 | 2008-09-25 | Nec Electronics Corp | 復号方法及び復号回路 |
| US8055985B2 (en) | 2007-03-09 | 2011-11-08 | Renesas Electronics Corporation | Decoding method and decoding circuit |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5170399A (en) | Reed-Solomon Euclid algorithm decoder having a process configurable Euclid stack | |
| US6374383B1 (en) | Determining error locations using error correction codes | |
| US5446743A (en) | Coefficient updating method and apparatus for Reed-Solomon decoder | |
| US6119262A (en) | Method and apparatus for solving key equation polynomials in decoding error correction codes | |
| JP3233860B2 (ja) | リードソロモン復号器 | |
| US5517509A (en) | Decoder for decoding ECC using Euclid's algorithm | |
| JPH0831803B2 (ja) | 誤り訂正のための方法と装置 | |
| US5805617A (en) | Apparatus for computing error correction syndromes | |
| US4841300A (en) | Error correction encoder/decoder | |
| US5583499A (en) | Method and apparatus for computing error locator polynomial for use in a Reed-Solomon decoder | |
| KR100258952B1 (ko) | 새로운 다항식 배열 구조를 채용한 리드-솔로몬(rs) 복호기와그 복호방법 | |
| JP3502583B2 (ja) | 誤り訂正方法および誤り訂正装置 | |
| KR100258951B1 (ko) | 리드-솔로몬(rs) 복호기와 그 복호방법 | |
| US6978415B1 (en) | Variable redundancy cyclic code encoders | |
| KR100305618B1 (ko) | 다목적에러교정계산회로 | |
| WO2003096546A2 (en) | A method of soft-decision decoding of reed-solomon codes | |
| US6263471B1 (en) | Method and apparatus for decoding an error correction code | |
| US5471486A (en) | Methods and devices for encoding data symbols in accordance with a BCH code to obtain a code word in which parity symbols are located in the middle of the code word | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| JPH0865175A (ja) | リードソロモン復号器の誤り位置検出回路 | |
| US5787100A (en) | Apparatus for determining error evaluator polynomial for use in a Reed-Solomon decoder | |
| EP0584864B1 (en) | A hardware-efficient method and device for encoding BCH codes and in particular Reed-Solomon codes | |
| JPH0750595A (ja) | 復号化装置 | |
| JP2000295116A (ja) | 誤り修正符号化方法 | |
| JP2752510B2 (ja) | 誤り訂正復号器 |