JPH0637646A - 誤り訂正方式及びこの誤り訂正方式を用いた復号器 - Google Patents
誤り訂正方式及びこの誤り訂正方式を用いた復号器Info
- Publication number
- JPH0637646A JPH0637646A JP4225020A JP22502092A JPH0637646A JP H0637646 A JPH0637646 A JP H0637646A JP 4225020 A JP4225020 A JP 4225020A JP 22502092 A JP22502092 A JP 22502092A JP H0637646 A JPH0637646 A JP H0637646A
- Authority
- JP
- Japan
- Prior art keywords
- reed
- bch
- decoding
- code
- solomon
- 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.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
Landscapes
- Physics & Mathematics (AREA)
- Algebra (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
(57)【要約】
【目的】 リードソロモン符号の伝送系にＢＣＨ復号を
行う機能を、またＢＣＨ符号の伝送系にリードソロモン
復号を行う機能を設けて、互いの復号の欠点を補って誤
り訂正の効率を向上する。 【構成】 演算がＧＦ（２m ）上で定義されるＢＣＨ符
号またはリードソロモン符号を用いてエラー訂正する系
において、送信側，受信側でそれぞれｍ×Ｌ（Ｌ≧１）
×Ｎの単位でインターリーブを施すバッファメモリを設
けて、送信側がＢＣＨ符号の時はリードソロモン符号で
リードソロモン符号の時はＢＣＨ符号でエラーを訂正で
きるような構成にした。
行う機能を、またＢＣＨ符号の伝送系にリードソロモン
復号を行う機能を設けて、互いの復号の欠点を補って誤
り訂正の効率を向上する。 【構成】 演算がＧＦ（２m ）上で定義されるＢＣＨ符
号またはリードソロモン符号を用いてエラー訂正する系
において、送信側，受信側でそれぞれｍ×Ｌ（Ｌ≧１）
×Ｎの単位でインターリーブを施すバッファメモリを設
けて、送信側がＢＣＨ符号の時はリードソロモン符号で
リードソロモン符号の時はＢＣＨ符号でエラーを訂正で
きるような構成にした。
Description
【０００１】
【産業上の利用分野】本発明は、誤り訂正方式及びこの
方式を用いた復号器に関する。
方式を用いた復号器に関する。
【０００２】
【従来の技術】図１は従来の復号器のハードウェアブロ
ック構成図である。図中、１はメモリ、２はアドレス／
データ／制御信号バス、３はリードソロモン符号に対す
るリードソロモン復号器、４は制御回路である。ガロア
体ＧＦ（２8 ）上の（Ｎ，Ｋ，Ｄ）リードソロモン符号
の例で説明する。但しＮは符号長、Ｋは情報シンボル
長、Ｄ（Ｄ＝Ｎ−Ｋ＋１）は符号の最小距離である。ま
た、１シンボルは８ビットからなる。
ック構成図である。図中、１はメモリ、２はアドレス／
データ／制御信号バス、３はリードソロモン符号に対す
るリードソロモン復号器、４は制御回路である。ガロア
体ＧＦ（２8 ）上の（Ｎ，Ｋ，Ｄ）リードソロモン符号
の例で説明する。但しＮは符号長、Ｋは情報シンボル
長、Ｄ（Ｄ＝Ｎ−Ｋ＋１）は符号の最小距離である。ま
た、１シンボルは８ビットからなる。
【０００３】リードソロモン符号の生成多項式は Ｇ（ｘ）＝（Ｘ−αi ）（Ｘ−αi+1 ）・・・（Ｘ−α
i+D-1 ） で与えられる。但しαはガロア体ＧＦ（２8 ）上の原始
元、ｉは任意の整数で通常０か１が選ばれる。この符号
語の受信語データＤ0 ，Ｄ1 ，…，ＤN-1 がメモリ１の
アドレス＃Ａ0 ，＃Ａ1 ，…，＃ＡN-1 に格納される。
データＤ0 ，Ｄ1，…，ＤN-1 は制御回路４の指令に基
づき、アドレス／データ／制御信号バス２を通ってリー
ドソロモン復号器３によってｔ≦［（Ｄ−１）／２］個
までの伝送路上で生起した誤りが訂正される。ここで
［ｘ］はガウス記号で、ｘを越えない最大の整数を表
す。なお、制御信号，タイミング等の細かい説明は省略
する。
i+D-1 ） で与えられる。但しαはガロア体ＧＦ（２8 ）上の原始
元、ｉは任意の整数で通常０か１が選ばれる。この符号
語の受信語データＤ0 ，Ｄ1 ，…，ＤN-1 がメモリ１の
アドレス＃Ａ0 ，＃Ａ1 ，…，＃ＡN-1 に格納される。
データＤ0 ，Ｄ1，…，ＤN-1 は制御回路４の指令に基
づき、アドレス／データ／制御信号バス２を通ってリー
ドソロモン復号器３によってｔ≦［（Ｄ−１）／２］個
までの伝送路上で生起した誤りが訂正される。ここで
［ｘ］はガウス記号で、ｘを越えない最大の整数を表
す。なお、制御信号，タイミング等の細かい説明は省略
する。
【０００４】最近、電子情報通信学会研究会において、
鴻巣敏之，金子敏充，西島利尚，平澤茂一等による「２
値展開されたReed-Solomon符号に関する一考察」（ＩＴ
91−42，以下従来文献という）に、リードソロモン符号
を２値のＢＣＨ符号に展開しリードソロモン符号のバー
スト誤り訂正能力を増大する技術が発表されている。以
下、その概要を述べる。 Ｎ：リードソロモン符号の符号長（Ｎ≦２m −１） Ｋ：リードソロモン符号の情報記号数 Ｄ：リードソロモン符号のＧＦ（２m ）上の最小距離
（Ｄ＝Ｎ−Ｋ＋１） α：ＧＦ（２m ）上の原始元 ｍS （ｘ）：αm のＧＦ（２）上での既約多項式 Ｇ（ｘ）：リードソロモン符号の生成多項式 とする。この時 Ｚn ＝｛０，１，…，Ｎ−１｝ Ｒt ＝｛ｉ｜ｍ0 ≦ｉ≦ｍ0 ＋Ｎ−Ｋ−１；ｉ∈Ｚn ｝ ＣS ＝｛ｉ｜ｉ＝２p Ｓ∈Ｒt,０≦ｐ≦ｍ−１｝ なる集合を定義する。ＣS はαS に対するＧＦ（２）上
のサイクルセットである。ＣS * は以下の式とする。
鴻巣敏之，金子敏充，西島利尚，平澤茂一等による「２
値展開されたReed-Solomon符号に関する一考察」（ＩＴ
91−42，以下従来文献という）に、リードソロモン符号
を２値のＢＣＨ符号に展開しリードソロモン符号のバー
スト誤り訂正能力を増大する技術が発表されている。以
下、その概要を述べる。 Ｎ：リードソロモン符号の符号長（Ｎ≦２m −１） Ｋ：リードソロモン符号の情報記号数 Ｄ：リードソロモン符号のＧＦ（２m ）上の最小距離
（Ｄ＝Ｎ−Ｋ＋１） α：ＧＦ（２m ）上の原始元 ｍS （ｘ）：αm のＧＦ（２）上での既約多項式 Ｇ（ｘ）：リードソロモン符号の生成多項式 とする。この時 Ｚn ＝｛０，１，…，Ｎ−１｝ Ｒt ＝｛ｉ｜ｍ0 ≦ｉ≦ｍ0 ＋Ｎ−Ｋ−１；ｉ∈Ｚn ｝ ＣS ＝｛ｉ｜ｉ＝２p Ｓ∈Ｒt,０≦ｐ≦ｍ−１｝ なる集合を定義する。ＣS はαS に対するＧＦ（２）上
のサイクルセットである。ＣS * は以下の式とする。
【０００５】
【数１】
【０００６】ＧＦ（２m ）上の（Ｎ，Ｋ，Ｎ−Ｋ＋１）
リードソロモン符号の生成多項式ｍS （ｘ）を用いて、
Ｇ（ｘ）は以下の式と書くことができるとする。
リードソロモン符号の生成多項式ｍS （ｘ）を用いて、
Ｇ（ｘ）は以下の式と書くことができるとする。
【０００７】
【数２】
【０００８】この時、ロードソロモン符号の符号語Ｃ
（ｘ）を以下とする。
（ｘ）を以下とする。
【０００９】
【数３】
【００１０】この時、上記式（Ａ）における下記（Ｂ）
を長さＮの２元符号とみなすと、下記（Ｃ）式によって
生成されるＢＣＨ符号になっている。
を長さＮの２元符号とみなすと、下記（Ｃ）式によって
生成されるＢＣＨ符号になっている。
【００１１】
【数４】
【００１２】
【数５】
【００１３】従来文献にはＧＦ（２m ）上のｔ誤り訂正
のリードソロモン符号を用いてバースト長ｍ（ｔ−１）
＋１≦ｂ≦ｍｔなるソリッドバースト誤りに対する復号
法が開示されている。図２に、従来方式によるリードソ
ロモン符号を２元ＢＣＨ復号に分割してバースト誤り訂
正能力を増大する方式のフローチャートを示す。まず、
ステップＳ１においてＧＦ（２m ）上のリードソロモン
復号を実行し、誤りがｔ以下であるか否かを判定する。
誤りがｔ以下の場合は誤り訂正し、誤り位置と誤り数値
とを求め、ステップＳ２へ進む。誤りがｔ＋１以上と判
定したときはステップＳ３へ進む。ステップＳ２では既
存の復号法に従って実際に訂正する。ステップＳ３では
既約多項式ｍS （ｘ）を２値展開する。次にステップＳ
４でｍ個のＢＣＨ符号のシンドローム計算をし、ステッ
プＳ５で計算したシンドロームの値を予め作っておいた
シンドロームパターンと比較する。等しいシンドローム
が存在する場合には、ステップＳ６で対応する誤りパタ
ーンをＲＯＭ等により索表して訂正できる。等しいシン
ドロームが存在しない場合には、誤りを訂正せず、ステ
ップＳ７で誤り検出フラグを立てる。
のリードソロモン符号を用いてバースト長ｍ（ｔ−１）
＋１≦ｂ≦ｍｔなるソリッドバースト誤りに対する復号
法が開示されている。図２に、従来方式によるリードソ
ロモン符号を２元ＢＣＨ復号に分割してバースト誤り訂
正能力を増大する方式のフローチャートを示す。まず、
ステップＳ１においてＧＦ（２m ）上のリードソロモン
復号を実行し、誤りがｔ以下であるか否かを判定する。
誤りがｔ以下の場合は誤り訂正し、誤り位置と誤り数値
とを求め、ステップＳ２へ進む。誤りがｔ＋１以上と判
定したときはステップＳ３へ進む。ステップＳ２では既
存の復号法に従って実際に訂正する。ステップＳ３では
既約多項式ｍS （ｘ）を２値展開する。次にステップＳ
４でｍ個のＢＣＨ符号のシンドローム計算をし、ステッ
プＳ５で計算したシンドロームの値を予め作っておいた
シンドロームパターンと比較する。等しいシンドローム
が存在する場合には、ステップＳ６で対応する誤りパタ
ーンをＲＯＭ等により索表して訂正できる。等しいシン
ドロームが存在しない場合には、誤りを訂正せず、ステ
ップＳ７で誤り検出フラグを立てる。
【００１４】従来文献には、以上の動作が数値例で示さ
れている。ＧＦ（２4 ）上の生成多項式が下記式となる
（15, ２，14）リードソロモン符号を考える。
れている。ＧＦ（２4 ）上の生成多項式が下記式となる
（15, ２，14）リードソロモン符号を考える。
【００１５】
【数６】
【００１６】αをＧＦ（２4 ）上の原始元とする。送信
語を （０００００００００００００００） とする。この送信語をＧＦ（２4 ）上の既約多項式 ｍ1 （ｘ）＝Ｘ4 ＋Ｘ＋１ を用いて２値展開したものは長さ15の４個のＢＣＨ符号
値となりその生成多項式は ｇb （ｘ）＝ｍ1 （ｘ）ｍ3 （ｘ） ＝（Ｘ4 ＋Ｘ＋１）（Ｘ4 ＋Ｘ3 ＋Ｘ2 ＋Ｘ＋１） であり、（15，７，５）ＢＣＨ符号の部分符号である
（15，２，５）ＢＣＨ符号になっている。α，α2 ，α
4 ，α8 ，α3 ，α6 ，α12，α9 が根となっている。
ＧＦ（２4 ）上の受信語が （００００１α12α12α12α12α12α6 ００００） の時、長さｂ＝23（ｍ（ｔ−１）＋１＜ｂ≦ｍｔ）のソ
リッドバーストが加わっており、基底ごとに分割すると ｇb （ｘ）はα，α3 を独立な根として持つ。バースト
長ｂ’＝６，及び５の時シンドロームは次式となる。
語を （０００００００００００００００） とする。この送信語をＧＦ（２4 ）上の既約多項式 ｍ1 （ｘ）＝Ｘ4 ＋Ｘ＋１ を用いて２値展開したものは長さ15の４個のＢＣＨ符号
値となりその生成多項式は ｇb （ｘ）＝ｍ1 （ｘ）ｍ3 （ｘ） ＝（Ｘ4 ＋Ｘ＋１）（Ｘ4 ＋Ｘ3 ＋Ｘ2 ＋Ｘ＋１） であり、（15，７，５）ＢＣＨ符号の部分符号である
（15，２，５）ＢＣＨ符号になっている。α，α2 ，α
4 ，α8 ，α3 ，α6 ，α12，α9 が根となっている。
ＧＦ（２4 ）上の受信語が （００００１α12α12α12α12α12α6 ００００） の時、長さｂ＝23（ｍ（ｔ−１）＋１＜ｂ≦ｍｔ）のソ
リッドバーストが加わっており、基底ごとに分割すると ｇb （ｘ）はα，α3 を独立な根として持つ。バースト
長ｂ’＝６，及び５の時シンドロームは次式となる。
【００１７】（１）ｂ’＝６に対して Ｓ1.i ＝αi+9 Ｓ3.i ＝α3i （２）ｂ’＝５に対して Ｓ1.i ＝αi+6 Ｓ3.i ＝０ ここでｉは受信系列において末尾を０ビット目とし、そ
こから数えたバースト開始位置である。（Ｄ）式より β3 ＝α3 α13＝αi+9 α12＝α3i よりｂ’＝６，ｉ＝４ β2 ＝α2 α13＝αi+9 α12＝α3i よりｂ’＝６，ｉ＝４ β1 ＝α α11＝αi+6 ０＝０ よりｂ’＝５，ｉ＝５ β0 ＝１ α14＝αi+9 α＝α3i よりｂ’＝６，ｉ＝５ となり訂正できる。
こから数えたバースト開始位置である。（Ｄ）式より β3 ＝α3 α13＝αi+9 α12＝α3i よりｂ’＝６，ｉ＝４ β2 ＝α2 α13＝αi+9 α12＝α3i よりｂ’＝６，ｉ＝４ β1 ＝α α11＝αi+6 ０＝０ よりｂ’＝５，ｉ＝５ β0 ＝１ α14＝αi+9 α＝α3i よりｂ’＝６，ｉ＝５ となり訂正できる。
【００１８】また、従来のものに、榊原勝己，常磐欣一
郎，笠原正雄による「ビット最小距離を利用したReed-S
olomon符号の復号に関する考察」（電子情報通信学会，
技術研究報告，ＩＴ86−28）によれば、（ｎ，２，ｎ−
１）リードソロモン符号に対し（ｍｎ，２ｍ，（ｍ−
１）２m-1 ）２元線形符号としての復号法が示されてい
るが、記号シンボルが２ｍビットしかとれず、符号化効
率が２／ｍと低く実用性に乏しい。また、榊原勝己，常
磐欣一郎，笠原正雄，滑川敏彦による「復号距離プロフ
ィールに基づいたReed-Solomon符号の復号法について」
（昭和61年度電子通信学会総合全国大会，1407，pp. ６
−49）によれば、最小距離４のリードソロモン符号を２
値展開してＳＥＣ−ＤＥＤ符号とみなして復号する方法
が開示されている。しかし、この技術も最小距離４のリ
ードソロモン符号に限定されており、また、誤りパター
ンを分類して数多くの合同式を解かねばならない。
郎，笠原正雄による「ビット最小距離を利用したReed-S
olomon符号の復号に関する考察」（電子情報通信学会，
技術研究報告，ＩＴ86−28）によれば、（ｎ，２，ｎ−
１）リードソロモン符号に対し（ｍｎ，２ｍ，（ｍ−
１）２m-1 ）２元線形符号としての復号法が示されてい
るが、記号シンボルが２ｍビットしかとれず、符号化効
率が２／ｍと低く実用性に乏しい。また、榊原勝己，常
磐欣一郎，笠原正雄，滑川敏彦による「復号距離プロフ
ィールに基づいたReed-Solomon符号の復号法について」
（昭和61年度電子通信学会総合全国大会，1407，pp. ６
−49）によれば、最小距離４のリードソロモン符号を２
値展開してＳＥＣ−ＤＥＤ符号とみなして復号する方法
が開示されている。しかし、この技術も最小距離４のリ
ードソロモン符号に限定されており、また、誤りパター
ンを分類して数多くの合同式を解かねばならない。
【００１９】
【発明が解決しようとする課題】図３はＧＦ（２4 ）上
のリードソロモン符号に、８個のランダム誤りが生起し
ている場合を示している。５はエラービットを表す。シ
ンボル誤りとしては８シンボルの誤りが生起しており、
これを訂正するにはリードソロモン符号としては最小距
離Ｄ＝２ｔ＋１＝17必要である。冗長シンボルは16シン
ボル必要であり、符号長15を越えてしまうので構成でき
ないという問題があった。
のリードソロモン符号に、８個のランダム誤りが生起し
ている場合を示している。５はエラービットを表す。シ
ンボル誤りとしては８シンボルの誤りが生起しており、
これを訂正するにはリードソロモン符号としては最小距
離Ｄ＝２ｔ＋１＝17必要である。冗長シンボルは16シン
ボル必要であり、符号長15を越えてしまうので構成でき
ないという問題があった。
【００２０】本発明はこのようなランダム誤りがシンボ
ル誤りに拡散されて訂正できないという上記の問題点を
解決するためになされたもので、リードソロモン符号を
用いて伝送するシステムにおいて、１シンボルの中の１
ビットでも誤りが生起するとシンボル誤りとなるため、
ガロア体ＧＦ（２m ）のｍが比較的大きいとランダムな
ビット誤りによるシンボル誤りの増加がリードソロモン
符号の訂正能力を減殺するので、これを防ぐため、２元
ＢＣＨ符号としてランダム誤りを訂正することにより、
分散している誤りをより効率よく訂正する誤り訂正方式
及びこれを用いた復号器を提供することを目的とする。
ル誤りに拡散されて訂正できないという上記の問題点を
解決するためになされたもので、リードソロモン符号を
用いて伝送するシステムにおいて、１シンボルの中の１
ビットでも誤りが生起するとシンボル誤りとなるため、
ガロア体ＧＦ（２m ）のｍが比較的大きいとランダムな
ビット誤りによるシンボル誤りの増加がリードソロモン
符号の訂正能力を減殺するので、これを防ぐため、２元
ＢＣＨ符号としてランダム誤りを訂正することにより、
分散している誤りをより効率よく訂正する誤り訂正方式
及びこれを用いた復号器を提供することを目的とする。
【００２１】また、ＢＣＨ符号を用いて伝送するシステ
ムにおいて、インターリーブをかけることにより、ＢＣ
Ｈ符号の受信語を復号するときそのままでは訂正効果が
上がらない場合にリードソロモン符号として復号できる
ようにして、誤り訂正効率の向上を図る誤り訂正方式を
提供することを目的とする。
ムにおいて、インターリーブをかけることにより、ＢＣ
Ｈ符号の受信語を復号するときそのままでは訂正効果が
上がらない場合にリードソロモン符号として復号できる
ようにして、誤り訂正効率の向上を図る誤り訂正方式を
提供することを目的とする。
【００２２】
【課題を解決するための手段】本願の第１発明の誤り訂
正方式は、メモリ内にｍ×Ｎのデータ配列を有し、ｍ個
のＮビットのＢＣＨ符号の受信語の復号と１個のＮシン
ボルのリードソロモン符号の復号とを実行することを特
徴とする。
正方式は、メモリ内にｍ×Ｎのデータ配列を有し、ｍ個
のＮビットのＢＣＨ符号の受信語の復号と１個のＮシン
ボルのリードソロモン符号の復号とを実行することを特
徴とする。
【００２３】本願の第２発明の誤り訂正方式は、メモリ
よりｍビット単位にデータを読み出してそれをパラレル
に各１ビットづつ出力し、各々のＢＣＨ受信語を復号す
ることを特徴とする。
よりｍビット単位にデータを読み出してそれをパラレル
に各１ビットづつ出力し、各々のＢＣＨ受信語を復号す
ることを特徴とする。
【００２４】本願の第３発明のリードソロモン符号の復
号器は、ＢＣＨ符号の復号を行うためのＧＦ（２）の除
算結果をＧＦ（２m ）のパターンに変換する基底変換を
行う変換手段を備えたことを特徴とする。
号器は、ＢＣＨ符号の復号を行うためのＧＦ（２）の除
算結果をＧＦ（２m ）のパターンに変換する基底変換を
行う変換手段を備えたことを特徴とする。
【００２５】本願の第４発明の復号器は、パラレルに出
力されるｍビットを順次入力して蓄積するＦＩＦＯメモ
リを備えたことを特徴とする。
力されるｍビットを順次入力して蓄積するＦＩＦＯメモ
リを備えたことを特徴とする。
【００２６】本願の第５発明の復号器は、同じガロア体
で定義されたＧＦ（２m ）上の演算を行うリードソロモ
ン復号手段とＢＣＨ復号手段とを備えたことを特徴とす
る。
で定義されたＧＦ（２m ）上の演算を行うリードソロモ
ン復号手段とＢＣＨ復号手段とを備えたことを特徴とす
る。
【００２７】本願の第６発明の復号器は、同一のガロア
体ＧＦ上で動作するリードソロモン符号の復号手段とＢ
ＣＨ符号の復号手段とにおいて誤り位置を求める演算処
理を共通化したことを特徴とする。
体ＧＦ上で動作するリードソロモン符号の復号手段とＢ
ＣＨ符号の復号手段とにおいて誤り位置を求める演算処
理を共通化したことを特徴とする。
【００２８】本願の第７発明の復号器は、１シンボルｍ
ビットの（Ｎ，Ｋ，Ｄ）リードソロモン受信語をｍ回の
ＢＣＨ受信語としてＢＣＨ復号した後にリードソロモン
復号を実行するように構成したことを特徴とする。
ビットの（Ｎ，Ｋ，Ｄ）リードソロモン受信語をｍ回の
ＢＣＨ受信語としてＢＣＨ復号した後にリードソロモン
復号を実行するように構成したことを特徴とする。
【００２９】本願の第８発明の誤り訂正方式は、ＢＣＨ
符号の受信語をｍ個入力してｍ×Ｎのメモリ配置にして
ＧＦ（２m ）上のリードソロモン符号として復号するこ
とを特徴とする。
符号の受信語をｍ個入力してｍ×Ｎのメモリ配置にして
ＧＦ（２m ）上のリードソロモン符号として復号するこ
とを特徴とする。
【００３０】本願の第９発明の誤り訂正方式は、送信側
でＢＣＨ符号化された符号語をｍの整数倍インターリー
ブして送信し、受信側でｍ個単位でまとめてリードソロ
モン符号として復号することを特徴とする。
でＢＣＨ符号化された符号語をｍの整数倍インターリー
ブして送信し、受信側でｍ個単位でまとめてリードソロ
モン符号として復号することを特徴とする。
【００３１】本願の第10発明の誤り訂正方式は、ＢＣＨ
符号化された符号語をｍの整数倍インターリーブしてリ
ードソロモン復号した後、更にＢＣＨ復号を実行して誤
りを訂正することを特徴とする。。
符号化された符号語をｍの整数倍インターリーブしてリ
ードソロモン復号した後、更にＢＣＨ復号を実行して誤
りを訂正することを特徴とする。。
【００３２】本願の第11発明の誤り訂正方式は、ＢＣＨ
符号化された符号語をｍの整数倍インターリーブしてＢ
ＣＨ復号した後、更にリードソロモン復号を実行して誤
りを訂正することを特徴とする。。
符号化された符号語をｍの整数倍インターリーブしてＢ
ＣＨ復号した後、更にリードソロモン復号を実行して誤
りを訂正することを特徴とする。。
【００３３】
【作用】第１発明では、２元ＢＣＨ符号としてランダム
誤りを訂正するので、ランダム誤りによるシンボル誤り
が増加せず、リードソロモン符号の訂正能力が劣化する
ことはなく、誤り訂正の効率が良い。
誤りを訂正するので、ランダム誤りによるシンボル誤り
が増加せず、リードソロモン符号の訂正能力が劣化する
ことはなく、誤り訂正の効率が良い。
【００３４】第２発明では、第１発明と同様に、リード
ソロモン受信語に対してＢＣＨ符号の復号を施すので、
誤り訂正の効率が良い。
ソロモン受信語に対してＢＣＨ符号の復号を施すので、
誤り訂正の効率が良い。
【００３５】第３発明では、この変換手段による基底変
換処理によって、ＢＣＨ符号の復号を行える。
換処理によって、ＢＣＨ符号の復号を行える。
【００３６】第４発明では、ｍ個の各ＦＩＦＯメモリに
ＢＣＨ受信語を格納し、これらのＦＩＦＯメモリの出力
を切り換えるので、ＢＣＨ復号手段は１個でよい。
ＢＣＨ受信語を格納し、これらのＦＩＦＯメモリの出力
を切り換えるので、ＢＣＨ復号手段は１個でよい。
【００３７】第５発明では、同じガロア体で定義された
ＢＣＨ符号，リードソロモン符号に対して、ＢＣＨ復
号，リードソロモン復号を実行する。
ＢＣＨ符号，リードソロモン符号に対して、ＢＣＨ復
号，リードソロモン復号を実行する。
【００３８】第６発明では、誤り位置を求める演算処理
を共通化したので、回路構成が簡略化される。
を共通化したので、回路構成が簡略化される。
【００３９】第７発明では、ＢＣＨ復号とリードソロモ
ン復号とが併用されるので、誤り訂正の効率が良い。
ン復号とが併用されるので、誤り訂正の効率が良い。
【００４０】第８発明では、このようなメモリ配列にす
ることにより、ＢＣＨ符号の受信語をリードソロモン符
号として復号できる。
ることにより、ＢＣＨ符号の受信語をリードソロモン符
号として復号できる。
【００４１】第９発明では、ＢＣＨ符号の符号語を伝送
するシステムにおいて、ｍ個のＢＣＨ受信語毎にリード
ソロモン符号として受信語を構成して誤りを訂正するこ
とができる。
するシステムにおいて、ｍ個のＢＣＨ受信語毎にリード
ソロモン符号として受信語を構成して誤りを訂正するこ
とができる。
【００４２】第10発明では、ｍ個のＢＣＨ符号の受信語
毎に纏めてリードソロモン符号として復号して誤りを訂
正し、訂正できないときは更に誤りをＢＣＨ復号して訂
正するので、誤り訂正の効率が高い。
毎に纏めてリードソロモン符号として復号して誤りを訂
正し、訂正できないときは更に誤りをＢＣＨ復号して訂
正するので、誤り訂正の効率が高い。
【００４３】第11発明では、ｍ個のＢＣＨ符号を復号し
て誤りを訂正し、訂正できないときは更に誤りをリード
ソロモン復号して訂正するので、誤り訂正の効率が高
い。
て誤りを訂正し、訂正できないときは更に誤りをリード
ソロモン復号して訂正するので、誤り訂正の効率が高
い。
【００４４】
【実施例】図４は本発明による復号器の一実施例の構成
図である。図中、１，２，３，４は、メモリ，アドレス
／データ／制御信号バス，リードソロモン復号器，制御
回路でわり、これらは従来のものと同一もしくは相当部
分である。６はアドレス／データ／制御信号バス２を介
したデータにシリアル／パラレル変換を行うシリアル／
パラレルフォーマット変換器、７は（Ｎ，Ｋ，Ｄ）リー
ドソロモン符号をｍ行に分解した２元のＢＣＨ符号を復
号するｍ個のＢＣＨ復号器、８は各ＢＣＨ復号器７から
の出力にパラレル／シリアル変換を行うパラレル／シリ
アルフォーマット変換器である。リードソロモン符号と
しては、ＧＦ（２4 ）上の（15，３，13）符号を考え
る。
図である。図中、１，２，３，４は、メモリ，アドレス
／データ／制御信号バス，リードソロモン復号器，制御
回路でわり、これらは従来のものと同一もしくは相当部
分である。６はアドレス／データ／制御信号バス２を介
したデータにシリアル／パラレル変換を行うシリアル／
パラレルフォーマット変換器、７は（Ｎ，Ｋ，Ｄ）リー
ドソロモン符号をｍ行に分解した２元のＢＣＨ符号を復
号するｍ個のＢＣＨ復号器、８は各ＢＣＨ復号器７から
の出力にパラレル／シリアル変換を行うパラレル／シリ
アルフォーマット変換器である。リードソロモン符号と
しては、ＧＦ（２4 ）上の（15，３，13）符号を考え
る。
【００４５】この例では、各行ごとにＢＣＨ符号がＢＣ
Ｈ復号器７へ入力され各２個の誤りが訂正される。ＢＣ
Ｈ符号の生成多項式は同じく ｇb （ｘ）＝ｇ1 （ｘ）ｇ3 （ｘ） ＝（Ｘ4 ＋Ｘ＋１）（Ｘ4 ＋Ｘ3 ＋Ｘ2 ＋Ｘ＋１） とするならば、α，α2 ，α3 ，α4 が連続する根とな
るので最小距離は５であり、２個までの誤りが各々ＢＣ
Ｈ符号として訂正できる。
Ｈ復号器７へ入力され各２個の誤りが訂正される。ＢＣ
Ｈ符号の生成多項式は同じく ｇb （ｘ）＝ｇ1 （ｘ）ｇ3 （ｘ） ＝（Ｘ4 ＋Ｘ＋１）（Ｘ4 ＋Ｘ3 ＋Ｘ2 ＋Ｘ＋１） とするならば、α，α2 ，α3 ，α4 が連続する根とな
るので最小距離は５であり、２個までの誤りが各々ＢＣ
Ｈ符号として訂正できる。
【００４６】今位置ｉ，ｊに誤りがあるとすればシンド
ローム Ｓ1 ＝αi ＋αj Ｓ3 ＝α3i＋α3j Ｓ3 ＝（αi ＋αj ）3 ＋α2iαj ＋αi α2j ＝Ｓ1 3＋αi αj （αi ＋αj ） αi αj ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1
ローム Ｓ1 ＝αi ＋αj Ｓ3 ＝α3i＋α3j Ｓ3 ＝（αi ＋αj ）3 ＋α2iαj ＋αi α2j ＝Ｓ1 3＋αi αj （αi ＋αj ） αi αj ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1
【００４７】誤り位置多項式σ（ｘ）は σ（ｘ）＝Ｘ2 ＋σ1 Ｘ＋σ2 ＝（Ｘ＋αi ）（Ｘ＋αj ） ＝Ｘ2 ＋Ｓ1 Ｘ＋（Ｓ3 ＋Ｓ1 3）／Ｓ1 となる。従って σ1 ＝Ｓ1 σ2 ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 である。ここでｘ＝ａｙとおいて σy （ｙ）＝ｙ2 ＋（σ1 ／ａ）ｙ＋（σ2 ／ａ2 ）
【００４８】更にａ＝σ1 とおいて σy （ｙ）＝ｙ2 ＋ｙ＋（σ2 ／σ1 2） となり根ｙ1 ，ｙ2 は定数項σ2 ／σ1 2で一意に決ま
る。従って定数項でＲＯＭを索表し、ｙ1 ，ｙ2 を求
め、一次変換ｘ＝σ1 ｙにより誤りの位置を求めること
により誤りを訂正することができる。
る。従って定数項でＲＯＭを索表し、ｙ1 ，ｙ2 を求
め、一次変換ｘ＝σ1 ｙにより誤りの位置を求めること
により誤りを訂正することができる。
【００４９】図４において、メモリ１より読み出された
データは、アドレス／データ／制御信号バス２を介して
シリアル／パラレルフォーマット変換器６を通過して各
ＢＣＨ復号器７で復号される。各ＢＣＨ復号語はパラレ
ル／シリアルフォーマット変換器８を通してリードソロ
モン復号器３へ入力され、リードソロモン復号されて出
力される。この時、ＢＣＨ復号時の誤り位置情報をリー
ドソロモン復号にも利用できることはいうまでもない。
データは、アドレス／データ／制御信号バス２を介して
シリアル／パラレルフォーマット変換器６を通過して各
ＢＣＨ復号器７で復号される。各ＢＣＨ復号語はパラレ
ル／シリアルフォーマット変換器８を通してリードソロ
モン復号器３へ入力され、リードソロモン復号されて出
力される。この時、ＢＣＨ復号時の誤り位置情報をリー
ドソロモン復号にも利用できることはいうまでもない。
【００５０】図５はＢＣＨ復号器７を１つに共通化した
本発明の他の実施例の復号器を示すブロック回路図であ
る。図中、９はシリアル／パラレルフォーマット変換器
６からの出力を格納するｍ個のＦＩＦＯメモリ、10は各
ＦＩＦＯメモリ９からの出力を切り換えるスイッチ、11
は復号結果を格納するｍ個のＦＩＦＯメモリ、12は各Ｆ
ＩＦＯメモリ11への接続を切り換えるスイッチである。
本発明の他の実施例の復号器を示すブロック回路図であ
る。図中、９はシリアル／パラレルフォーマット変換器
６からの出力を格納するｍ個のＦＩＦＯメモリ、10は各
ＦＩＦＯメモリ９からの出力を切り換えるスイッチ、11
は復号結果を格納するｍ個のＦＩＦＯメモリ、12は各Ｆ
ＩＦＯメモリ11への接続を切り換えるスイッチである。
【００５１】データはシリアル／パラレルフォーマット
変換器６を通過して各ＦＩＦＯメモリ９へ各々格納され
る。スイッチ10によって、１つのＢＣＨ受信語毎に復号
がＢＣＨ復号器７において実行され、得られた復号語は
ＦＩＦＯメモリ11へ順次出力される。ＢＣＨ復号器７が
ｍ回復号した後に、ＦＩＦＯメモリ11には順に復号結果
が格納される。この復号結果がパラレル／シリアルフォ
ーマット変換器８を通してリードソロモン復号器３に入
力され、さらに復号して出力を得る。
変換器６を通過して各ＦＩＦＯメモリ９へ各々格納され
る。スイッチ10によって、１つのＢＣＨ受信語毎に復号
がＢＣＨ復号器７において実行され、得られた復号語は
ＦＩＦＯメモリ11へ順次出力される。ＢＣＨ復号器７が
ｍ回復号した後に、ＦＩＦＯメモリ11には順に復号結果
が格納される。この復号結果がパラレル／シリアルフォ
ーマット変換器８を通してリードソロモン復号器３に入
力され、さらに復号して出力を得る。
【００５２】図６はＢＣＨ復号部とリードソロモン復号
部との演算部を一部共通化した本発明の他の実施例の復
号器を示すブロック回路図である。即ち、ＢＣＨ符号，
リードソロモン符号がともに同じガロア体で定義されて
おり、シンドロームから誤り位置を求める部分（ＧＦ演
算部13）は共通化することができる。その他はＢＣＨ復
号、リードソロモン復号特有の回路となる。例えば、Ｂ
ＣＨ復号部7aのみに含まれるものは基底変換回路があ
る。一方、リードソロモン符号部3aのみに含まれるもの
は誤りパターン計算回路部である。
部との演算部を一部共通化した本発明の他の実施例の復
号器を示すブロック回路図である。即ち、ＢＣＨ符号，
リードソロモン符号がともに同じガロア体で定義されて
おり、シンドロームから誤り位置を求める部分（ＧＦ演
算部13）は共通化することができる。その他はＢＣＨ復
号、リードソロモン復号特有の回路となる。例えば、Ｂ
ＣＨ復号部7aのみに含まれるものは基底変換回路があ
る。一方、リードソロモン符号部3aのみに含まれるもの
は誤りパターン計算回路部である。
【００５３】例として２元符号としての（15，７，５）
ＢＣＨ受信語よりシンドロームＳ1，Ｓ2 ，Ｓ3 ，Ｓ4
を得る基底変換器の構成例を図７に示す。受信入力はｇ
1 （ｘ）の除算回路を構成するシフトレジスタｇ1 ，ｇ
2 （ｘ）の除算回路を構成するシフトレジスタｇ2 へ入
力して除算結果が得られる。ｇ1 ，ｇ2 の除算結果はＶ
1 ，Ｖ2 の基底変換回路によってＧＦ（２4 ）上のベク
トル表現に変換される。
ＢＣＨ受信語よりシンドロームＳ1，Ｓ2 ，Ｓ3 ，Ｓ4
を得る基底変換器の構成例を図７に示す。受信入力はｇ
1 （ｘ）の除算回路を構成するシフトレジスタｇ1 ，ｇ
2 （ｘ）の除算回路を構成するシフトレジスタｇ2 へ入
力して除算結果が得られる。ｇ1 ，ｇ2 の除算結果はＶ
1 ，Ｖ2 の基底変換回路によってＧＦ（２4 ）上のベク
トル表現に変換される。
【００５４】図８は（15，７，５）ＢＣＨ符号の受信語
を４個のメモリ内に再生した図である。即ち、（15，
７，５）ＢＣＨ符号語を送信，受信するシステムにおい
て、ＢＣＨ受信語として復号するのみならず、ＧＦ（２
4 ）上の（15，11，５）リードソロモン符号の部分符号
である（15，７，５）リードソロモン符号の受信語とし
て復号することができる。
を４個のメモリ内に再生した図である。即ち、（15，
７，５）ＢＣＨ符号語を送信，受信するシステムにおい
て、ＢＣＨ受信語として復号するのみならず、ＧＦ（２
4 ）上の（15，11，５）リードソロモン符号の部分符号
である（15，７，５）リードソロモン符号の受信語とし
て復号することができる。
【００５５】即ち、（15，７，５）ＢＣＨ符号で訂正し
きれず残留する誤りの内、最も生起確率が大なるものは
図９に示すような１行のＢＣＨ受信語に３ビット誤りが
生起する場合である。この３ビット誤りをリードソロモ
ン符号の３シンボル誤りとみて訂正する例を示す。誤り
はαi ，αj ，αk の３カ所に１ビットの誤りを同じビ
ット位置にもつシンボル誤りであるから３つの誤りパタ
ーンは同一誤りパターンであると仮定し、これをｅ0 と
置くと、 Ｓ1 ＝ｅ0 αi ＋ｅ0 αj ＋ｅ0 αk Ｓ2 ＝ｅ0 α2i ＋ｅ0 α2j ＋ｅ0 α2k Ｓ3 ＝ｅ0 α3i ＋ｅ0 α3j ＋ｅ0 α3k Ｓ4 ＝ｅ0 α4i ＋ｅ0 α4j ＋ｅ0 α4k となる。Ｓ1 ，Ｓ2 ，Ｓ3 ，Ｓ4 は既知でありｅ0 ，α
i ，αj ，αk は未知で方程式は４個あるので解くこと
ができ、誤りパターンｅ0 とその誤り位置αi ，αj ，
αk が求まり誤りが訂正される。
きれず残留する誤りの内、最も生起確率が大なるものは
図９に示すような１行のＢＣＨ受信語に３ビット誤りが
生起する場合である。この３ビット誤りをリードソロモ
ン符号の３シンボル誤りとみて訂正する例を示す。誤り
はαi ，αj ，αk の３カ所に１ビットの誤りを同じビ
ット位置にもつシンボル誤りであるから３つの誤りパタ
ーンは同一誤りパターンであると仮定し、これをｅ0 と
置くと、 Ｓ1 ＝ｅ0 αi ＋ｅ0 αj ＋ｅ0 αk Ｓ2 ＝ｅ0 α2i ＋ｅ0 α2j ＋ｅ0 α2k Ｓ3 ＝ｅ0 α3i ＋ｅ0 α3j ＋ｅ0 α3k Ｓ4 ＝ｅ0 α4i ＋ｅ0 α4j ＋ｅ0 α4k となる。Ｓ1 ，Ｓ2 ，Ｓ3 ，Ｓ4 は既知でありｅ0 ，α
i ，αj ，αk は未知で方程式は４個あるので解くこと
ができ、誤りパターンｅ0 とその誤り位置αi ，αj ，
αk が求まり誤りが訂正される。
【００５６】図10は本発明による他の実施例復号器の構
成図である。図で14はデータ入力端子、15はＢＣＨ符号
器、16は第１インターリーブメモリ、17は第２インター
リーブメモリ、18はスイッチ、19は符号化側のメモリ制
御回路、20は通信路（または記録再生媒体）、21はシリ
アル／パラレルフォーマット変換器、22は第３インター
リーブメモリ、23は第４インターリーブメモリ、24はス
イッチ、25は復号側のメモリ制御回路、26はリードソロ
モン符号に対するリードソロモン復号器、27は出力端子
である。
成図である。図で14はデータ入力端子、15はＢＣＨ符号
器、16は第１インターリーブメモリ、17は第２インター
リーブメモリ、18はスイッチ、19は符号化側のメモリ制
御回路、20は通信路（または記録再生媒体）、21はシリ
アル／パラレルフォーマット変換器、22は第３インター
リーブメモリ、23は第４インターリーブメモリ、24はス
イッチ、25は復号側のメモリ制御回路、26はリードソロ
モン符号に対するリードソロモン復号器、27は出力端子
である。
【００５７】入力端子14より入力されたデータはＢＣＨ
符号器15で符号化され、第１インターリーブメモリ16及
び第２インターリーブメモリ17へ交互に記録される。メ
モリ制御回路19は書き込むときはＢＣＨ符号長Ｎの方向
に書き込みｍ×Ｌ段のＢＣＨ符号語を順次書き込む。読
み出すときはＢＣＨ符号語と直交する方向にｍ×Ｌビッ
トづつ読み出し、スイッチ18を介して通信路20へ送出す
る。スイッチ18は常に読み出しになっているインターリ
ーブメモリ側に接続される。
符号器15で符号化され、第１インターリーブメモリ16及
び第２インターリーブメモリ17へ交互に記録される。メ
モリ制御回路19は書き込むときはＢＣＨ符号長Ｎの方向
に書き込みｍ×Ｌ段のＢＣＨ符号語を順次書き込む。読
み出すときはＢＣＨ符号語と直交する方向にｍ×Ｌビッ
トづつ読み出し、スイッチ18を介して通信路20へ送出す
る。スイッチ18は常に読み出しになっているインターリ
ーブメモリ側に接続される。
【００５８】受信側では通信路で雑音が加算されたまま
受信されシリアル／パラレルフォーマット変換器21でｍ
ビット単位で第３インターリーブメモリ22または第４イ
ンターリーブメモリ23へ書き込まれる。インターリーブ
メモリの書き込みはＬバイト（この場合１バイトはｍビ
ットとなる）単位で行なわれる。読み出しはＮバイト単
位に行なわれる。スイッチ24は常に読み出し側のインタ
ーリーブメモリを選択して、リードソロモン復号器26で
誤りが訂正され、出力端子27からデータが出力される。
受信されシリアル／パラレルフォーマット変換器21でｍ
ビット単位で第３インターリーブメモリ22または第４イ
ンターリーブメモリ23へ書き込まれる。インターリーブ
メモリの書き込みはＬバイト（この場合１バイトはｍビ
ットとなる）単位で行なわれる。読み出しはＮバイト単
位に行なわれる。スイッチ24は常に読み出し側のインタ
ーリーブメモリを選択して、リードソロモン復号器26で
誤りが訂正され、出力端子27からデータが出力される。
【００５９】ここで、４個のインターリーブメモリの動
作を、図11, 図12を参照して説明する。まず、第１イン
ターリーブメモリ16はｍ×Ｎの２次元アドレスを持ち各
々のアドレスに１ビットのデータが読み書きできるとす
る。ＢＣＨ符号化が終わった各データビットは、図11の
水平方向へ書き込まれる。即ち、Ｎビットのデータがア
ドレス（０，０）より（０，Ｎ−１）へ書き込まれる。
ここで（ｘ，ｙ）表記でｘは垂直方向，ｙは水平方向の
アドレスを表すとする。２番目のＢＣＨ符号語は（１，
０）から（１，Ｎ−１）に書き込まれ最終的に（ｍ×
Ｌ，０）から（ｍ×Ｌ，Ｎ−１）のＢＣＨ符号語が書き
込まれて第１インターリーブメモリ16の書き込みが終了
する。この間第２インターリーブメモリ17からはデータ
の読み出しが行われているが、第１インターリーブメモ
リ16の書き込みが終了するとメモリ制御回路19は第２イ
ンターリーブメモリ17へＢＣＨ符号語の書き込みを開始
し、第１インターリーブメモリ16からはデータの読み出
しを行って、スイッチ18を介して通信路20へ出力する。
この時データ（０，０）から（１，０）…（ｍ×Ｌ，
０）の順のｍ×Ｌビットがまず読み出され、次に（０，
１）（１，１）…（ｍ×Ｌ，１）の順にｍ×Ｌビットが
まず読み出されて、通信路20へ出力される。
作を、図11, 図12を参照して説明する。まず、第１イン
ターリーブメモリ16はｍ×Ｎの２次元アドレスを持ち各
々のアドレスに１ビットのデータが読み書きできるとす
る。ＢＣＨ符号化が終わった各データビットは、図11の
水平方向へ書き込まれる。即ち、Ｎビットのデータがア
ドレス（０，０）より（０，Ｎ−１）へ書き込まれる。
ここで（ｘ，ｙ）表記でｘは垂直方向，ｙは水平方向の
アドレスを表すとする。２番目のＢＣＨ符号語は（１，
０）から（１，Ｎ−１）に書き込まれ最終的に（ｍ×
Ｌ，０）から（ｍ×Ｌ，Ｎ−１）のＢＣＨ符号語が書き
込まれて第１インターリーブメモリ16の書き込みが終了
する。この間第２インターリーブメモリ17からはデータ
の読み出しが行われているが、第１インターリーブメモ
リ16の書き込みが終了するとメモリ制御回路19は第２イ
ンターリーブメモリ17へＢＣＨ符号語の書き込みを開始
し、第１インターリーブメモリ16からはデータの読み出
しを行って、スイッチ18を介して通信路20へ出力する。
この時データ（０，０）から（１，０）…（ｍ×Ｌ，
０）の順のｍ×Ｌビットがまず読み出され、次に（０，
１）（１，１）…（ｍ×Ｌ，１）の順にｍ×Ｌビットが
まず読み出されて、通信路20へ出力される。
【００６０】受信側の第３インターリーブメモリ22，第
４インターリーブメモリ23では、図12のように、（０，
０）（１，０）…（ｍ×Ｌ，０）の順にデータが書き込
まれる。第１列が終了すると、（０，１）（１，１）…
（ｍ×Ｌ，１）の順にＮ列全部が書き込まれる。この間
もう一方の第４インターリーブメモリ23（または第３イ
ンターリーブメモリ22）からはデータが読み出され、第
３インターリーブメモリ22（または第４インターリーブ
メモリ23）の書き込みが終了すると、メモリ制御回路25
は、読み出しと書き込みとを切り換えて、今度は第３イ
ンターリーブメモリ22（または第４インターリーブメモ
リ23）から読み出しを行う。今度はリードソロモン受信
語としてデータを読み出すので、読み出しは（０，０）
（１，０）…（ｍ，０）とますｍビットをパラレルに出
力し、次に、（０，１）（１，１）…（ｍ，１）のｍビ
ットを、次には（０，２）（１，２）…（ｍ，２）のｍ
ビットと順々にｍビットずつ出力し、（０，Ｎ−１）
（１，Ｎ−１）…（ｍ，Ｎ−１）と出力して最初のリー
ドソロモン受信語が出力される。その次に（ｍ＋１，
０）（ｍ＋２，０）…（２ｍ，０）のｍビットと順次ｍ
ビットずつ出力されて、２番目のリードソロモン受信語
が出力される。このようにして最後のＬ番目のリードソ
ロモン受信語がｍ×Ｎビット出力され、第３インターリ
ーブメモリ22（または第４インターリーブメモリ23）の
読み出しが終了する。以上のように、ＢＣＨ符号語とリ
ードソロモン符号語とのビットとシンボルとの区分けが
スムーズに実行される。
４インターリーブメモリ23では、図12のように、（０，
０）（１，０）…（ｍ×Ｌ，０）の順にデータが書き込
まれる。第１列が終了すると、（０，１）（１，１）…
（ｍ×Ｌ，１）の順にＮ列全部が書き込まれる。この間
もう一方の第４インターリーブメモリ23（または第３イ
ンターリーブメモリ22）からはデータが読み出され、第
３インターリーブメモリ22（または第４インターリーブ
メモリ23）の書き込みが終了すると、メモリ制御回路25
は、読み出しと書き込みとを切り換えて、今度は第３イ
ンターリーブメモリ22（または第４インターリーブメモ
リ23）から読み出しを行う。今度はリードソロモン受信
語としてデータを読み出すので、読み出しは（０，０）
（１，０）…（ｍ，０）とますｍビットをパラレルに出
力し、次に、（０，１）（１，１）…（ｍ，１）のｍビ
ットを、次には（０，２）（１，２）…（ｍ，２）のｍ
ビットと順々にｍビットずつ出力し、（０，Ｎ−１）
（１，Ｎ−１）…（ｍ，Ｎ−１）と出力して最初のリー
ドソロモン受信語が出力される。その次に（ｍ＋１，
０）（ｍ＋２，０）…（２ｍ，０）のｍビットと順次ｍ
ビットずつ出力されて、２番目のリードソロモン受信語
が出力される。このようにして最後のＬ番目のリードソ
ロモン受信語がｍ×Ｎビット出力され、第３インターリ
ーブメモリ22（または第４インターリーブメモリ23）の
読み出しが終了する。以上のように、ＢＣＨ符号語とリ
ードソロモン符号語とのビットとシンボルとの区分けが
スムーズに実行される。
【００６１】ＢＣＨ符号の生成多項式を ｇb （ｘ）＝ｇ1 （ｘ）ｇ3 （ｘ） ＝（Ｘ4 ＋Ｘ＋１）（Ｘ4 ＋Ｘ3 ＋Ｘ2 ＋Ｘ＋１） とするならばα，α2 ，α3 ，α4 が連続する根となる
ので最小距離は５であり、２個までの誤りが各々ＢＣＨ
符号として訂正できる。このとき符号長15，情報記号数
７，チェックシンボル８となる。
ので最小距離は５であり、２個までの誤りが各々ＢＣＨ
符号として訂正できる。このとき符号長15，情報記号数
７，チェックシンボル８となる。
【００６２】ここでＧＦ（２4 ）上の生成多項式 Ｇ（ｘ）＝（Ｘ−α）（Ｘ−α2 ）（Ｘ−α3 ）（Ｘ−α4 ） を考えるならば、α，α2 ，α3 ，α4 が連続する根と
なるので、リードソロモン符号としても最小距離が５で
あり、２個までの誤りが訂正できるが、ＢＣＨ符号と違
うのは４ビット一まとめにして２個のエラーを訂正でき
ることである。パラメータはＧＦ（２4 ）上の（15，
７，５）リードソロモン符号となる。これは（15，11，
５）リードソロモン符号の部分符号である。
なるので、リードソロモン符号としても最小距離が５で
あり、２個までの誤りが訂正できるが、ＢＣＨ符号と違
うのは４ビット一まとめにして２個のエラーを訂正でき
ることである。パラメータはＧＦ（２4 ）上の（15，
７，５）リードソロモン符号となる。これは（15，11，
５）リードソロモン符号の部分符号である。
【００６３】ここで主としてバースト誤りを訂正する復
号器を考えよう。図13のように長大なバースト誤りが伝
送方向に分散され、直交方向に訂正すればランダム誤り
となっているから訂正可能となるわけであるが、リード
ソロモン受信語としてｍ×Ｎ単位（今の場合、４×15単
位) に復号するのでＮ単位に行なわれるＢＣＨ符号の復
号に比べて復号スピードが速くなる。もしＢＣＨ復号と
リードソロモン復号とが同じと仮定すると（実際はリー
ドソロモン符号のほうが少し長い）約１／ｍに短縮され
る。従ってこの実施例では１／４近くに短縮される可能
性がある。
号器を考えよう。図13のように長大なバースト誤りが伝
送方向に分散され、直交方向に訂正すればランダム誤り
となっているから訂正可能となるわけであるが、リード
ソロモン受信語としてｍ×Ｎ単位（今の場合、４×15単
位) に復号するのでＮ単位に行なわれるＢＣＨ符号の復
号に比べて復号スピードが速くなる。もしＢＣＨ復号と
リードソロモン復号とが同じと仮定すると（実際はリー
ドソロモン符号のほうが少し長い）約１／ｍに短縮され
る。従ってこの実施例では１／４近くに短縮される可能
性がある。
【００６４】いま位置ｉ，ｊに誤りがあるとするとリー
ドソロモン符号のシンドロームは、以下のようになる。 Ｓ1 ＝ｅi αi ＋ｅj αj Ｓ2 ＝ｅi α2i＋ｅj α2j Ｓ3 ＝ｅi α3i＋ｅj α3j Ｓ4 ＝ｅi α4i＋ｅj α4j 未知数ｅi ，ｅj ，αi ，αj を解いて誤りを訂正す
る。データはリードソロモン復号されて出力される。
ドソロモン符号のシンドロームは、以下のようになる。 Ｓ1 ＝ｅi αi ＋ｅj αj Ｓ2 ＝ｅi α2i＋ｅj α2j Ｓ3 ＝ｅi α3i＋ｅj α3j Ｓ4 ＝ｅi α4i＋ｅj α4j 未知数ｅi ，ｅj ，αi ，αj を解いて誤りを訂正す
る。データはリードソロモン復号されて出力される。
【００６５】図14にリードソロモン復号後にＢＣＨ復号
するようにした他の実施例の構成を示す。28はリードソ
ロモン復号器26の出力ににパラレル／シリアル変換を施
すパラレル／シリアルフォーマット変換器、29はパラレ
ル／シリアルフォーマット変換器28の出力をＢＣＨ復号
するＢＣＨ復号器である。リードソロモン復号後訂正で
きなかった場合に、ＢＣＨ符号で復号すいる。例えば、
ランダム誤りが主体で各行のＢＣＨ符号語に２個誤りが
生起しているとする。今位置ｉ，ｊに誤りがあるとすれ
ばシンドローム Ｓ1 ＝αi ＋αj Ｓ3 ＝α3i＋α3j Ｓ3 ＝（αi ＋αj ）3 ＋α2iαj ＋αi α2j ＝Ｓ1 3＋αi αj （αi ＋αj ） αi αj ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 誤り位置多項式σ（ｘ）は σ（ｘ）＝Ｘ2 ＋σ1 Ｘ＋σ2 ＝（Ｘ＋αi ）（Ｘ＋αj ） ＝Ｘ2 ＋Ｓ1 Ｘ＋（Ｓ3 ＋Ｓ1 3）／Ｓ1 となる。従って σ1 ＝Ｓ1 σ2 ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 である。ここでｘ＝ａｙとおいて σy （ｙ）＝ｙ2 ＋（σ1 ／ａ）ｙ＋（σ2 ／ａ2 ） 更にａ＝σ1 とおいて σy （ｙ）＝ｙ2 ＋ｙ＋（σ2 ／σ1 2） となり根ｙ1 ，ｙ2 は定数項σ2 ／σ1 2で一意に決ま
る。従って定数項でＲＯＭを索表し、ｙ1 ，ｙ2 を求
め、一次変換ｘ＝σ1 ｙにより誤りの位置を求めること
により誤りを訂正することができる。即ち、リードソロ
モン符号が訂正できなかった場合はランダム性のノイズ
が主体的であるので各々ＢＣＨ符号の受信語でみてＢＣ
Ｈ符号としての訂正を行なえば訂正できる場合がある。
するようにした他の実施例の構成を示す。28はリードソ
ロモン復号器26の出力ににパラレル／シリアル変換を施
すパラレル／シリアルフォーマット変換器、29はパラレ
ル／シリアルフォーマット変換器28の出力をＢＣＨ復号
するＢＣＨ復号器である。リードソロモン復号後訂正で
きなかった場合に、ＢＣＨ符号で復号すいる。例えば、
ランダム誤りが主体で各行のＢＣＨ符号語に２個誤りが
生起しているとする。今位置ｉ，ｊに誤りがあるとすれ
ばシンドローム Ｓ1 ＝αi ＋αj Ｓ3 ＝α3i＋α3j Ｓ3 ＝（αi ＋αj ）3 ＋α2iαj ＋αi α2j ＝Ｓ1 3＋αi αj （αi ＋αj ） αi αj ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 誤り位置多項式σ（ｘ）は σ（ｘ）＝Ｘ2 ＋σ1 Ｘ＋σ2 ＝（Ｘ＋αi ）（Ｘ＋αj ） ＝Ｘ2 ＋Ｓ1 Ｘ＋（Ｓ3 ＋Ｓ1 3）／Ｓ1 となる。従って σ1 ＝Ｓ1 σ2 ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 である。ここでｘ＝ａｙとおいて σy （ｙ）＝ｙ2 ＋（σ1 ／ａ）ｙ＋（σ2 ／ａ2 ） 更にａ＝σ1 とおいて σy （ｙ）＝ｙ2 ＋ｙ＋（σ2 ／σ1 2） となり根ｙ1 ，ｙ2 は定数項σ2 ／σ1 2で一意に決ま
る。従って定数項でＲＯＭを索表し、ｙ1 ，ｙ2 を求
め、一次変換ｘ＝σ1 ｙにより誤りの位置を求めること
により誤りを訂正することができる。即ち、リードソロ
モン符号が訂正できなかった場合はランダム性のノイズ
が主体的であるので各々ＢＣＨ符号の受信語でみてＢＣ
Ｈ符号としての訂正を行なえば訂正できる場合がある。
【００６６】図15にＢＣＨ復号部29a とリードソロモン
復号部26a とを一部共通化した他の実施例の構成を示
す。即ち、ＢＣＨ符号，リードソロモン符号がともに同
じガロア体で定義されている場合、これらのＧＦ演算部
30を共通化することができる。その他はＢＣＨ復号, リ
ードソロモン復号特有の回路となる。例えば、ＢＣＨ復
号部29a のみに含まれるものは基底変換回路がある。一
方、例えばリードソロモン復号部26a のみに含まれるも
のは誤りパターン計算回路部がある。
復号部26a とを一部共通化した他の実施例の構成を示
す。即ち、ＢＣＨ符号，リードソロモン符号がともに同
じガロア体で定義されている場合、これらのＧＦ演算部
30を共通化することができる。その他はＢＣＨ復号, リ
ードソロモン復号特有の回路となる。例えば、ＢＣＨ復
号部29a のみに含まれるものは基底変換回路がある。一
方、例えばリードソロモン復号部26a のみに含まれるも
のは誤りパターン計算回路部がある。
【００６７】なお、上述の各実施例ではガロア体ＧＦ
（２4 ）にて説明したが、例えばガロア体ＧＦ（２8 ）
等の他のガロア体ＧＦにおいても本発明が適用可能であ
ることはいうまでもない。
（２4 ）にて説明したが、例えばガロア体ＧＦ（２8 ）
等の他のガロア体ＧＦにおいても本発明が適用可能であ
ることはいうまでもない。
【００６８】
【発明の効果】以上のように、本発明によれば、ｍビッ
ト１シンボルのリードソロモン符号語を、１ビット１シ
ンボルのｍ個のＢＣＨ符号語に分割してそれぞれのＢＣ
Ｈ符号語で誤りを訂正するので、分散しているランダム
誤りを効率よく訂正することができる。また、ＢＣＨ受
信語をリードソロモン符号の受信語としても訂正できる
ので効率よく誤りを訂正することができる。
ト１シンボルのリードソロモン符号語を、１ビット１シ
ンボルのｍ個のＢＣＨ符号語に分割してそれぞれのＢＣ
Ｈ符号語で誤りを訂正するので、分散しているランダム
誤りを効率よく訂正することができる。また、ＢＣＨ受
信語をリードソロモン符号の受信語としても訂正できる
ので効率よく誤りを訂正することができる。
【００６９】また、ＢＣＨ符号を深さｍ×Ｌのインタリ
ーブのバッファメモリに蓄積しｍビット１シンボルのリ
ードソロモン符号語として誤りを訂正するのでバースト
誤りを分散させて効率よく訂正することができる。ま
た、ＢＣＨ受信語としても訂正できるのでリードソロモ
ン符号として訂正できなかった誤りを効率よく訂正でき
る。
ーブのバッファメモリに蓄積しｍビット１シンボルのリ
ードソロモン符号語として誤りを訂正するのでバースト
誤りを分散させて効率よく訂正することができる。ま
た、ＢＣＨ受信語としても訂正できるのでリードソロモ
ン符号として訂正できなかった誤りを効率よく訂正でき
る。
【図１】従来のリードソロモン符号の復号器のブロック
回路図である。
回路図である。
【図２】別の従来の方式の復号フローチャートを示す図
である。
である。
【図３】リードソロモン符号の受信語に生起した誤りパ
ターンの例を示す図である。
ターンの例を示す図である。
【図４】本発明の一実施例の復号器のブロック回路図で
ある。
ある。
【図５】本発明の他の実施例の復号器のブロック回路図
である
である
【図６】本発明の更に他の実施例の復号器のブロック回
路図である。
路図である。
【図７】ＢＣＨ符号の復号器に用いられる基底変換器の
ブロック回路図である。
ブロック回路図である。
【図８】ＢＣＨ符号をメモリ内でｍ×Ｎの配列に構成し
た例を示す図である。
た例を示す図である。
【図９】ＢＣＨ受信語をリードソロモン受信語とみた
時、訂正できる誤りパターンの例を示す図である。
時、訂正できる誤りパターンの例を示す図である。
【図１０】本発明の更に他の実施例の復号器のブロック
回路図である。
回路図である。
【図１１】図10における第１，第２インターリーブメモ
リ内のデータの一例を示す図である。
リ内のデータの一例を示す図である。
【図１２】図10における第３，第４インターリーブメモ
リ内のデータの一例を示す図である。
リ内のデータの一例を示す図である。
【図１３】リードソロモン符号の受信語に生起した誤り
パターンの一例を示す図である。
パターンの一例を示す図である。
【図１４】本発明の更に他の実施例の復号器のブロック
回路図である。
回路図である。
【図１５】本発明の更に他の実施例の復号器のブロック
回路図である。
回路図である。
１ メモリ ２ アドレス／データ／制御信号バス ３ リードソロモン復号器 3a リードソロモン復号部 ４ 制御回路 ６ シリアル／パラレルフォーマット変換器 ７ ＢＣＨ復号器 7a ＢＣＨ復号部 ８ パラレル／シリアルフォーマット変換器 ９ ＦＩＦＯメモリ 10 スイッチ 11 ＦＩＦＯメモリ 12 スイッチ 15 ＢＣＨ符号器 16 第１インターリーブメモリ 17 第２インターリーブメモリ 22 第３インターリーブメモリ 23 第４インターリーブメモリ 24 スイッチ 25 メモリ制御回路 26 リードソロモン復号器 26a リードソロモン復号部 28 パラレル／シリアルフォーマット変換器 29 ＢＣＨ復号器 29a ＢＣＨ復号部
─────────────────────────────────────────────────────
【手続補正書】
【提出日】平成５年３月８日
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】請求項８
【補正方法】変更
【補正内容】
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】請求項９
【補正方法】変更
【補正内容】
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】請求項１０
【補正方法】変更
【補正内容】
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】請求項１１
【補正方法】変更
【補正内容】
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正内容】
【０００８】この時、リードソロモン符号の符号語Ｃ
（ｘ）を以下とする。
（ｘ）を以下とする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正内容】
【００１６】αをＧＦ（２4 ）上の原始元とする。送信
語を （０００００００００００００００） とする。この送信語をＧＦ（２4 ）上の既約多項式 ｍ1 （ｘ）＝Ｘ4 ＋Ｘ＋１ を用いて２値展開したものは長さ15の４個のＢＣＨ符号
語となりその生成多項式は ｇb （ｘ）＝ｍ1 （ｘ）ｍ3 （ｘ） ＝（Ｘ4 ＋Ｘ＋１）（Ｘ4 ＋Ｘ3 ＋Ｘ2 ＋Ｘ＋１） であり、（15，７，５）ＢＣＨ符号の部分符号である
（15，２，５）ＢＣＨ符号になっている。α，α2 ，α
4 ，α8 ，α3 ，α6 ，α12，α9 が根となっている。
ＧＦ（２4 ）上の受信語が （００００１α12α12α12α12α12α6 ００００） の時、長さｂ＝23（ｍ（ｔ−１）＋１＜ｂ≦ｍｔ）のソ
リッドバーストが加わっており、基底ごとに分割すると ｇb （ｘ）はα，α3 を独立な根として持つ。バースト
長ｂ’＝６，及び５の時シンドロームは次式となる。
語を （０００００００００００００００） とする。この送信語をＧＦ（２4 ）上の既約多項式 ｍ1 （ｘ）＝Ｘ4 ＋Ｘ＋１ を用いて２値展開したものは長さ15の４個のＢＣＨ符号
語となりその生成多項式は ｇb （ｘ）＝ｍ1 （ｘ）ｍ3 （ｘ） ＝（Ｘ4 ＋Ｘ＋１）（Ｘ4 ＋Ｘ3 ＋Ｘ2 ＋Ｘ＋１） であり、（15，７，５）ＢＣＨ符号の部分符号である
（15，２，５）ＢＣＨ符号になっている。α，α2 ，α
4 ，α8 ，α3 ，α6 ，α12，α9 が根となっている。
ＧＦ（２4 ）上の受信語が （００００１α12α12α12α12α12α6 ００００） の時、長さｂ＝23（ｍ（ｔ−１）＋１＜ｂ≦ｍｔ）のソ
リッドバーストが加わっており、基底ごとに分割すると ｇb （ｘ）はα，α3 を独立な根として持つ。バースト
長ｂ’＝６，及び５の時シンドロームは次式となる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正内容】
【００２７】本願の第６発明の復号器は、同一のガロア
体ＧＦ（２m ）上で動作するリードソロモン符号の復号
手段とＢＣＨ符号の復号手段とにおいて誤り位置を求め
る演算処理を共通化したことを特徴とする。
体ＧＦ（２m ）上で動作するリードソロモン符号の復号
手段とＢＣＨ符号の復号手段とにおいて誤り位置を求め
る演算処理を共通化したことを特徴とする。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００４４
【補正方法】変更
【補正内容】
【００４４】
【実施例】図４は本発明による復号器の一実施例の構成
図である。図中、１，２，３，４は、メモリ，アドレス
／データ／制御信号バス，リードソロモン復号器，制御
回路であり、これらは従来のものと同一もしくは相当部
分である。６はアドレス／データ／制御信号バス２を介
したデータにシリアル／パラレル変換を行うシリアル／
パラレルフォーマット変換器、７は（Ｎ，Ｋ，Ｄ）リー
ドソロモン符号をｍ行に分解した２元のＢＣＨ符号を復
号するｍ個のＢＣＨ復号器、８は各ＢＣＨ復号器７から
の出力にパラレル／シリアル変換を行うパラレル／シリ
アルフォーマット変換器である。リードソロモン符号と
しては、ＧＦ（２4 ）上の（15，３，13）符号を考え
る。
図である。図中、１，２，３，４は、メモリ，アドレス
／データ／制御信号バス，リードソロモン復号器，制御
回路であり、これらは従来のものと同一もしくは相当部
分である。６はアドレス／データ／制御信号バス２を介
したデータにシリアル／パラレル変換を行うシリアル／
パラレルフォーマット変換器、７は（Ｎ，Ｋ，Ｄ）リー
ドソロモン符号をｍ行に分解した２元のＢＣＨ符号を復
号するｍ個のＢＣＨ復号器、８は各ＢＣＨ復号器７から
の出力にパラレル／シリアル変換を行うパラレル／シリ
アルフォーマット変換器である。リードソロモン符号と
しては、ＧＦ（２4 ）上の（15，３，13）符号を考え
る。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正内容】
【００５３】例として２元符号としての（15，７，５）
ＢＣＨ受信語よりシンドロームＳ1，Ｓ2 ，Ｓ3 ，Ｓ4
を得る基底変換器の構成例を図７に示す。受信入力はｇ
1 （ｘ）の除算回路を構成するシフトレジスタｇ
1 （ｘ），ｇ2 （ｘ）の除算回路を構成するシフトレジ
スタｇ2 へ入力して除算結果が得られる。ｇ1 ，ｇ2 の
除算結果はＶ1 ，Ｖ2 の基底変換回路によってＧＦ（２
4 ）上のベクトル表現に変換される。
ＢＣＨ受信語よりシンドロームＳ1，Ｓ2 ，Ｓ3 ，Ｓ4
を得る基底変換器の構成例を図７に示す。受信入力はｇ
1 （ｘ）の除算回路を構成するシフトレジスタｇ
1 （ｘ），ｇ2 （ｘ）の除算回路を構成するシフトレジ
スタｇ2 へ入力して除算結果が得られる。ｇ1 ，ｇ2 の
除算結果はＶ1 ，Ｖ2 の基底変換回路によってＧＦ（２
4 ）上のベクトル表現に変換される。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００５５
【補正方法】削除
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正内容】
【００５６】図９は本発明による他の実施例復号器の構
成図である。図で14はデータ入力端子、15はＢＣＨ符号
器、16は第１インターリーブメモリ、17は第２インター
リーブメモリ、18はスイッチ、19は符号化側のメモリ制
御回路、20は通信路（または記録再生媒体）、21はシリ
アル／パラレルフォーマット変換器、22は第３インター
リーブメモリ、23は第４インターリーブメモリ、24はス
イッチ、25は復号側のメモリ制御回路、26はリードソロ
モン符号に対するリードソロモン復号器、27は出力端子
である。
成図である。図で14はデータ入力端子、15はＢＣＨ符号
器、16は第１インターリーブメモリ、17は第２インター
リーブメモリ、18はスイッチ、19は符号化側のメモリ制
御回路、20は通信路（または記録再生媒体）、21はシリ
アル／パラレルフォーマット変換器、22は第３インター
リーブメモリ、23は第４インターリーブメモリ、24はス
イッチ、25は復号側のメモリ制御回路、26はリードソロ
モン符号に対するリードソロモン復号器、27は出力端子
である。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００５９
【補正方法】変更
【補正内容】
【００５９】ここで、４個のインターリーブメモリの動
作を、図10, 図11を参照して説明する。まず、第１イン
ターリーブメモリ16はｍ×Ｎの２次元アドレスを持ち各
々のアドレスに１ビットのデータが読み書きできるとす
る。ＢＣＨ符号化が終わった各データビットは、図10の
水平方向へ書き込まれる。即ち、Ｎビットのデータがア
ドレス（０，０）より（０，Ｎ−１）へ書き込まれる。
ここで（ｘ，ｙ）表記でｘは垂直方向，ｙは水平方向の
アドレスを表すとする。２番目のＢＣＨ符号語は（１，
０）から（１，Ｎ−１）に書き込まれ最終的に（ｍ×
Ｌ，０）から（ｍ×Ｌ，Ｎ−１）のＢＣＨ符号語が書き
込まれて第１インターリーブメモリ16の書き込みが終了
する。この間第２インターリーブメモリ17からはデータ
の読み出しが行われているが、第１インターリーブメモ
リ16の書き込みが終了するとメモリ制御回路19は第２イ
ンターリーブメモリ17へＢＣＨ符号語の書き込みを開始
し、第１インターリーブメモリ16からはデータの読み出
しを行って、スイッチ18を介して通信路20へ出力する。
この時データ（０，０）から（１，０）…（ｍ×Ｌ，
０）の順のｍ×Ｌビットがまず読み出され、次に（０，
１）（１，１）…（ｍ×Ｌ，１）の順にｍ×Ｌビットが
まず読み出されて、通信路20へ出力される。
作を、図10, 図11を参照して説明する。まず、第１イン
ターリーブメモリ16はｍ×Ｎの２次元アドレスを持ち各
々のアドレスに１ビットのデータが読み書きできるとす
る。ＢＣＨ符号化が終わった各データビットは、図10の
水平方向へ書き込まれる。即ち、Ｎビットのデータがア
ドレス（０，０）より（０，Ｎ−１）へ書き込まれる。
ここで（ｘ，ｙ）表記でｘは垂直方向，ｙは水平方向の
アドレスを表すとする。２番目のＢＣＨ符号語は（１，
０）から（１，Ｎ−１）に書き込まれ最終的に（ｍ×
Ｌ，０）から（ｍ×Ｌ，Ｎ−１）のＢＣＨ符号語が書き
込まれて第１インターリーブメモリ16の書き込みが終了
する。この間第２インターリーブメモリ17からはデータ
の読み出しが行われているが、第１インターリーブメモ
リ16の書き込みが終了するとメモリ制御回路19は第２イ
ンターリーブメモリ17へＢＣＨ符号語の書き込みを開始
し、第１インターリーブメモリ16からはデータの読み出
しを行って、スイッチ18を介して通信路20へ出力する。
この時データ（０，０）から（１，０）…（ｍ×Ｌ，
０）の順のｍ×Ｌビットがまず読み出され、次に（０，
１）（１，１）…（ｍ×Ｌ，１）の順にｍ×Ｌビットが
まず読み出されて、通信路20へ出力される。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正内容】
【００６０】受信側の第３インターリーブメモリ22，第
４インターリーブメモリ23では、図11のように、（０，
０）（１，０）…（ｍ×Ｌ，０）の順にデータが書き込
まれる。第１列が終了すると、（０，１）（１，１）…
（ｍ×Ｌ，１）の順にＮ列全部が書き込まれる。この間
もう一方の第４インターリーブメモリ23（または第３イ
ンターリーブメモリ22）からはデータが読み出され、第
３インターリーブメモリ22（または第４インターリーブ
メモリ23）の書き込みが終了すると、メモリ制御回路25
は、読み出しと書き込みとを切り換えて、今度は第３イ
ンターリーブメモリ22（または第４インターリーブメモ
リ23）から読み出しを行う。今度はリードソロモン受信
語としてデータを読み出すので、読み出しは（０，０）
（１，０）…（ｍ，０）とますｍビットをパラレルに出
力し、次に、（０，１）（１，１）…（ｍ，１）のｍビ
ットを、次には（０，２）（１，２）…（ｍ，２）のｍ
ビットと順々にｍビットずつ出力し、（０，Ｎ−１）
（１，Ｎ−１）…（ｍ，Ｎ−１）と出力して最初のリー
ドソロモン受信語が出力される。その次に（ｍ＋１，
０）（ｍ＋２，０）…（２ｍ，０）のｍビットと順次ｍ
ビットずつ出力されて、２番目のリードソロモン受信語
が出力される。このようにして最後のＬ番目のリードソ
ロモン受信語がｍ×Ｎビット出力され、第３インターリ
ーブメモリ22（または第４インターリーブメモリ23）の
読み出しが終了する。以上のように、ＢＣＨ符号語とリ
ードソロモン符号語とのビットとシンボルとの区分けが
スムーズに実行される。
４インターリーブメモリ23では、図11のように、（０，
０）（１，０）…（ｍ×Ｌ，０）の順にデータが書き込
まれる。第１列が終了すると、（０，１）（１，１）…
（ｍ×Ｌ，１）の順にＮ列全部が書き込まれる。この間
もう一方の第４インターリーブメモリ23（または第３イ
ンターリーブメモリ22）からはデータが読み出され、第
３インターリーブメモリ22（または第４インターリーブ
メモリ23）の書き込みが終了すると、メモリ制御回路25
は、読み出しと書き込みとを切り換えて、今度は第３イ
ンターリーブメモリ22（または第４インターリーブメモ
リ23）から読み出しを行う。今度はリードソロモン受信
語としてデータを読み出すので、読み出しは（０，０）
（１，０）…（ｍ，０）とますｍビットをパラレルに出
力し、次に、（０，１）（１，１）…（ｍ，１）のｍビ
ットを、次には（０，２）（１，２）…（ｍ，２）のｍ
ビットと順々にｍビットずつ出力し、（０，Ｎ−１）
（１，Ｎ−１）…（ｍ，Ｎ−１）と出力して最初のリー
ドソロモン受信語が出力される。その次に（ｍ＋１，
０）（ｍ＋２，０）…（２ｍ，０）のｍビットと順次ｍ
ビットずつ出力されて、２番目のリードソロモン受信語
が出力される。このようにして最後のＬ番目のリードソ
ロモン受信語がｍ×Ｎビット出力され、第３インターリ
ーブメモリ22（または第４インターリーブメモリ23）の
読み出しが終了する。以上のように、ＢＣＨ符号語とリ
ードソロモン符号語とのビットとシンボルとの区分けが
スムーズに実行される。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正内容】
【００６３】ここで主としてバースト誤りを訂正する復
号器を考えよう。図12のように長大なバースト誤りが伝
送方向に分散され、直交方向に訂正すればランダム誤り
となっているから訂正可能となるわけであるが、リード
ソロモン受信語としてｍ×Ｎ単位（今の場合、４×15単
位) に復号するのでＮ単位に行なわれるＢＣＨ符号の復
号に比べて復号スピードが速くなる。もしＢＣＨ復号と
リードソロモン復号とが同じと仮定すると（実際はリー
ドソロモン符号のほうが少し長い）約１／ｍに短縮され
る。従ってこの実施例では１／４近くに短縮される可能
性がある。
号器を考えよう。図12のように長大なバースト誤りが伝
送方向に分散され、直交方向に訂正すればランダム誤り
となっているから訂正可能となるわけであるが、リード
ソロモン受信語としてｍ×Ｎ単位（今の場合、４×15単
位) に復号するのでＮ単位に行なわれるＢＣＨ符号の復
号に比べて復号スピードが速くなる。もしＢＣＨ復号と
リードソロモン復号とが同じと仮定すると（実際はリー
ドソロモン符号のほうが少し長い）約１／ｍに短縮され
る。従ってこの実施例では１／４近くに短縮される可能
性がある。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正内容】
【００６５】図13にリードソロモン復号後にＢＣＨ復号
するようにした他の実施例の構成を示す。28はリードソ
ロモン復号器26の出力ににパラレル／シリアル変換を施
すパラレル／シリアルフォーマット変換器、29はパラレ
ル／シリアルフォーマット変換器28の出力をＢＣＨ復号
するＢＣＨ復号器である。リードソロモン復号後訂正で
きなかった場合に、ＢＣＨ符号で復号すいる。例えば、
ランダム誤りが主体で各行のＢＣＨ符号語に２個誤りが
生起しているとする。今位置ｉ，ｊに誤りがあるとすれ
ばシンドローム Ｓ1 ＝αi ＋αj Ｓ3 ＝α3i＋α3j Ｓ3 ＝（αi ＋αj ）3 ＋α2iαj ＋αi α2j ＝Ｓ1 3＋αi αj （αi ＋αj ） αi αj ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 誤り位置多項式σ（ｘ）は σ（ｘ）＝Ｘ2 ＋σ1 Ｘ＋σ2 ＝（Ｘ＋αi ）（Ｘ＋αj ） ＝Ｘ2 ＋Ｓ1 Ｘ＋（Ｓ3 ＋Ｓ1 3）／Ｓ1 となる。従って σ1 ＝Ｓ1 σ2 ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 である。ここでｘ＝ａｙとおいて σy （ｙ）＝ｙ2 ＋（σ1 ／ａ）ｙ＋（σ2 ／ａ2 ） 更にａ＝σ1 とおいて σy （ｙ）＝ｙ2 ＋ｙ＋（σ2 ／σ1 2） となり根ｙ1 ，ｙ2 は定数項σ2 ／σ1 2で一意に決ま
る。従って定数項でＲＯＭを索表し、ｙ1 ，ｙ2 を求
め、一次変換ｘ＝σ1 ｙにより誤りの位置を求めること
により誤りを訂正することができる。即ち、リードソロ
モン符号が訂正できなかった場合はランダム性のノイズ
が主体的であるので各々ＢＣＨ符号の受信語でみてＢＣ
Ｈ符号としての訂正を行なえば訂正できる場合がある。
するようにした他の実施例の構成を示す。28はリードソ
ロモン復号器26の出力ににパラレル／シリアル変換を施
すパラレル／シリアルフォーマット変換器、29はパラレ
ル／シリアルフォーマット変換器28の出力をＢＣＨ復号
するＢＣＨ復号器である。リードソロモン復号後訂正で
きなかった場合に、ＢＣＨ符号で復号すいる。例えば、
ランダム誤りが主体で各行のＢＣＨ符号語に２個誤りが
生起しているとする。今位置ｉ，ｊに誤りがあるとすれ
ばシンドローム Ｓ1 ＝αi ＋αj Ｓ3 ＝α3i＋α3j Ｓ3 ＝（αi ＋αj ）3 ＋α2iαj ＋αi α2j ＝Ｓ1 3＋αi αj （αi ＋αj ） αi αj ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 誤り位置多項式σ（ｘ）は σ（ｘ）＝Ｘ2 ＋σ1 Ｘ＋σ2 ＝（Ｘ＋αi ）（Ｘ＋αj ） ＝Ｘ2 ＋Ｓ1 Ｘ＋（Ｓ3 ＋Ｓ1 3）／Ｓ1 となる。従って σ1 ＝Ｓ1 σ2 ＝（Ｓ3 ＋Ｓ1 3）／Ｓ1 である。ここでｘ＝ａｙとおいて σy （ｙ）＝ｙ2 ＋（σ1 ／ａ）ｙ＋（σ2 ／ａ2 ） 更にａ＝σ1 とおいて σy （ｙ）＝ｙ2 ＋ｙ＋（σ2 ／σ1 2） となり根ｙ1 ，ｙ2 は定数項σ2 ／σ1 2で一意に決ま
る。従って定数項でＲＯＭを索表し、ｙ1 ，ｙ2 を求
め、一次変換ｘ＝σ1 ｙにより誤りの位置を求めること
により誤りを訂正することができる。即ち、リードソロ
モン符号が訂正できなかった場合はランダム性のノイズ
が主体的であるので各々ＢＣＨ符号の受信語でみてＢＣ
Ｈ符号としての訂正を行なえば訂正できる場合がある。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正内容】
【００６６】図14にＢＣＨ復号部29a とリードソロモン
復号部26a とを一部共通化した他の実施例の構成を示
す。即ち、ＢＣＨ符号，リードソロモン符号がともに同
じガロア体で定義されている場合、これらのＧＦ演算部
30を共通化することができる。その他はＢＣＨ復号, リ
ードソロモン復号特有の回路となる。例えば、ＢＣＨ復
号部29a のみに含まれるものは基底変換回路がある。一
方、例えばリードソロモン復号部26a のみに含まれるも
のは誤りパターン計算回路部がある。
復号部26a とを一部共通化した他の実施例の構成を示
す。即ち、ＢＣＨ符号，リードソロモン符号がともに同
じガロア体で定義されている場合、これらのＧＦ演算部
30を共通化することができる。その他はＢＣＨ復号, リ
ードソロモン復号特有の回路となる。例えば、ＢＣＨ復
号部29a のみに含まれるものは基底変換回路がある。一
方、例えばリードソロモン復号部26a のみに含まれるも
のは誤りパターン計算回路部がある。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】図面の簡単な説明
【補正方法】変更
【補正内容】
【図面の簡単な説明】
【図１】従来のリードソロモン符号の復号器のブロック
回路図である。
回路図である。
【図２】別の従来の方式の復号フローチャートを示す図
である。
である。
【図３】リードソロモン符号の受信語に生起した誤りパ
ターンの例を示す図である。
ターンの例を示す図である。
【図４】本発明の一実施例の復号器のブロック回路図で
ある。
ある。
【図５】本発明の他の実施例の復号器のブロック回路図
である
である
【図６】本発明の更に他の実施例の復号器のブロック回
路図である。
路図である。
【図７】ＢＣＨ符号の復号器に用いられる基底変換器の
ブロック回路図である。
ブロック回路図である。
【図８】ＢＣＨ符号をメモリ内でｍ×Ｎの配列に構成し
た例を示す図である。
た例を示す図である。
【図９】本発明の更に他の実施例の復号器のブロック回
路図である。
路図である。
【図１０】図９における第１，第２インターリーブメモ
リ内のデータの一例を示す図である。
リ内のデータの一例を示す図である。
【図１１】図９における第３，第４インターリーブメモ
リ内のデータの一例を示す図である。
リ内のデータの一例を示す図である。
【図１２】リードソロモン符号の受信語に生起した誤り
パターンの一例を示す図である。
パターンの一例を示す図である。
【図１３】本発明の更に他の実施例の復号器のブロック
回路図である。
回路図である。
【図１４】本発明の更に他の実施例の復号器のブロック
回路図である。
回路図である。
【符号の説明】 １ メモリ ２ アドレス／データ／制御信号バス ３ リードソロモン復号器 3a リードソロモン復号部 ４ 制御回路 ６ シリアル／パラレルフォーマット変換器 ７ ＢＣＨ復号器 7a ＢＣＨ復号部 ８ パラレル／シリアルフォーマット変換器 ９ ＦＩＦＯメモリ 10 スイッチ 11 ＦＩＦＯメモリ 12 スイッチ 15 ＢＣＨ符号器 16 第１インターリーブメモリ 17 第２インターリーブメモリ 22 第３インターリーブメモリ 23 第４インターリーブメモリ 24 スイッチ 25 メモリ制御回路 26 リードソロモン復号器 26a リードソロモン復号部 28 パラレル／シリアルフォーマット変換器 29 ＢＣＨ復号器 29a ＢＣＨ復号部
【手続補正１８】
【補正対象書類名】図面
【補正対象項目名】図９
【補正方法】変更
【補正内容】
【図９】
【手続補正１９】
【補正対象書類名】図面
【補正対象項目名】図１０
【補正方法】変更
【補正内容】
【図１０】
【手続補正２０】
【補正対象書類名】図面
【補正対象項目名】図１１
【補正方法】変更
【補正内容】
【図１１】
【手続補正２１】
【補正対象書類名】図面
【補正対象項目名】図１２
【補正方法】変更
【補正内容】
【図１２】
【手続補正２２】
【補正対象書類名】図面
【補正対象項目名】図１３
【補正方法】変更
【補正内容】
【図１３】
【手続補正２３】
【補正対象書類名】図面
【補正対象項目名】図１４
【補正方法】変更
【補正内容】
【図１４】
【手続補正２４】
【補正対象書類名】図面
【補正対象項目名】図１５
【補正方法】削除
Claims (11)
- 【請求項１】 第１の方向にｍビット，第２の方向にＮ
ビットのｍ×Ｎの２次元のデータとしてメモリにリード
ソロモン符号語を収納し、第２の方向のＮビットを２元
ＢＣＨ符号としてｍ回復号し、第１の方向のｍビットを
ガロア体ＧＦ（２m ）上のシンボルとして符号長Ｎシン
ボルのリードソロモン符号の復号を行うことを特徴とす
る誤り訂正方式。 - 【請求項２】 １シンボルｍビットのＮシンボルのリー
ドソロモン受信語をｍビット単位でメモリから読み出
し、読み出したｍビットをパラレルに出力してＮビット
単位のｍ個のビット系列を得、このビット系列をＢＣＨ
符号としてｍ回復号することを特徴とする誤り訂正方
式。 - 【請求項３】 ＢＣＨ符号としての復号を行うためのガ
ロア体ＧＦ（２）の除算結果をガロア体ＧＦ（２m ）の
パターンに変換する基底変換を行う変換手段を備えたこ
とを特徴とするリードソロモン符号の復号器。 - 【請求項４】 ガロア体ＧＦ（２m ）上のリードソロモ
ン受信語を１シンボルごとにシリアル／パラレル変換す
るフォーマット変換手段と、該フォーマット変換手段の
ｍ個の出力を順次入力し蓄積するＦＩＦＯメモリと、該
ＦＩＦＯメモリの出力を切り換えてｍ回ＢＣＨ復号を行
うＢＣＨ復号手段と、得られる復号結果を格納するＦＩ
ＦＯメモリとを備えたことを特徴とする復号器。 - 【請求項５】 ガロア体ＧＦ（２m ）上で動作するリー
ドソロモン符号の復号手段と、該復号手段と同じガロア
体上で動作するＢＣＨ符号の復号手段とを備え、ガロア
体ＧＦ（２m ）上で定義されたリードソロモン符号につ
いて、同じガロア体上で定義された２元ＢＣＨ符号の復
号とガロア体ＧＦ（２m ）上のリードソロモン符号の復
号とを行うように構成したことを特徴とする復号器。 - 【請求項６】 同一のガロア体ＧＦ（２m ）上で動作す
る、Ｎシンボル符号長の（Ｎ，Ｋ，Ｄ）リードソロモン
符号の復号手段と、Ｎビット符号長の（Ｎ，ｋ，ｄ）Ｂ
ＣＨ符号の復号手段とを備え、誤り位置を求める処理を
共通化すべく構成したことを特徴とする復号器。 - 【請求項７】 深さｍビットのメモリ上に構成された１
シンボルｍビットのガロア体ＧＦ（２m ）上の（Ｎ，
Ｋ，Ｄ）リードソロモン符号を復号する復号器であっ
て、リードソロモン受信語をｍ個のＢＣＨ受信語に分割
する手段と、ｍ個の各ＢＣＨ受信語を復号して誤りを訂
正する手段と、ＢＣＨ復号による誤り訂正後にリードソ
ロモン符号としての復号を行う手段とを備えたことを特
徴とする復号器。 - 【請求項８】 ガロア体ＧＦ（２m ）上の（Ｎ，ｋ，
ｄ）ＢＣＨ受信語をメモリにｍ個入力し、ｍ×Ｎのメモ
リ配列を作成してガロア体ＧＦ（２m ）上のリードソロ
モン受信語とし、リードソロモン符号として復号するこ
とを特徴とする誤り訂正方式。 - 【請求項９】 ガロア体ＧＦ（２m ）上の（Ｎ，ｋ，
ｄ）ＢＣＨ符号語における誤りを訂正する誤り訂正方式
において、前記ＢＣＨ符号語にインターリーブを施した
後、ｍ×Ｎビット単位毎にガロア体ＧＦ（２m ）上のリ
ードソロモン符号の符号語として復号することを特徴と
する誤り訂正方式。 - 【請求項１０】 ガロア体ＧＦ（２m ）上の（Ｎ，ｋ，
ｄ）ＢＣＨ符号語における誤りを訂正する誤り訂正方式
において、前記ＢＣＨ符号語にインターリーブを施し、
ｍ×Ｎビット単位毎にガロア体ＧＦ（２m ）上のリード
ソロモン符号の符号語として復号した後、更にＢＣＨ復
号を実行して誤りを訂正することを特徴とする誤り訂正
方式。 - 【請求項１１】 ガロア体ＧＦ（２m ）上の（Ｎ，ｋ，
ｄ）ＢＣＨ符号語における誤りを訂正する誤り訂正方式
において、前記ＢＣＨ符号語にインターリーブを施した
後にＢＣＨ符号を復号し、ＢＣＨ復号後のデータをリー
ドソロモン復号することを特徴とする誤り訂正方式。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4225020A JP2824474B2 (ja) | 1992-02-17 | 1992-08-01 | 誤り訂正方式及びこの誤り訂正方式を用いた復号器 |
| US08/014,235 US5537429A (en) | 1992-02-17 | 1993-02-05 | Error-correcting method and decoder using the same |
Applications Claiming Priority (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2957792 | 1992-02-17 | ||
| JP4-29577 | 1992-05-19 | ||
| JP4-126051 | 1992-05-19 | ||
| JP12605192 | 1992-05-19 | ||
| JP4225020A JP2824474B2 (ja) | 1992-02-17 | 1992-08-01 | 誤り訂正方式及びこの誤り訂正方式を用いた復号器 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0637646A true JPH0637646A (ja) | 1994-02-10 |
| JP2824474B2 JP2824474B2 (ja) | 1998-11-11 |
Family
ID=27286631
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4225020A Expired - Fee Related JP2824474B2 (ja) | 1992-02-17 | 1992-08-01 | 誤り訂正方式及びこの誤り訂正方式を用いた復号器 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5537429A (ja) |
| JP (1) | JP2824474B2 (ja) |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3710586B2 (ja) * | 1997-02-21 | 2005-10-26 | 株式会社ルネサステクノロジ | 誤り訂正装置 |
| FR2769776B1 (fr) * | 1997-10-09 | 1999-12-17 | Alsthom Cge Alcatel | Procede de codage bloc par code produit applicable notamment au codage d'une cellule atm |
| KR100330980B1 (ko) * | 1997-11-10 | 2002-04-01 | 다치카와 게이지 | 인터리빙 방법, 인터리빙 장치 및 인터리빙 패턴 생성 프로그램이 기록된 기록 매체 |
| US6634007B1 (en) | 1999-11-08 | 2003-10-14 | Codevector Technology | Algebraic soft decoding of reed-solomon codes |
| US7458007B2 (en) * | 2000-02-18 | 2008-11-25 | Texas Instruments Incorporated | Error correction structures and methods |
| JP3485075B2 (ja) * | 2000-07-19 | 2004-01-13 | 日本電気株式会社 | 復号回路及びその復号方法 |
| US20020104059A1 (en) * | 2000-12-15 | 2002-08-01 | Clara Baroncelli | In-band FEC syndrome computation for SONET |
| US20020116679A1 (en) * | 2000-12-15 | 2002-08-22 | Mike Lei | In-band FEC decoder for sonet |
| US6990624B2 (en) * | 2001-10-12 | 2006-01-24 | Agere Systems Inc. | High speed syndrome-based FEC encoder and decoder and system using same |
| US7146553B2 (en) * | 2001-11-21 | 2006-12-05 | Infinera Corporation | Error correction improvement for concatenated codes |
| WO2004095759A2 (en) * | 2003-04-22 | 2004-11-04 | Vitesse Semiconductor Corporation | Concatenated iterative forward error correction coding |
| US20050180332A1 (en) * | 2004-02-13 | 2005-08-18 | Broadcom Corporation | Low latency interleaving and deinterleaving |
| CN1561005B (zh) * | 2004-02-20 | 2010-12-08 | 汇智系统股份有限公司 | 快速纠双错bch码译码器 |
| US7502986B2 (en) * | 2005-02-09 | 2009-03-10 | International Business Machines Corporation | Method and apparatus for collecting failure information on error correction code (ECC) protected data |
| US7653862B2 (en) * | 2005-06-15 | 2010-01-26 | Hitachi Global Storage Technologies Netherlands B.V. | Error detection and correction for encoded data |
| EP1770896A1 (en) * | 2005-09-28 | 2007-04-04 | Koninklijke Philips Electronics N.V. | Method, apparatus and system for error detection and selective retransmission |
| CN100440738C (zh) * | 2005-12-16 | 2008-12-03 | 北京中星微电子有限公司 | BCH编码中Galois扩域运算的快速实现方法 |
| US7793195B1 (en) * | 2006-05-11 | 2010-09-07 | Link—A—Media Devices Corporation | Incremental generation of polynomials for decoding reed-solomon codes |
| JP2008035230A (ja) * | 2006-07-28 | 2008-02-14 | Fujifilm Corp | データ圧縮装置およびデータ圧縮プログラム |
| JP4891704B2 (ja) * | 2006-08-28 | 2012-03-07 | 株式会社東芝 | 半導体記憶装置 |
| US8171368B1 (en) * | 2007-02-16 | 2012-05-01 | Link—A—Media Devices Corporation | Probabilistic transition rule for two-level decoding of reed-solomon codes |
| US8136020B2 (en) * | 2007-09-19 | 2012-03-13 | Altera Canada Co. | Forward error correction CODEC |
| US8103934B2 (en) | 2007-12-21 | 2012-01-24 | Honeywell International Inc. | High speed memory error detection and correction using interleaved (8,4) LBCs |
| US8621322B2 (en) * | 2008-09-30 | 2013-12-31 | Freescale Semiconductor, Inc. | Data interleaver |
| JP5259343B2 (ja) * | 2008-10-31 | 2013-08-07 | 株式会社東芝 | メモリ装置 |
| JP4867980B2 (ja) * | 2008-11-26 | 2012-02-01 | 住友電気工業株式会社 | 誤り訂正復号装置 |
| RU2009119260A (ru) * | 2009-05-22 | 2010-11-27 | ЭлЭсАй Корпорейшн (US) | Декодер кодов бчх или кодов рида-соломона с модификацией синдромов |
| CN103916139B (zh) * | 2014-04-22 | 2016-12-21 | 淮安固泰存储科技有限公司 | 一种基于里德所罗门码的加强型编码方法、解码方法及解码器 |
| US11537464B2 (en) * | 2019-06-14 | 2022-12-27 | Micron Technology, Inc. | Host-based error correction |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5778608A (en) * | 1980-10-31 | 1982-05-17 | Matsushita Electric Ind Co Ltd | Decoding method of reed-solomon code |
| JPS60501930A (ja) * | 1983-07-29 | 1985-11-07 | エタブリスメント パブリツク テレデイフユ−ジヨン デ フランス | リ−ドソロモンコ−ドのディジタル信号の誤り訂正方式 |
| JPS6133023A (ja) * | 1984-07-25 | 1986-02-15 | Mitsubishi Electric Corp | 符号化復号化装置 |
| JPS6146623A (ja) * | 1984-08-10 | 1986-03-06 | Mitsubishi Electric Corp | 符号化復号化方法 |
| JPS61216044A (ja) * | 1985-03-21 | 1986-09-25 | Canon Inc | 信号処理装置 |
| JPH01256228A (ja) * | 1988-04-05 | 1989-10-12 | Nec Corp | 誤り訂正符号化装置 |
Family Cites Families (18)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB1389551A (en) * | 1972-05-15 | 1975-04-03 | Secr Defence | Multiplex digital telecommunications apparatus having error- correcting facilities |
| JPS58219852A (ja) * | 1982-06-15 | 1983-12-21 | Toshiba Corp | エラ−訂正回路 |
| US4564945A (en) * | 1983-06-20 | 1986-01-14 | Reference Technology, Inc. | Error-correction code for digital data on video disc |
| US4653051A (en) * | 1983-09-14 | 1987-03-24 | Matsushita Electric Industrial Co., Ltd. | Apparatus for detecting and correcting errors on product codes |
| JPH0812612B2 (ja) * | 1983-10-31 | 1996-02-07 | 株式会社日立製作所 | 誤り訂正方法及び装置 |
| DE3486408T2 (de) * | 1983-12-20 | 1996-03-14 | Sony Corp | Verfahren und Vorrichtung zur Dekodierung eines fehlerkorrigierenden Kodes. |
| US4555784A (en) * | 1984-03-05 | 1985-11-26 | Ampex Corporation | Parity and syndrome generation for error detection and correction in digital communication systems |
| JPS61154227A (ja) * | 1984-12-26 | 1986-07-12 | Mitsubishi Electric Corp | ２段符号化方法 |
| CA1235189A (en) * | 1985-01-14 | 1988-04-12 | Haruhiko Akiyama | Error correction encoding system |
| CA1310112C (en) * | 1985-05-21 | 1992-11-10 | Takao Abe | Apparatus for decoding error correcting code |
| JPS63186338A (ja) * | 1987-01-28 | 1988-08-01 | Nec Corp | 誤り訂正回路 |
| JPS63193723A (ja) * | 1987-02-06 | 1988-08-11 | Sony Corp | リ−ドソロモン符号の復号方法 |
| JP2751201B2 (ja) * | 1988-04-19 | 1998-05-18 | ソニー株式会社 | データ伝送装置及び受信装置 |
| US4958349A (en) * | 1988-11-01 | 1990-09-18 | Ford Aerospace Corporation | High data rate BCH decoder |
| JPH02125532A (ja) * | 1988-11-04 | 1990-05-14 | Sony Corp | Ｂｃｈ符号の復号装置 |
| US5168509A (en) * | 1989-04-12 | 1992-12-01 | Kabushiki Kaisha Toshiba | Quadrature amplitude modulation communication system with transparent error correction |
| US5040179A (en) * | 1989-08-18 | 1991-08-13 | Loral Aerospace Corp. | High data rate BCH encoder |
| US5099482A (en) * | 1989-08-30 | 1992-03-24 | Idaho Research Foundation, Inc. | Apparatus for detecting uncorrectable error patterns when using Euclid's algorithm to decode Reed-Solomon (BCH) codes |
-
1992
- 1992-08-01 JP JP4225020A patent/JP2824474B2/ja not_active Expired - Fee Related
-
1993
- 1993-02-05 US US08/014,235 patent/US5537429A/en not_active Expired - Fee Related
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5778608A (en) * | 1980-10-31 | 1982-05-17 | Matsushita Electric Ind Co Ltd | Decoding method of reed-solomon code |
| JPS60501930A (ja) * | 1983-07-29 | 1985-11-07 | エタブリスメント パブリツク テレデイフユ−ジヨン デ フランス | リ−ドソロモンコ−ドのディジタル信号の誤り訂正方式 |
| JPS6133023A (ja) * | 1984-07-25 | 1986-02-15 | Mitsubishi Electric Corp | 符号化復号化装置 |
| JPS6146623A (ja) * | 1984-08-10 | 1986-03-06 | Mitsubishi Electric Corp | 符号化復号化方法 |
| JPS61216044A (ja) * | 1985-03-21 | 1986-09-25 | Canon Inc | 信号処理装置 |
| JPH01256228A (ja) * | 1988-04-05 | 1989-10-12 | Nec Corp | 誤り訂正符号化装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5537429A (en) | 1996-07-16 |
| JP2824474B2 (ja) | 1998-11-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0637646A (ja) | 誤り訂正方式及びこの誤り訂正方式を用いた復号器 | |
| JP3549788B2 (ja) | 多段符号化方法、多段復号方法、多段符号化装置、多段復号装置およびこれらを用いた情報伝送システム | |
| US7278085B1 (en) | Simple error-correction codes for data buffers | |
| EP0026516A1 (en) | Apparatus for the processing of an information stream with the aid of an error-correcting convolutional code and for the detection of an error still irremediable in this processing | |
| CN110071727B (zh) | 编码方法、译码方法、纠错方法及装置 | |
| US4488302A (en) | Burst error correction using cyclic block codes | |
| JP2001357630A (ja) | 光ディスク記憶装置の符号化／復号化システム | |
| EP2309650B1 (en) | A systematic encoder with arbitrary parity positions | |
| US3588819A (en) | Double-character erasure correcting system | |
| JP3891568B2 (ja) | 誤り訂正符号を復号化する方法及び装置 | |
| Yathiraj et al. | Implementation of BCH code (n, k) encoder and decoder for multiple error correction control | |
| JP3260095B2 (ja) | 誤り訂正符号及び誤り検出符号の復号器並びにその復号方法 | |
| JP3306413B2 (ja) | 誤り訂正装置および誤り訂正方法 | |
| JPH08293802A (ja) | インターリーブ式誤り訂正方法 | |
| JPH06204893A (ja) | 符号化方法および装置 | |
| EP0674395A2 (en) | Error correction code encoding device and error correction code encoding method | |
| JPS60170330A (ja) | 復号化システム | |
| JPH08509351A (ja) | セミサイクリックコードに基づく誤り補正可能データ伝送方法及び装置 | |
| CN101447234B (zh) | 存储器模块及其写入及读取方法 | |
| JPH0365698B2 (ja) | ||
| JP2609475B2 (ja) | 誤り訂正符号の符号器および復号器ならびにこの復合器を用いた復号方法 | |
| Key | Some error-correcting codes and their applications | |
| JP2863726B2 (ja) | 符号化伝送方式 | |
| JP2000236265A (ja) | 疑似積符号復号装置及び方法 | |
| JPH0361210B2 (ja) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |