JP3234130B2

JP3234130B2 - 誤り訂正符号復号化方法およびこの方法を用いる回路

Info

Publication number: JP3234130B2
Application number: JP13246195A
Authority: JP
Inventors: 英夫吉田
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1995-05-30
Filing date: 1995-05-30
Publication date: 2001-12-04
Anticipated expiration: 2016-12-04
Also published as: US6336203B1; CN1334647A; US6052820A; CN1140363A; FR2736479B1; JPH08330975A; US6024485A; US5951708A; CN1172447C; CN1334646A; CN1334645A; KR960043552A; FR2736479A1; CN1084966C; KR100210583B1

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は誤り訂正符号復号化方
法及びその回路に係り、特に、データ伝送あるいはデー
タ記録などのデータ送出において、情報シンボルより大
きなシンボル上で構成するリードソロモン符号の符号化
および復号化の方法およびこれを実現するための回路に
関する。

【０００２】

【従来の技術】一般に、ディジタル情報を伝送する際に
は、誤り訂正符号がよく用いられる。例えば、文献「符
号理論」（今井秀樹著、電子情報通信学会編、平成２年
３月１５日初版発行）には、さまざまな誤り訂正符号復
号化方法が開示されている。その中でも、リードソロモ
ン符号は、８ビットをシンボルとしてシンボル誤り訂正
ができる点で、コンピュータあるいはディジタル機器と
の整合性が高く、情報伝送や情報記録などの多くの装置
に適用されている。

【０００３】一方、フラッシュメモリは、書き込み消去
ができる上に、電源がなくてもデータを保存でき、また
ＤＲＡＭ以上に高集積化ができるデバイスとして注目さ
れており、メモリディスクとしての応用が期待されてい
る。しかし、フラッシュメモリは、書き込みおよび消去
を繰り返していると内部のセルが破壊され、データを破
壊する可能性がある。このため、フラッシュメモリにデ
ータの記録を行う場合は、誤り訂正符号を用いることが
多い。また、データの消去を行った場合、データは全て
“１”となるので、これをチェックして消去の確認を行
う。

【０００４】一般に、ディスクメモリにデータを記録す
る場合、情報データの５１２バイトを１セクタとして記
憶する。また、メモリも８ビットを単位として記憶する
ため、８ビットを１シンボルとするリードソロモン符号
が用いられる。しかし、８ビットを１シンボルとするリ
ードソロモン符号では、符号長が一般に２５５までしか
とれないために、複数の符号語に分ける方法が用いられ
る。

【０００５】これに対して、例えば、符号長が、一般に
１０２３シンボルまで可能な、１シンボルを１０ビット
とするリードソロモン符号を用いることによって、１セ
クタのデータを１符号語のリードソロモン符号で保護す
る方法も用いられている。

【０００６】図１５は、かかる従来の誤り訂正符号復号
化方法における符号の構成例を示す説明図であり、特に
（４１８、４１０）リードソロモン符号を示している。

【０００７】ここで、“４１８”は符号シンボル長、
“４１０”は情報長であり、４シンボルの訂正が可能で
ある。図１５において、３０は短縮符号部分、３１は実
情報データシンボル部分、３２はチェックシンボル部
分、３６はダミーシンボル部分を示している。

【０００８】さて、図１５に示すリードソロモン符号
は、本来、符号長１０２３シンボルの符号であるが、短
縮符号部分３０の６０５シンボルは、０であるものとし
て符号化する。また１セクタを５１２バイトとすると、
４０９６ビットとなり、１０ビット／シンボルとするに
は、４ビット足りない。このため、４ビットのダミーシ
ンボル部分３６を付加し、それより実情報データシンボ
ル部分３１を４１０シンボルとして、チェックシンボル
部分３２を８シンボル、つまり１０ビット生成する。

【０００９】次に、図１５のリードソロモン符号のチェ
ックバイトを生成する符号化回路を図１６を用いて説明
する。なお、ここでは、フラッシュメモリで一般的に処
理されるようにデータの入力は８ビット単位、チェック
シンボルの出力も８ビット単位とする。さて、図１６に
おいて、２２は８ビット構成の情報データ入力端子、１
９は８ビット／１０ビット変換回路、２３はＧＦ（２Ｅ
１０）上のリードソロモン符号の符号化回路、２６は８
ビットのチェックシンボル出力端子、２９は１０ビット
／８ビット変換回路である。

【００１０】次に、図１６の構成の動作を説明する。符
号化回路２３では、リードソロモン符号のチェックシン
ボルが生成される。そのため、予め、符号化回路２３は
“０”クリアされている。

【００１１】まず、８ビットの情報データが情報データ
入力端子２２より入力され、８ビット／１０ビット変換
回路１９に入る。８ビット／１０ビット変換回路１９で
は、１０ビットの情報が蓄えられれば、その情報を符号
化回路２３に入力する。

【００１２】図１５におけるダミーシンボル部分３６の
４ビットを含め、実情報データシンボル部分３１が全て
符号化回路２３に入力されると、８シンボル（８０ビッ
ト）のチェックシンボル部分３２が得られる。すなわ
ち、短縮符号部分３０は計算を行う必要がない。

【００１３】チェックシンボル部分３２は、１０ビット
／８ビット変換回路２９により、上位から１０ビット／
８ビット変換され、８ビット毎にチェックバイトデータ
がチェックシンボル出力端子２６より出力される。すな
わち、１０バイトのデータがチェックシンボルとして出
力される。

【００１４】次に、図１７を用いて、従来の復号化方
法、特にシンドローム計算について説明する。ちなみ
に、図１７の構成は、フラッシュメモリを想定して、デ
ータの消去チェックの機能も含んでいる。さて、図１７
において、１は８ビットの受信データを入力するための
データ入力端子、５はＧＦ（２Ｅ１０）上のガロア体加
算回路、７は１０ビットのレジスタ、８はＧＦ（２Ｅ１
０）上のガロア体係数乗算回路、９はシンドローム出力
端子、２０は８ビットデータが全て“１”、つまりＨＥ
Ｘコードで“ＦＦ”であるか否かをチェックするＦＦチ
ェック回路、２１は消去検査フラグ出力端子である。

【００１５】まず、誤り訂正としての復号であるが、レ
ジスタ７は予め０クリアされているものとする。データ
入力端子１より入力された受信データは、８ビット／１
０ビット変換回路１９に入力される。８ビット／１０ビ
ット変換回路１９で、１０ビットのデータが蓄えられれ
ば、その情報は、ガロア体係数乗算回路８の出力と、ガ
ロア体加算回路５においてガロア体加算される。そし
て、加算結果はレジスタ７に入力される。ちなみに、レ
ジスタ７の出力はガロア体係数乗算回路８の入力端子に
送出される。

【００１６】これを、図１５における実情報データシン
ボル部分３１およびチェックシンボル部分３２について
全て入力した時のレジスタ７の状態がシンドロームＳ_j
となり、シンドローム出力端子９より出力される。

【００１７】この時、リードソロモン符号の先頭データ
シンボルが“０”で、シンボル単位でスリップが生じて
いても、リードソロモン符号が巡回符号であることか
ら、訂正によりスリップしたまま復号する可能性があ
る。

【００１８】一方、フラッシュメモリにおいてデータを
消去した場合、データは全て“１”となるが、その消去
が異常なく実行されたか否かを調べる必要がある。

【００１９】この場合は、データ入力端子１よりの８ビ
ットデータは、ＦＦチェック回路２０に入り、１ビット
でも“０”が検出されれば、異常フラグを消去検査フラ
グ出力端子２１より出力する。

【００２０】さて、従来から、誤り訂正を行う場合、積
符号の構成である符号の復号では、一旦メモリに蓄えた
上で、復号を行う。図１８は、このような場合の例を示
す回路ブロック図である。図において、５９はバッファ
メモリ、６０はシンドローム回路、６３は誤り位置およ
び大きさを求める誤り位置／大きさ検出回路、６４は訂
正回路、６５は訂正後の復号データ出力端子である。

【００２１】以上のような構成において、データ入力端
子１から入力された符号化データは、バッファメモリ５
９に蓄えられ、その後にインターリーブを解かれ、符号
化系列にされシンドローム回路６０に入力される。そこ
で得られたシンドロームを基に、誤り位置／大きさ検出
回路６３で誤り位置およびその大きさを求め、訂正回路
６４でバッファメモリ５９にある誤り位置のデータを読
み出し、誤りを訂正してバッファメモリ５９に書き込
む。積符号などでは、この復号操作を複数回繰り返し、
全て復号して復号データ出力端子６５より出力する。

【００２２】以上のような操作を、ひとつのバッファメ
モリで行う場合、受信データの入力、シンドローム回路
への出力、誤り位置のデータ入出力、訂正したデータの
出力などを、時分割で行う必要がある。特に、積符号な
どの複数回繰り返し復号を行う場合、高速アクセス可能
なバッファメモリを用いる必要がある。

【００２３】さて、メモリ等の信頼性を保持するため
に、１ビット誤り訂正、２ビット誤り検出符号が良く用
いられる。（７２、６４）バイナリ線形符号はその代表
的な例である。ここで、“７２”はビット符号長、“６
４”はビット情報長である。すなわち、チェックビット
は８ビットである。

【００２４】このような符号の復号回路は、一般に、符
号ビットデータの全てを並列で処理して復号することが
多く、併せて、誤りを検出するための回路を有すること
が多い。このような符号については、例えば、文献「フ
ォールトトレランスシステム論」（当麻喜弘編著、電子
情報通信学会編、平成２年６月１０日初版発行）に示さ
れている。

【００２５】図１９は、（７２、６４）バイナリ線形符
号の復号回路の従来例を示す回路ブロック図である。図
において、６６はシンドローム回路６０からの信号を入
力される８入力ＯＲ回路、６７は誤り位置／大きさ検出
回路６３からの信号を入力される７２ビット入力ＮＯＲ
回路、６８は８入力ＯＲ回路６６と７２ビット入力ＮＯ
Ｒ回路６７の出力を与えられる２入力ＡＮＤ回路、４９
は２入力ＡＮＤ回路６８からの訂正不可検出フラグを出
力するための訂正不可検出フラグ出力端子である。

【００２６】以上のような構成において、メモリの誤り
訂正の場合、データバスがパラレルに構成されるため、
７２ビットの符号データがシンドローム回路６０に一度
に入力される。シンドローム回路６０では、受信データ
より８ビットのシンドロームを生成して出力する。誤り
位置／大きさ検出回路６３は、パリティ検査行列により
決定されるチェックビットを含む各ビット位置の８ビッ
トのパターンと、シンドロームが一致するかどうかを検
査する。その結果は、７２ビット入力ＮＯＲ回路６７と
訂正回路６４に送られる。このとき、訂正回路６４には
情報部分の６４ビットを送る。訂正回路６４では、受信
した各情報ビットと各ビットの誤り検出結果とを、それ
ぞれ排他的論理和演算し、その結果を、復号データ出力
端子６５より出力する。

【００２７】なお、この符号では２ビット誤りに対する
誤り検出が行われる。これは、シンドロームが“０”で
なく、かつ７２ビットの符号長のパリティ検査行列のパ
ターンに合致しない場合、訂正不可であり誤り検出とな
る。８入力ＯＲ回路６６は、シンドロームの８ビットが
“０”でないことを検査し、７２ビット入力ＮＯＲ回路
６７は１ビット誤りではないことを検査し、２入力ＡＮ
Ｄ回路６８で２つの検査結果の論理積をとって訂正不可
検出フラグ出力端子４９から出力する。

【００２８】以上のような構成および作用については、
例えば特公昭５３−５０９９（Ｄ．Ｗ．プライス、１９
７２年１１月８日出願）にも示されている。

【００２９】

【発明が解決しようとする課題】従来の誤り訂正符号復
号化方法は、以上のように構成されていたので、次に述
べるような数々の課題を残している。

【００３０】第１の課題として、８ビット入出力データ
に対して、例えば１シンボル１０ビットのリードソロモ
ン符号を用いる場合、８ビット／１０ビット変換回路や
１０ビット／８ビット変換回路が必要であり、シンボル
クロックも８ビット用と１０ビット用を生成する必要が
あり、ビットクロックが必要であった。

【００３１】第２の課題として、フラッシュメモリの消
去のチェックのためには、全て“１”であることをチェ
ックする特別の回路が必要であった。

【００３２】第３の課題は、リードソロモン符号がシン
ボル単位でスリップを生じていても、リードソロモン符
号が巡回符号であることから、訂正によりスリップした
まま復号する可能性がある。

【００３３】第４の課題は、符号化データをメモリに蓄
えた場合、メモリは受信データの入力、復号回路への入
出力、復号結果の出力を時分割でアクセスすることにな
るため、複数回の復号のためには、高速アクセスのメモ
リが必要である。

【００３４】第５の課題は、メモリの誤り訂正に用いる
（７２、６４）バイナリ線形符号において、誤り訂正不
可フラグを出力するために、７２ビットの１ビット誤り
検査と、その結果の論理演算を行う回路が必要であり、
そのために大きな遅延時間を余儀なくされると共に論理
演算のために多くのゲート数の回路が必要である。

【００３５】この発明は上記のような従来技術の問題点
を解消するためになされたもので、８ビットシンボルの
みを扱うようにすると共に冗長な回路を省略することに
より簡単な構成で誤り訂正および符号復号化を行うこと
を可能にすると共に信頼性に優れた誤り訂正符号復号化
方法及びその回路を提供することを目的とする。

【００３６】

【課題を解決するための手段】上記目的を達成するため
に、この発明は、請求項１に記載の誤り訂正符号復号化
方法として、情報データのシンボルよりも大きなシンボ
ル上で構成するリードソロモン符号の符号化および復号
化方法において、情報シンボルのビット長を越えるリー
ドソロモン符号のシンボルのビットデータは、ダミーデ
ータを設定して送出しないプロセスと、復号では情報部
分のシンボルにリードソロモン符号のシンボルとして不
足するビットデータとして予めダミーデータを付加する
プロセスと、チェックシンボル部分は、情報シンボルの
ビット長に相当する部分はそのまま送出し、情報シンボ
ルのビット長を越える部分は、情報シンボルのビット長
に相当するチェックシンボル部分を送出した後に情報シ
ンボルのビット長ごとにまとめて送出するプロセスと、
復号では先に送出された情報シンボルのビット長に相当
するチェックシンボル部分は、ダミーデータを付加して
そのままシンドローム計算し、後に送出された情報シン
ボルのビット長を越える部分のまとめられたデータに対
しては、そのチェックビットデータに基づくシンドロー
ム計算を行うプロセスと、先に得られている情報および
チェックシンボルからシンドロームとガロア体加算する
プロセスと、を備える誤り訂正符号復号化方法を提供す
るものである。

【００３７】上記目的を達成するために、この発明は、
請求項７に記載の誤り訂正符号復号化方法として、誤り
訂正符号の符号化および復号化を行うに当たって、情報
およびチェックバイトを全て０／１反転して送出し、復
号では読み出されたデータを０／１反転してから復号す
る、プロセスを備える誤り訂正符号復号化方法を提供す
るものである。

【００３８】上記目的を達成するために、この発明は、
請求項９に記載の誤り訂正符号復号化方法として、符号
長を短縮した誤り訂正符号の符号化および復号化におい
て、情報およびチェックシンボルが全て“１”になるデ
ータが符号となるように、短縮部分にデータパターンを
付加してチェックシンボルを生成し、情報およびチェッ
クシンボルのみを送出するプロセスと、復号側におい
て、短縮部分のデータに相当するシンドロームデータを
情報およびチェックシンボルより生成されるシンドロー
ムに付加するプロセスと、を備える誤り訂正符号復号化
方法を提供するものである。

【００３９】上記目的を達成するために、この発明は、
請求項１５に記載の誤り訂正符号復号化方法として、符
号長を短縮した誤り訂正符号の符号化および復号化にお
いて、情報の１シンボル前の短縮部分に、その符号固有
のデータパターンを付加してチェックシンボルを生成
し、情報およびチェックシンボルのみ送出するプロセス
と、復号側で、短縮部分に付加した符号固有データパタ
ーンに相当するシンドロームを、情報およびチェックシ
ンボルより生成されるシンドロームに付加するプロセス
と、を備える誤り訂正符号復号化方法を提供するもので
ある。

【００４０】上記目的を達成するために、この発明は、
請求項２２に記載の誤り訂正復号化回路として、受信し
た誤り訂正符号化されたデータを入力部よりバッファメ
モリに蓄え前記誤り訂正符号により複数回復号操作を行
う復号回路において、誤り訂正符号化されたデータをバ
ッファメモリに蓄えて複数回の復号操作を行うプロセス
と、入力データに対するシンドローム計算を行うと共に
バッファメモリのデータに対するシンドローム計算を行
うシンドローム計算手段と、２つのシンドロームを選択
すると共に誤りを訂正して復号を行う手段と、を備える
誤り訂正復号化回路を提供するものである。

【００４１】上記目的を達成するために、この発明は、
請求項２３に記載の誤り訂正符号復号化方法として、誤
り訂正符号化および復号化において、１ビット誤り訂
正、２ビット誤り検出を行う（７６、６４）バイナリ線
形符号において、パリティ検査行列の重みを、“１”、
“３”、“７”のみで処理するプロセス、を備える誤り
訂正符号復号化方法を提供するものである。

【００４２】

【作用】上記手段において、この発明の請求項１に記載
の誤り訂正符号復号化方法は、例えば情報８ビットを１
シンボルとして、それより大きいシンボルで構成される
リードソロモン符号に対して、不足するビットはダミー
データを与えて、１シンボルとし、これにより生成され
たリードソロモン符号のチェックシンボルは、情報と同
じ８ビットについては情報シンボルに続けて送出し、余
ったチェックシンボルのビットは、後からまとめて送る
ようにし、復号においては、８ビットの情報シンボルお
よび８ビットのチェックシンボルにダミービットを付加
してシンドローム計算を行い、後に続く余りをまとめた
チェックシンボルのビットデータに対しては、補正計算
を行う。

【００４３】上記手段において、この発明の請求項７に
記載の誤り訂正符号復号化方法は、例えば、情報および
チェックシンボルを全て反転した上でフラッシュメモリ
などに記録し、読み出しにおいては、これを全て反転し
て復号することで、フラッシュメモリの消去状態である
全“１”を、全“０”の符号化データとして扱うことを
可能にする。

【００４４】上記手段において、この発明の請求項９に
記載の誤り訂正符号復号化方法は、短縮部分に情報およ
びチェックバイトが全て“１”であっても符号となるよ
うにダミー情報を設定し、復号側においては、短縮部分
のデータに相当するシンドロームデータを情報およびチ
ェックシンボルより生成されるシンドロームに付加して
復号を行う。

【００４５】上記手段において、この発明の請求項１５
に記載の誤り訂正符号復号化方法は、短縮部分の先頭に
その符号固有のデータを与え、符号化においてはその固
有データに基づくチェックシンボルを生成して、情報お
よびチェックシンボルのみ送出し、復号においては、固
有データパターンに相当するシンドロームを情報および
チェックシンボルより生成されるシンドロームに付加し
て復号を行う。

【００４６】上記手段において、この発明の請求項２２
に記載の誤り訂正復号化回路は、入力データに対応する
シンドロームと、バッファメモリのデータに対するシン
ドロームを選択し、これに基づく誤り訂正と復号を行う
ことにより、バッファメモリへのアクセス回数を低減
し、バッファメモリの低速化を可能にする。

【００４７】上記手段において、この発明の請求項２３
に記載の誤り訂正符号復号化方法は、誤り訂正符号化お
よび復号化において、１ビット誤り訂正、２ビット誤り
検出を行う（７６、６４）バイナリ線形符号において、
パリティ検査行列の重みが“１”、“３”、“７”とな
るように構成し、誤り訂正不可の検出には、シンドロー
ムの重みを求め、この重み検出に基づく誤り訂正不可の
検出を行う。

【００４８】

【実施例】

実施例１．図１は、この発明の実施例１の誤り訂正符号
復号化方法を実現するための回路ブロック図であり、特
に１シンボル１０ビットの（１０２３、１０１５）リー
ドソロモン符号を短縮した（５２０、５１２）リードソ
ロモン符号符号のシンドローム演算までを示した復号回
路を示すものである。

【００４９】図において、２は１シンボル中の剰余ビッ
トである２ビットのダミーデータ（例えば、“００”を
入力するためのダミーデータ入力回路）、３はチェック
シンボルのオーバー分（２ビットＸ８シンボル）による
シンドロームデータを生成するシンドロームデータ補正
回路、４は１０ビットの２つのデータを選択して出力す
るセレクタ、５は従来のＧＦ（２Ｅ１０）上のガロア体
加算回路、７は１０ビットのレジスタ、８はＧＦ（２Ｅ
１０）上のガロア体係数乗算回路、６は１０ビットの２
つのデータを選択するセレクタ、９はシンドローム出力
端子、１０はデータ入力端子１に接続される０／１反転
回路である。

【００５０】ちなみに、この実施例１は、先に述べた第
１の課題と、第２の課題を解決するものである。

【００５１】以上述べたような構成において、次にその
動作を説明する。

【００５２】図１の構成においては、符号データは、全
て０／１が反転した状態で記録されているものとする。
つまり、データ入力端子１から入力される符号データ
は、８ビット単位で反転したデータである。このデータ
は、０／１反転回路１０において、反転される。すなわ
ち、記録データの全ビットが“１”の場合、符号は反転
して全て“０”となる。したがって、フラッシュメモリ
の消去において、消去データは全て“１”となるので、
０／１反転回路１０の出力としては、全て“０”の符号
としてシンドロームチェックできることになる。

【００５３】つまり、第２の課題が解決される。

【００５４】次に、第１の課題に対応する動作を説明す
る。

【００５５】まず、先に送られた５１２バイトの情報
は、剰余ビットである２ビットについて、例えば“０”
として符号化されており、受信側においても、ダミーデ
ータ入力回路２よりダミーデータ（例えば、“０”）を
付加して、１０ビットのシンボルとしてセレクタ４を介
してガロア体加算回路５に入力される。

【００５６】ガロア体加算回路５のもうひとつの入力
は、初期値を“０”とするレジスタ７から、ガロア体係
数乗算回路８を通じて、セレクタ６から出力されるデー
タである。この回路系は従来のシンドローム回路と同じ
演算を行う。

【００５７】次に、８シンボルチェックバイトが入力さ
れるが、これは情報シンボルと同じ８ビットのデータに
ついてのみ入力され、情報シンボル同様、ダミーデータ
入力回路２よりダミーデータ（例えば、“０”）を付加
して１０ビットのシンボルとしてセレクタ４よりガロア
体加算回路５に入力され、先の情報シンボルと同様にシ
ンドローム計算が行われる。

【００５８】最後に、符号の系列として、各チェックシ
ンボル中のオーバービット２ビットが、８ビット単位に
まとめられ、８ビットデータとして２シンボル入力され
る。このデータはシンドロームデータ補正回路３に入力
され、

【数２】なる、ＧＦ（２¹⁰）のガロア体係数乗算および加算が行
われる。ここで、ｄｉはＨＥＸコードで表現される００
０（ＨＥＸ）、１００（ＨＥＸ）、２００（ＨＥＸ）、
３００（ＨＥＸ）のいずれかである。ここで得られた補
正データは、前のチェックシンボルまでのシンドローム
データとガロア体加算回路５で加算される。ちなみに、
前のチェックシンボルは、レジスタ７から、セレクタ４
を通り、セレクタ６を通じて出力されるシンボルであ
る。そして、ガロア体加算回路５の加算結果は、再びレ
ジスタ７に記憶される。そして、これがシンドロームデ
ータＳ_jとしてシンドローム出力端子９より出力され
る。

【００５９】ここで、シンドロームデータ補正回路３の
構成の第１の例を図１０の回路ブロック図に基づいて説
明する。図において、３７は８ビットの受信データ入力
端子、３８〜４０はＧＦ（２¹⁰）上のガロア体係数乗算
回路、４１〜４４はＧＦ（２¹⁰）上のガロア体加算回
路、４５は１０ビットのレジスタ、４６はＧＦ（２¹⁰）
上のガロア体係数乗算回路、４７は補正データ出力端子
である。

【００６０】以上のような構成において、次にその動作
を説明する。

【００６１】この例では、８ビットの入力に対して、４
シンボルのチェックシンボルの上位２ビットが一度に入
力され、それが２シンボル入る。８ビットで受信データ
入力端子３７より入力されたシンボルが、それに対し、
チェックシンボルの次数の高い方から順にα^3j、α^2j、
α^jの係数を有するガロア体係数乗算回路３８〜４０
に、それぞれ入力され、その結果がガロア体加算回路４
１〜４３で加算される。

【００６２】これらは、上位２ビットのみ“１”になる
ので、下位８ビットに関係する論理回路は省略でき、小
さな回路規模で実現できる。

【００６３】ガロア体加算回路４３の結果は、ガロア体
加算回路４４に入力され、ガロア体係数乗算回路４６の
出力と加算され、レジスタ４５に入力される。レジスタ
４５は初期値を“０”とし、その出力をガロア体係数乗
算回路４６に入力する。ガロア体係数乗算回路４６は、
図１におけるガロア体係数乗算回路８と同じ役割を果た
すが、ガロア体係数乗算回路８の４乗倍の係数乗算を行
う。これは、８ビットのデータに４シンボルのチェック
バイトの上位２ビットが割り当てられているためであ
る。次のチェックシンボルの上位２ビットのデータも、
同様に処理され、レジスタ４５に記憶される。以上のよ
うな処理を通じて、補正データの計算を終了する。

【００６４】次に、シンドロームデータ補正回路３の構
成の第２の例を図１１の回路ブロック図に基づいて説明
する。図１１の構成は、図１０に示した構成から、レジ
スタ４５およびガロア体加算回路４４を外して、セレク
タ４８を追加したものとなっている。

【００６５】以上のような構成において、次にその動作
を説明する。

【００６６】図１１の構成において、ガロア体加算回路
４３までの動作は、図１０の場合と同様である。

【００６７】一方、先に入力されたシンボルに対して得
られたガロア体加算回路４３の出力は、ガロア体係数乗
算回路４６を通り、セレクタ４８を通って、補正データ
出力端子４７より出力される。

【００６８】この結果を、図１のセレクタ４を通じて、
セレクタ６を通って出力されるレジスタ７の出力結果
と、ガロア体加算回路５で加算し、レジスタ７に記憶す
る。そして、次の８ビットシンボルデータによるガロア
体加算回路４３の出力を、そのままセレクタ４８を通
り、先のシンボルと同様の操作を行うことにより、シン
ドロームが得られる。

【００６９】実施例２．図２は、この発明の実施例２の
誤り訂正符号復号化方法を実現するための回路ブロック
図であり、特に第２の課題に対する解決を図るものであ
る。

【００７０】さて、実施例１では、符号化データを反転
して記録したので、全て“１”のデータが、情報が全て
“０”の符号なのか、消去によって全て“１”となって
いるのかの区別がつかないという問題点があったが、図
２の構成は、この問題を解決するものである。

【００７１】図２において、１１は８ビットの２入力デ
ータに対応したセレクタであり、データ入力端子１から
の入力を０／１反転回路１０を通じて取り込むか、直接
取り込むかの選択を行っている。

【００７２】以上のような構成において、通常において
は、データ入力端子１からの受信データをセレクタ１１
を通じて、直接取り込みシンドローム計算を行い、フラ
ッシュメモリの消去チェックの時のみ、０／１反転回路
１０を通じて入力されるデータをセレクタ１１で選択し
て取り出し、シンドローム計算する。

【００７３】なお、この場合は、通常の符号化データ
は、０／１の反転は行わずに記憶させる。

【００７４】ところで、この実施例２では、０／１反転
回路１０とセレクタ１１を分けて制御する構成を例示し
ているが、両者を合わせた機能は排他的論理和回路を用
いて実現できることは、周知である。

【００７５】実施例３．さて、実施例１、実施例２で
は、第２の課題に対して、０／１反転回路を用いて、フ
ラッシュメモリの消去、すなわち全て“１”の状態をチ
ェックする方法を示したが、この実施例３では、シンド
ロームのレジスタ７の初期値設定だけで、フラッシュメ
モリの消去のチェックが行える方法を提示する。また、
この実施例３では、第３の課題に対応して、シンボル単
位のスリップが生じても、これを検出できる方法を提示
する。

【００７６】図８は、この実施例３を実行するに当たっ
ての（５２０、５１２）リードソロモン符号の構成法を
示している。ちなみに、図８の符号構成は、実施例１に
おける、第１の課題の解決のためにも適用される。

【００７７】さて、図８において、３０は短縮符号部
分、３１は実情報データシンボル部分、３２はチェック
シンボル部分、３３は情報およびチェックシンボルが全
て“１”であっても、符号となるように挿入したダミー
シンボル、３４は１０ビットのチェックシンボルのうち
の各上位２ビットをまとめて符号系列の後ろに付加した
付加チェックシンボルである。

【００７８】さて、１０ビットを１シンボルとするリー
ドソロモン符号は、通常１０２３シンボルまでの符号長
をとることができる。そこで、図１５の従来例と異な
り、フラッシュメモリの記憶単位である８ビットの実情
報データシンボル部分３１を１シンボルとして、上位２
ビットにはダミーとして、例えば“０”を挿入する。こ
れにより、８ビット／１０ビットの変換が不要となる。

【００７９】この情報シンボルにより生成されるチェッ
クシンボル部分３２は、１シンボル当たり１０ビットで
あり、上位２ビットが固定データである保証はない。そ
こで、下位８ビットのみは８ビット情報シンボルに続い
て配置し、上位の２ビットは８ビット単位にまとめて、
チェックバイトであるチェックシンボル部分３２の後
に、剰余シンボルとして付加チェックシンボル３４を２
シンボル配置する。これらの動作は、シンボルクロック
処理できることであり、全ての操作がシンボルクロック
で可能になる。

【００８０】次に、第２、第３の課題に対する解決策と
なる符号構成を図８にしたがって説明する。例えば、１
シンボルを１０ビットとする（１０２３、１０１５）リ
ードソロモン符号の例として、原始多項を

【数３】とし、生成多項式を

【数４】とする。ただし、

【数５】であり、βはＰ（Ｘ）の原始元である。この場合、ダミ
ーデータの先頭部分を０番目、すなわち実情報シンボル
部分３１の先頭を５０３番目として、短縮符号部分３０
であるシンボル部分にダミーシンボル３３として、位置
２７８番目に１９Ｄ（ＨＥＸ）、４５４番目に０ＡＢ
（ＨＥＸ）を設定すると、図８における実情報データシ
ンボル部分３１が全て“１”、情報シンボルの上位２ビ
ット部分を“０”とした場合、チェックシンボル部分３
２の８シンボルは全て“１”となる。すなわち、フラッ
シュメモリの消去状態である全てが“１”の状態を図８
における（５２０、５１２）リードソロモン符号の符号
として見ることができる。

【００８１】次に、図８に示した符号構成における符号
化回路について説明する。

【００８２】図６は、図８における符号構成に対応した
符号化回路の構成例を示す回路ブロック図である。図に
おいて、２２は８ビットの情報データ入力端子、２は情
報シンボルの上位２ビットのダミーデータ入力回路、２
３は、例えば、線形帰還シフトレジスタタイプの初期位
置設定可能なＧＦ（２¹⁰）上の符号化回路、２４は符号
化回路２３のレジスタの初期値設定を行うための符号化
回路初期値データ設定回路、２５はチェックシンボルの
下位８ビットか上位２ビットを束ねて８ビットとしたシ
ンボルを出力として選択するセレクタ、２６はチェック
バイトデータを出力するチェックシンボル出力端子であ
る。

【００８３】図からも明らかなように、この回路構成は
従来の符号化回路と演算量、回路規模においてほとんど
変わらない構成となっている。

【００８４】以上述べたような構成において、次にその
動作を説明する。

【００８５】まず、８ビットの情報データが情報データ
入力端子２２に入る前に、図８におけるダミーシンボル
３３を入力し、符号化回路２３で計算する。しかし、ダ
ミーシンボル３３は固定値であるので、次に続く情報デ
ータが入力される前の符号化回路における状態は、事前
に計算しておくことができる。例えば、符号化回路２３
を、従来から用いられてきたような情報シンボルを入力
した時点でチェックシンボルが得られる線形帰還シフト
レジスタタイプとし、チェックシンボルを多項式次数の
係数とみなして、その計算途中となるレジスタの状態を
高次から見ると、１７４（ＨＥＸ）、０Ｂ６（ＨＥ
Ｘ）、１０５（ＨＥＸ）、０ＥＡ（ＨＥＸ）、２６Ｂ
（ＨＥＸ）、２６０（ＨＥＸ）、１８Ｆ（ＨＥＸ）、０
Ｄ７（ＨＥＸ）となる。したがって、この計算結果を、
符号化回路初期値データ設定回路２４から、符号化回路
２３のレジスタに対して、初期値として与えればよい。
ちなみに、このような初期値を与えるための構成は、例
えば、フリップフロップ回路のセット端子やリセット端
子にダイレクトにデータを設定するように構成すること
で実現できる。

【００８６】これに続いて、情報データ入力端子２２か
ら入力された８ビットの情報データは、２ビットのダミ
ーデータ入力回路２により、例えば“０”を２ビット付
加されて、１０ビットのシンボルデータの形で、符号化
回路２３に入力される。そして、５１２シンボルの８ビ
ット情報データを入力し終えた時点で、符号化回路２３
では８シンボルのチェックシンボルが得られている。た
だし、これは１シンボルを１０ビットとしたシンボルで
ある。そこで、まず各チェックシンボルの下位８ビット
についてセレクタ２５を通じて、チェックシンボル出力
端子２６より出力し、その後に、各チェックシンボルの
上位２ビットを８ビット単位にまとめてセレクタ２５を
通じてチェックシンボル出力端子２６より出力する。こ
れにより、全てのデータを８ビットの情報データのシン
ボルクロックで処理することが可能になる。

【００８７】次に、第２、第３の課題に対する解決策を
説明する。図７は、そのための構成例であり、２７は８
ビット排他論理和ゲートで構成されるガロア体加算回路
であり、２８は補正データをガロア体加算回路２７に与
えるためのチェックシンボル補正データ設定回路２８で
ある。図からも明らかなように、この回路はセレクタ２
５の出力までの構成は図６の構成と略同様である。ただ
し、初期値を設定するための回路を持たず、符号化回路
２３は情報データが入力される前に“０”クリアされ
る。

【００８８】以上述べたような構成において、次にその
動作を説明する。

【００８９】図７の構成では、符号化回路２３の初期設
定値を“０”とすること以外は、基本的に図６の構成と
同様の動作となる。そして、固定値として与えられるダ
ミーシンボルに対しては以下のように処理する。つま
り、リードソロモン符号は線形符号であるので、初期設
定値“０”より得られたチェックシンボルに対して、図
８におけるダミーシンボル３３に対するチェックシンボ
ルを、チェックシンボル補正データ設定回路２８からガ
ロア体加算回路２７を通じて、ガロア体加算すればよ
い。ここで、ダミーシンボル３３に対するチェックシン
ボルは、高次からみて、０４Ａ（ＨＥＸ）、０１５（Ｈ
ＥＸ）、３ＡＦ（ＨＥＸ）、２９４（ＨＥＸ）、１２５
（ＨＥＸ）、０９Ｆ（ＨＥＸ）、０２Ｂ（ＨＥＸ）、２
７４（ＨＥＸ）となる。セレクタ２５は８ビットずつの
出力となるので、チェックシンボル補正データ設定回路
２８の出力は、高次からみて、４Ａ（ＨＥＸ）、１５
（ＨＥＸ）、ＡＦ（ＨＥＸ）、９４（ＨＥＸ）、２５
（ＨＥＸ）、９Ｆ（ＨＥＸ）、２Ｂ（ＨＥＸ）、７４
（ＨＥＸ）、０Ｅ（ＨＥＸ）、４２（ＨＥＸ）となる。
そして、セレクタ２５の出力にチェックシンボル補正デ
ータ設定回路２８の出力を、ガロア体加算回路２７でガ
ロア体加算し、チェックシンボル出力端子２６から出力
する。

【００９０】次に、この実施例３における復号回路の例
を説明する。この発明の復号では、シンドローム計算に
特長があるので、実施例１と同様に、シンドローム回路
部分について示す。

【００９１】図３は、実施例３に適用される復号回路の
回路ブロック図であり、図１の構成と異なる点は、０／
１反転回路１０がなく、代わりにシンドローム初期デー
タ設定手段１２が付加された構成となっている。

【００９２】以上述べたような構成において、次にその
動作を説明する。

【００９３】８ビット単位で受信された受信データに
は、図８におけるダミーシンボル３３は入力されないの
で、図６の符号化回路での動作と同様に、レジスタ７に
情報データが入力される直前のダミーシンボル３３に対
応したシンドローム計算の途中結果を予め計算してお
き、これをシンドローム初期データ設定手段１２に設定
しておく。この時、例えば、先の例で示したのと同じパ
ラメータでは、シンドロームＳ₀〜Ｓ₇は、

【数６】

【数７】

【数８】

【数９】

【数１０】

【数１１】

【数１２】

【数１３】が設定される。その後の動作は、実施例１における図１
の構成と、０／１反転回路１０がないだけで、同様であ
る。

【００９４】次に、図７で説明した符号化回路同様、情
報データに対するシンドロームを求めた後に、図８にお
けるダミーシンボル３３のシンドロームデータに補正す
る方法について説明する。図４はそのための回路構成を
示す回路ブロック図であり、図６におけるシンドローム
初期データ設定手段１２に代わってシンドローム補正デ
ータ設定回路１４を設けている。また、１３はＧＦ（２
¹⁰）上のガロア体加算を行うガロア体加算回路１３で、
排他的論理和ゲートで構成される。

【００９５】図４の構成の動作は、シンドローム回路部
分のレジスタ７の初期値データ設定が全て“０”となる
以外は、図６の構成と同様の演算となる。

【００９６】受信データが全て入力され、シンドローム
が得られ、シンドローム出力端子９より出力される時、
シンドローム補正データ設定回路１４からそれぞれ図８
におけるダミーデータのシンドローム数値をガロア体加
算回路１３で、受信データからのシンドロームと加算す
る。この補正データは、例えば、先の例で示したパラメ
ータでは、シンドロームＳ₀〜Ｓ₇に対して、それぞれ

【数１４】

【数１５】

【数１６】

【数１７】

【数１８】

【数１９】

【数２０】

【数２１】が設定される。

【００９７】なお、第２、第３の課題に対する解決策と
して、本発明では、ダミーシンボル３３に対する初期値
設定を行っているので、全て第１の状態のデータを除
き、受信データがシンボル単位でスリップしたとして
も、ダミーデータ部分がエラーとみなされてしまうの
で、スリップを検出できる確率が高くなる。

【００９８】また、実施例２と同様に、フラッシュメモ
リの消去時のみシンドローム初期データ設定手段１２あ
るいはシンドローム補正データ設定回路１４を、図８に
おけるダミーシンボル３３に関するシンドロームデータ
とし、普通は“０”を設定するようにすることも可能で
ある。

【００９９】また、この実施例では、１０ビットシンボ
ルのリードソロモン符号を使った第１の課題の解決策上
で、第２、第３の課題を示したが、例えば８ビットシン
ボルのリードソロモン符号の短縮符号などでも、この実
施例同様、第２の課題、第３の課題に対する解決策を実
現することができる。

【０１００】実施例４．次に、本発明の実施例４の誤り
訂正符号復号化方法について説明する。図９は、本実施
例を実現するための符号構成例であり、特に図８を改良
したものである。図９において、３５は情報データの手
前の短縮符号の符号固有データ挿入シンボル部分を示す
ものである。

【０１０１】ちなみに、本実施例は、実施例３で示し
た、第２の課題、第３の課題を解決する発明と類似して
いるが、第３の課題に対する解決策をより強化したもの
である。

【０１０２】次に、図９について説明する。符号固有デ
ータ挿入シンボル部分３５の部分に、図８と同様に、
“０”を除くその符号固有のパターンを設定している。
例えば、ｋ段のインターリーブで構成されるリードソロ
モン符号の構成では、各段に“１”から“ｋ”までの数
値を設定する。

【０１０３】なお、この方法における符号化方法および
復号方法は、実施例３で示した、図６、図７、図３、図
４の回路構成により実現される。

【０１０４】次に、図９の符号構成における同期判定の
方法について説明する。図５は、これを実現するための
構成例を示す回路ブロック図である。図５の構成におい
て、シンドローム出力端子９までの系統は、図３の構成
と同様である。一方、１５は誤り位置、誤り数値を求め
る誤り位置／大きさ検出回路１５、１６は同期が正しい
か否かを調べるための同期判定回路、１７は誤りの位置
と大きさを出力する誤り位置／大きさ出力端子、同期判
定回路１６から出力される同期チェックフラグを導出す
るための同期チェックフラグ出力端子である。

【０１０５】以上述べたような構成において、次にその
動作を説明する。

【０１０６】初期値データでは、それぞれ受信した符号
の、期待される固有のデータが設定されるものとする。
これにより得られたシンドローム出力端子９からのシン
ドロームから、誤り位置／大きさ検出回路１５におい
て、誤り位置多項式および誤り数値多項式を求め、チェ
ンサーチにより誤り位置および誤りの大きさを求める。
ここで、一般には、受信したリードソロモン符号の符号
長部分のチェンサーチの検査を行うが、この実施例で
は、符号固有データ挿入シンボル部分３５を挿入した短
縮部分を含む短縮符号部分３０もチェックする。この
時、正しく訂正できた場合、短縮符号長−１の“０”シ
ンボルランが続き、続いて符号固有データ挿入シンボル
部分３５が現れる。この先頭の挿入データの状態を同期
判定回路１６で監視し、同期がとれていたら、フラグを
同期チェックフラグ出力端子１８より出力する。一方、
誤り位置／大きさ出力端子１７からは、同期のずれ情報
を含め、誤り位置および大きさを出力する。

【０１０７】このように、短縮部分の“０”ランおよび
短縮部分に埋め込んだ先頭の固有データにより、符号長
を増やすことなく、シンボル単位のスリップに対して、
検出及びリカバリができる。

【０１０８】なお、本実施例の方法の実現に当たって
は、実施例３で示した符号化回路および復号化回路がほ
とんどそのまま使用できるので、例えばフラッシュメモ
リの消去には実施例３の方法を採用し、通常のケースで
は、この実施例４の方法を採るようにすることも可能で
ある。

【０１０９】実施例５．次に、本発明の実施例５の誤り
訂正符号復号化方法について説明する。この実施例は、
これまで示してきた実施例において、特に第１課題の解
決策について、不完全であった部分に対する解決策を示
す。

【０１１０】これまで説明してきた実施例、例えば図
８、図９のような符号構成の復号においては、情報シン
ボル位置での上位２ビットのダミー部分に誤りがあると
判定された場合、訂正不可能な誤りが存在する。

【０１１１】これに対して、図８、図９において、後に
付加した付加チェックシンボル３４は、１シンボルの全
てを誤ると、例えばリードソロモン符号として４シンボ
ルの誤りに拡散する可能性があるが、全体として付加す
るシンボル数は少ないので、確率的には小さい。また、
誤った場合で訂正不可能が検出された場合には、その付
加したシンボルを消失として消失訂正を行い、その消失
位置の誤りの大きさがチェックシンボルの上位２ビット
のみに現れたのであれば情報シンボルには誤りがないと
判断してもよい。すなわち、誤りの大きさから誤り検出
することが可能である。

【０１１２】また、後に付加した上位２ビットをまとめ
たシンボルについては、複数回送信送信あるいは複数シ
ンボル記録とし、復号側で多数決復号する方法もある。

【０１１３】また、後に付加した上位２ビットをまとめ
たシンボルを情報として、伝送形態にあった、例えば８
ビットシンボルのリードソロモン符号、あるいは４ビッ
トシンボルのリードソロモン符号などの第２の誤り訂正
符号で符号化して、そのチェックを付加して送信あるい
は記録し、復号側では後ろに付加した上位２ビットをま
とめたシンボルに対して、第２の誤り訂正符号で復号し
てから情報シンボルに対する復号を行う方法もある。

【０１１４】実施例６．次に、この発明の実施例６につ
いて説明する。図１２はこの発明の実施例６の誤り訂正
符号復号化方法を実現するための回路の回路ブロック図
であり、特に第４の課題を解決するための構成を例示す
るものである。図において、６１は受信データを入力す
るためのデータ入力端子１から入力される符号系列のた
めのシンドローム回路、６２はバッファメモリ５９から
のデータに対応するシンドローム回路６０のデータと、
データ入力端子１からのデータに対応するシンドローム
回路６１のデータを選択して、誤り位置／大きさ検出回
路６３に入力するためのセレクタである。その他の構成
については、図１８の構成と同様である。

【０１１５】以上述べたような構成において、次にその
動作を説明する。

【０１１６】データ入力端子１から入力される符号系列
は、バッファメモリ５９に記憶されると同時に、シンド
ローム回路６１に入力される。また、シンドローム回路
６０は、受信直後の符号系列を除く符号系列についてシ
ンドローム計算を行う。

【０１１７】セレクタ６２は、シンドローム回路６０、
６１のそれぞれのデータを時分割で選択して誤り位置／
大きさ検出回路６３に入力する。誤り位置／大きさ検出
回路６３では、入力されたシンドロームに応じて、誤り
位置と誤りの大きさを求め、訂正回路６４に渡す。訂正
回路６４は、バッファメモリ５９に記憶されているデー
タから誤り位置に該当するデータを取り込み、誤りを訂
正して再びバッファメモリ５９に返す。

【０１１８】これにより、バッファメモリ５９とシンド
ローム回路６０とのデータアクセスは、入力符号長分少
なくなり、バッファメモリ５９のアクセス速度は遅くて
もよくなり、例えば従来高価なＳＲＡＭで構成していた
バッファメモリ５９が、安価なＤＲＡＭで済むようにな
る。

【０１１９】実施例７．次に、この発明の実施例７につ
いて説明する。図１３はこの発明の実施例７の誤り訂正
符号復号化方法を実現するための回路の回路ブロック図
であり、特に第５の課題を解決するための構成を例示す
るものである。図において、５１はシンドローム回路６
０から出力される８ビットのシンドローム信号、５０は
シンドローム信号５１から偶数および重み“５”を検出
するための偶数および重み“５”検出回路、５２は偶数
および重み“５”検出回路５０で偶数および重み“５”
を検出した時に信号“１”を出力する偶数および重み
“５”検出信号線であり、その他の構成については、７
２ビット入力ＮＯＲ回路６７を除けば図１９の構成と同
様である。

【０１２０】さて、１ビット誤り訂正２ビットで検出を
行う符号の構成法として、パリティ検査行列をそれぞれ
異なる奇数重みのビット系列で構成する方法がある。こ
れは、先に挙げた文献などにも示されている。（７２、
６４）バイナリ線形符号では、パリティ検査行列は、８
ビットとなるが、それぞれ奇数重みの状態の組み合わせ
は、以下のようになる。

【０１２１】重み１＝８重み３＝５６重み５＝５６重み７＝８そして、従来は、重み“１”、“３”、“５”の状態を
選択し、（７２、６４）符号を構成していたが、この実
施例では、重み“１”、“３”、“７”をとって符号を
構成する。この場合、例えば、パリティ検査行列を、

【数２２】としたものでも、１ビット誤り訂正２ビットの誤り検出
が可能になる。これにより、シンドローム計算では、従
来の最小構成よりも遅延段数は変わらず、１６個の排他
的論理和回路が増えるが、訂正不可の検出がシンドロー
ムデータから直接得られるため、高速でしかも簡単で全
体としては少ない回路量の構成で、誤り検出ができる。

【０１２２】さて、以上のような観点から、図１３の動
作を説明する。

【０１２３】この実施例の符号構成では、パリティ検査
行列に、奇数重みである“１”、“３”、“７”の全パ
ターンを用いているので、該当しないシンドロームパタ
ーン、すなわち“０”を除く偶数重みパターンおよび重
み“５”のパターンを検出すればよい。なお、シンドロ
ームの“０”検出は、８入力ＯＲ回路６６で検出し、２
入力ＡＮＤ回路６８で訂正不可フラグが“１”にならな
いようにしているので、偶数および重み“５”検出回路
５０は偶数および重み“５”を検出すればよいことにな
る。

【０１２４】図１４は、偶数および重み“５”検出回路
５０の詳細な構成を示す回路ブロック図である。図にお
いて、５３は２入力ＸＯＲ回路、５４は２入力ＡＮＤ回
路、５５は２入力ＯＲ回路、５６は２入力ＸＮＯＲ回路
５６である。

【０１２５】図からも明らかなように、従来は７１個の
２入力ＯＲ回路あるいはＮＯＲ回路が必要であったが、
この実施例の構成では極めて小さな回路規模で同様の機
能を実現することができる。

【０１２６】なお、ここでは（７２、６４）バイナリ線
形符号について説明したが、他のパリティ長の符号につ
いても同様に適用されることは言うまでもない。

【０１２７】

【発明の効果】この発明の誤り訂正符号復号化方法は以
上のように構成したので、以下に説明するようなさまざ
まな効果を得ることができる。

【０１２８】効果１．この発明は、第１の課題に対し
て、情報シンボルよりも大きなビット長をシンボルとす
るリードソロモン符号符号において、情報ビットの上位
部分をダミーとし、チェックシンボルの上位２ビットに
ついては後から付加するように構成したので、シンボル
変換することなく、またシンボルクロックのみで符号復
号化ができるので、高速で処理できるという効果があ
る。

【０１２９】効果２．この発明は、第２の課題に対し
て、符号系列の反転あるいは短縮部分へのダミーデータ
の設定により、フラッシュメモリの消去チェックを、誤
り訂正回路を用いて実施できるので、検査のための特別
な回路が不要になり、回路構成を簡略化できるという効
果がある。

【０１３０】効果３．この発明は、第３の課題に対し
て、短縮部分への符号固有データの重畳により、同期デ
ータを挿入したので、情報長あるいはデータ長を増やす
ことなく、同期チェックあるいはリカバリが可能になる
という効果がある。

【０１３１】効果４．この発明は、第４の課題に対し
て、入力データに対応したシンドローム回路を設け、セ
レクタにより従来のシンドローム回路と選択的して復号
できるので、従来に比べてバッファメモリのアクセス速
度が遅くてもよく、安価なメモリを適用できるという効
果がある。

【０１３２】効果５．この発明は、第５の課題に対し
て、８ビットのシンドローム長において、重み“１”、
“３”、“７”の全てのパターンについて１ビット誤り
訂正に対応させたので、シンドロームから直接“０”を
除く偶数および重み“５”を検出するだけで訂正不可の
検出が可能となり、従来より高速で小型の回路で誤りの
検出が可能になるという効果がある。

【図面の簡単な説明】

【図１】この発明の実施例１の誤り訂正符号復号化方
法を実現するための回路ブロック図である。

【図２】この発明の実施例２の誤り訂正符号復号化方
法を実現するための回路ブロック図である。

【図３】この発明の実施例３の誤り訂正符号復号化方
法における復号回路の第１の例の回路ブロック図であ
る。

【図４】この発明の実施例３の誤り訂正符号復号化方
法における復号回路の第２の例の回路ブロック図であ
る。

【図５】この発明の実施例４の誤り訂正符号復号化方
法における、同期判定を行う回路ブロック図である。

【図６】この発明の実施例３の誤り訂正符号復号化方
法において、図８に示した符号構成に対応する符号化回
路の回路ブロック図である。

【図７】この発明の実施例３の誤り訂正符号復号化方
法における、符号化回路の他の例を示すブロック図であ
る。

【図８】この発明の実施例３を実行するに当たっての
（５２０、５１２）リードソロモン符号の構成法の説明
図である。

【図９】この発明の実施例４を実行するに当たっての
符号の構成法の説明図である。

【図１０】図１の構成におけるシンドロームデータ補
正回路の第１の例を示す回路ブロック図である。

【図１１】図１の構成におけるシンドロームデータ補
正回路の第２の例を示す回路ブロック図である。

【図１２】この発明の実施例６の誤り訂正符号復号化
方法を実現するための回路ブロック図である。

【図１３】この発明の実施例７の誤り訂正符号復号化
方法を実現するための回路ブロック図である。

【図１４】図１３の偶数および重み“５”検出回路の
回路例を示す回路ブロック図である。

【図１５】従来の誤り訂正符号復号化方法における符
号の構成例の説明図である。

【図１６】図１５のリードソロモン符号のチェックバ
イトを生成する符号化回路の回路ブロック図である。

【図１７】従来の誤り訂正符号復号化方法における復
号化回路の回路ブロック図である。

【図１８】従来の誤り訂正符号復号化方法において、
積符号構成の復号を行う回路の回路ブロック図である。

【図１９】従来の誤り訂正符号復号化方法において、
（７２、６４）バイナリ線形符号の復号回路の回路ブロ
ック図である。

【符号の説明】

１データ入力端子、２ダミーデータ入力回路、３
シンドロームデータ補正回路、４セレクタ、５ガロ
ア体加算回路、６セレクタ、７レジスタ、８ガロ
ア体係数乗算回路、９シンドローム出力端子、１０
０／１反転回路、１１セレクタ、１２シンドローム
初期データ設定手段、１３ガロア体加算回路、１４
シンドローム補正データ設定回路、１５誤り位置／大
きさ検出回路、１６同期判定回路、１７誤り位置／
大きさ出力端子、１８同期チェックフラグ出力端子、
１９８ビット／１０ビット変換回路、２０ＦＦチェ
ック回路、２１消去検査フラグ出力端子、２２情報
データ入力端子、２３符号化回路、２４符号化回路
初期値データ設定回路、２５セレクタ、２６チェッ
クシンボル出力端子、２７ガロア体加算回路、２８
チェックシンボル補正データ設定回路、２９１０ビッ
ト／８ビット変換回路、３０短縮符号部分、３１実
情報データシンボル部分、３２チェックシンボル部
分、３３ダミーシンボル、３４付加チェックシンボ
ル、３５符号固有データ挿入シンボル部分、３６ダ
ミーシンボル部分、３７受信データ入力端子、３８、
３９、４０ガロア体係数乗算回路、４１、４２、４
３、４４ガロア体加算回路、４５レジスタ、４６ガ
ロア体係数乗算回路、４７補正データ出力端子、４８
セレクタ、４９訂正不可検出フラグ出力端子、５０
偶数および重み“５”検出回路、５１シンドローム信
号、５２偶数および重み“５”検出信号線、５３２
入力ＸＯＲ回路、５４２入力ＡＮＤ回路、５５２入
力ＯＲ回路、５６２入力ＸＮＯＲ回路、５９バッファ
メモリ、６０、６１シンドローム回路、６２セレク
タ、６３誤り位置／大きさ検出回路、６４訂正回
路、６５復号データ出力端子、６６８入力ＯＲ回路、
６７７２ビット入力ＮＯＲ回路、６８２入力ＡＮＤ
回路。

Claims

(57)【特許請求の範囲】

【請求項１】単位情報データを表わす情報ビットと、
所定の第１ダミーデータを表わす第１剰余ビットと、か
ら構成された情報シンボルが複数集まった情報シンボル
群と、前記情報シンボルをもとに生成され、前記情報ビットの
ビット長に相当する部分である第１チェックビットと、
前記第１剰余ビットのビット長に相当する部分である第
２チェックビットと、から構成されたチェックシンボル
が複数集まったチェックシンボル群と、からなるリードソロモン符号の符号化及び復号化方法で
あって、前記リードソロモン符号を送出する際に、情報シンボルに対しては、情報ビットのみを送出し、第
１剰余ビットは送出しないプロセスと、チェックシンボ
ルに対しては、第１チェックビットはそのまま送出し、
第２チェックビットは前記情報ビットのビット長ごとの
データにまとめて送出するプロセスと、前記送出されたリードソロモン符号を復号する際に、情報シンボルに対しては、送出された第１情報ビットに
所定の第１剰余ビットを付加したデータをもとにシンド
ローム計算を行い、且つ送出されたチェックシンボルの
第１チェックビットに対しては第２ダミーデータを表わ
す第２剰余ビットを付加したデータをもとにシンドロー
ム計算を行って第１シンドロームデータを得るプロセス
と、送出されたチェックシンボルの第２チェックビット
に対しては、前記情報ビットのビット長ごとにまとめた
データをもとにシンドローム計算を行い第２シンドロー
ムデータを得るプロセスと、前記第１シンドロームデー
タと前記第２シンドロームデータとをガロア体加算する
プロセスと、を備えることを特徴とする誤り訂正符号復号化方法。
【請求項２】請求項１に記載の誤り訂正符号復号化方
法に用いられる符号化回路であって、前記情報ビットに前記所定の第１剰余ビットを付加する
付加手段と、前記第１チェックビットと、前記第２チェックビットを
前記情報ビットのビット長ごとにまとめたデータと、を
選択して出力する出力手段と、を備えることを特徴とする符号化回路。
【請求項３】請求項１に記載の誤り訂正符号復号化方
法に用いられる復号化回路であって、前記情報ビットに前記第１剰余ビットを付加し、且つ前
記第１チェックビットに前記第２剰余ビットを付加する
付加手段と、前記チェックシンボルの第２チェックビットに対してシ
ンドローム計算を行って第２シンドロームデータを得る
補正手段と、前記情報ビットに前記第１剰余ビットが付加されたデー
タ、及び前記第１チェックビットに前記第２剰余ビット
が付加されたデータに対してシンドローム計算を行って
得られた第１シンドロームデータと前記第２シンドロー
ムデータとをガロア体加算する加算手段と、を備える請求項１の誤り訂正復号化方法を用いる復号化
回路。
【請求項４】請求項１に記載の誤り訂正符号復号化方
法であって、前記送出されたリードソロモン符号を復号する際に、前記第２チェックビットを消失位置として消失訂正を行
うプロセスと、前記消失訂正で得られた誤りパターンが前記第２剰余ビ
ットにのみ現れた場合、情報シンボル部分には誤りがな
いと判定するプロセスと、を備える請求項１の誤り訂正復号化方法。
【請求項５】請求項１、請求項２、請求項３又は請求
項４の誤り訂正符号復号化方法であって、前記リードソロモン符号を送出する際に、第２チェックビットを前記情報ビットのビット長ごとに
まとめたデータを多重化して送出するプロセスと、前記送出されたリードソロモン符号を復号化する際に、前記送出された第２チェックビットに対しては、多重化
して送出された前記データについて多数決判定して復号
するプロセスを備える事を特徴とする誤り訂正符号復号
化方法。
【請求項６】請求項１、請求項２、請求項３又は請求
項４の誤り訂正符号復号化方法であって、前記リードソロモン符号を送出する際に、第２チェックビットに対しては、前記情報ビットのビッ
ト長の整数倍に合致する検査ビットを有する他の誤り訂
正符号で符号化を行って送出するプロセスを備え、前記リードソロモン符号を復号化する際に、第２チェックビットについては他の誤り訂正符号で復号
した上で、情報シンボルを復号するプロセスを備える事
を特徴とする誤り訂正符号復号化回路。
【請求項７】誤り訂正符号の符号化および復号化を行
うに当たって、情報およびチェックバイトを全て０／１
反転して送出し、復号では読み出されたデータを０／１
反転してから復号する、プロセスを備えることを特徴と
する誤り訂正符号復号化方法。
【請求項８】復号側で送出されてきたデータについ
て、通常はそのまま入力してシンドローム計算し、特別
な場合においては、データの全てを０／１反転してから
シンドローム計算するプロセス、を備える請求項７の誤
り訂正符号復号化方法。
【請求項９】符号長を短縮した誤り訂正符号の符号化
および復号化において、情報およびチェックシンボルが
全て“１”になるデータが符号となるように、短縮部分
にデータパターンを付加してチェックシンボルを生成
し、情報およびチェックシンボルのみを送出するプロセ
スと、復号側において、短縮部分のデータに相当するシ
ンドロームデータを情報およびチェックシンボルより生
成されるシンドロームに付加するプロセスと、を備える
ことを特徴とする誤り訂正符号復号化方法。
【請求項１０】符号化に当たり、情報が入力する前に
予め得られているダミーパターンに基づくチェックシン
ボルを符号化手段に初期値データとして設定する初期値
データ設定手段、を備える請求項９の誤り訂正符号化方
法に用いる符号化回路
【請求項１１】符号化に当たり、情報を入力して得ら
れたチェックシンボルと、予め得られているダミーパタ
ーンに基づくチェックシンボルをガロア体加算したもの
を符号化チェックシンボルとするガロア体加算回路及び
補正データ入力手段、を備える請求項９の誤り訂正符号
化方法に用いる符号化回路。
【請求項１２】復号化に当たり、送出されてきた符号
データが入力する前に、予め得られているダミーパター
ンに基づくシンドロームデータを、シンドローム回路に
初期値として設定する初期値データ設定手段、を備える
請求項９の誤り訂正復号化方法に用いる復号化回路。
【請求項１３】復号化に当たり、送出されてきた符号
データのシンドロームデータと、予め得られているダミ
ーパターンに基づくシンドロームデータをガロア体加算
したものを符号シンドロームデータとするガロア体加算
回路及び補正データ入力手段、を備える請求項９の誤り
訂正復号化方法に用いる復号化回路。
【請求項１４】復号化に当たり、通常は、読み出され
た符号データに基づくシンドロームを使って誤り訂正を
行うプロセスと、特別な場合においては、ダミーパター
ンに基づくシンドロームデータをシンドローム計算前に
設定およびシンドローム計算後の少なくとも一方でガロ
ア体加算するプロセスと、を備える請求項９の誤り訂正
復号化方法。
【請求項１５】符号長を短縮した誤り訂正符号の符号
化および復号化において、情報の１シンボル前の短縮部
分に、その符号固有のデータパターンを付加してチェッ
クシンボルを生成し、情報およびチェックシンボルのみ
送出するプロセスと、復号側で、短縮部分に付加した符
号固有データパターンに相当するシンドロームを情報お
よびチェックシンボルより生成されるシンドロームに付
加するプロセスと、を備えることを特徴とする誤り訂正
符号復号化方法。
【請求項１６】符号化に当たり、情報が入力する前に
予め得られている符号固有のデータに基づくチェックシ
ンボルを符号化手段に初期値データとして設定する初期
値データ設定手段、を備える請求項１５の誤り訂正符号
化方法に用いる符号化回路。
【請求項１７】符号化に当たり、情報を入力して得ら
れたチェックシンボルと、予め得られている符号固有の
データに基づくチェックシンボルをガロア体加算したも
のを符号化チェックシンボルとするガロア体加算回路及
び補正データ入力手段、を備える請求項１５の誤り訂正
符号化方法に用いる符号化回路。
【請求項１８】復号化に当たり、送出されてきた符号
データが入力する前に、予め期待される符号固有のデー
タに基づくシンドロームデータをシンドローム手段に初
期値として設定する初期値データ設定手段、を備える請
求項１５の誤り訂正復号化方法に用いる復号化回路。
【請求項１９】復号化に当たり、送出されてきた符号
データのシンドロームデータと、予め期待される符号固
有のデータに基づくシンドロームデータをガロア体加算
したものを符号のシンドロームデータとするガロア体加
算回路及び補正データ入力手段、を備える請求項１５の
誤り訂正復号化方法に用いる復号化回路。
【請求項２０】復号化に当たり、通常においては、短
縮部分に付加した符号固有データパターンに相当するシ
ンドロームと、情報およびチェックシンボルより生成さ
れるシンドロームに付加したシンドロームから復号する
時に、短縮部分を含めて訂正する訂正手段と、短縮部分
の付加データの復号結果により同期ずれを判定する判定
手段と、を備える請求項１５、請求項１８又は請求項１
９の誤り訂正復号化方法又は回路に用いる復号化回路。
【請求項２１】符号化、復号化に当たり、通常におい
ては、情報の１シンボル前の短縮部分にその符号固有の
データパターンを付加してチェックシンボルを生成し、
情報およびチェックシンボルのみ送出するプロセスと、
復号において、短縮部分に付加した符号固有データパタ
ーンに相当するシンドロームを情報およびチェックシン
ボルより生成されるシンドロームに付加するプロセス
と、特別な場合には、符号データが全て“１”となるよ
うに付加したダミーパターンに基づくシンドロームデー
タを情報およびチェックシンボルより生成されるシンド
ロームに付加するプロセスと、を備える請求項９又は請
求項１５の誤り訂正符号化復号化方法。
【請求項２２】受信した誤り訂正符号化されたデータ
を入力部よりバッファメモリに蓄え前記誤り訂正符号に
より複数回復号操作を行う復号回路において、誤り訂正
符号化されたデータをバッファメモリに蓄えて複数回の
復号操作を行うシンドローム計算手段と、入力データに
対するシンドローム計算を行うと共にバッファメモリの
データに対するシンドローム計算を行うプロセスと、２
つのシンドロームを選択すると共に誤りを訂正して復号
を行うプロセスと、を備えることを特徴とする誤り訂正
復号化回路。
【請求項２３】誤り訂正符号化および復号化におい
て、１ビット誤り訂正、２ビット誤り検出を行う（７
６、６４）バイナリ線形符号において、パリティ検査行
列の重みを、“１”、“３”、“７”のみで処理するプ
ロセス、を備えることを特徴とする誤り訂正符号復号化
方法。
【請求項２４】（７６、６４）バイナリ線形符号の復
号において、シンドローム計算を行うシンドローム計算
手段と、誤り訂正を行う誤り訂正手段と、８ビットのシ
ンドロームのビット重みが全“０”を除く偶数および
“５”の時に、訂正不可を判定する訂正不可検出手段
と、を備える請求項２３の誤り訂正復号化方法に用いる
復号化回路。
【請求項２５】（７６、６４）バイナリ線形符号の復
号において、パリティ検査行列を、【数１】として処理するプロセス、を備える請求項２３又は請求
項２４の誤り訂正符号復号化方法。