JPH0221180B2 - - Google Patents
Info
- Publication number
- JPH0221180B2 JPH0221180B2 JP60089149A JP8914985A JPH0221180B2 JP H0221180 B2 JPH0221180 B2 JP H0221180B2 JP 60089149 A JP60089149 A JP 60089149A JP 8914985 A JP8914985 A JP 8914985A JP H0221180 B2 JPH0221180 B2 JP H0221180B2
- Authority
- JP
- Japan
- Prior art keywords
- gate
- exclusive
- input
- stage
- stages
- 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.)
- Expired - Lifetime
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/17—Burst error correction, e.g. error trapping, Fire codes
Landscapes
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Error Detection And Correction (AREA)
Description
【発明の詳細な説明】
産業上の利用分野
本発明は、ｉ桁だけ短縮されたｎ桁の巡回ブロ
ツクコードで最大ｂ桁のバーストエラーを「エラ
ートラツピング」法によつて訂正する装置に関す
る。ここで、巡回ブロツクコードは、ｒ桁の検査
部分とｋ桁の情報部分から成つている。またこの
装置には、ｒ個の段を有するシンドローム・レジ
スタが設けられ、訂正装置全体の入力側が前記ｒ
個の段の間に配置された少くとも１つの排他的論
理和ゲートと接続され、この排他的論理和ゲート
を配置する位置が事前乗算多項式の係数から導出
される。またシンドローム・レジスタの最終段の
出力側が第１のスイツチを介して第１段の入力側
と接続され、かつ前記ｒ個の段の間に配置された
別の排他的論理和ゲートを介してシンドローム・
レジスタの別の段と接続され、別の排他的論理和
ゲートの配置位置がコードの生成多項式によつて
決定される。またｒ−ｂ個の段を有するゼロ検出
装置が設けられ、このゼロ検出装置はシンドロー
ム・レジスタの複数の段に接続されている。また
ｎ個の段を有するバツフアメモリが設けられ、こ
のバツフアメモリは装置全体の入力側と接続され
ている。また、さらにべつの排他的論理和ゲート
が設けられ、この排他的論理和ゲートの１つの入
力側がバツフアメモリの出力側と接続され、他の
入力側が第２のスイツチを介してシンドローム・
レジスタの出力側と接続されまた前記排他的論理
和ゲートの出力側は装置全体の出力側と接続され
ている。また装置全体の入力側に加わる同期信号
によつてすべてのスイツチを同期制御するシーケ
ンス制御部が設けられ、さらに入力側に加わる受
信信号のビツトクロツクと同期したクロツク供給
装置が設けられている。
ツクコードで最大ｂ桁のバーストエラーを「エラ
ートラツピング」法によつて訂正する装置に関す
る。ここで、巡回ブロツクコードは、ｒ桁の検査
部分とｋ桁の情報部分から成つている。またこの
装置には、ｒ個の段を有するシンドローム・レジ
スタが設けられ、訂正装置全体の入力側が前記ｒ
個の段の間に配置された少くとも１つの排他的論
理和ゲートと接続され、この排他的論理和ゲート
を配置する位置が事前乗算多項式の係数から導出
される。またシンドローム・レジスタの最終段の
出力側が第１のスイツチを介して第１段の入力側
と接続され、かつ前記ｒ個の段の間に配置された
別の排他的論理和ゲートを介してシンドローム・
レジスタの別の段と接続され、別の排他的論理和
ゲートの配置位置がコードの生成多項式によつて
決定される。またｒ−ｂ個の段を有するゼロ検出
装置が設けられ、このゼロ検出装置はシンドロー
ム・レジスタの複数の段に接続されている。また
ｎ個の段を有するバツフアメモリが設けられ、こ
のバツフアメモリは装置全体の入力側と接続され
ている。また、さらにべつの排他的論理和ゲート
が設けられ、この排他的論理和ゲートの１つの入
力側がバツフアメモリの出力側と接続され、他の
入力側が第２のスイツチを介してシンドローム・
レジスタの出力側と接続されまた前記排他的論理
和ゲートの出力側は装置全体の出力側と接続され
ている。また装置全体の入力側に加わる同期信号
によつてすべてのスイツチを同期制御するシーケ
ンス制御部が設けられ、さらに入力側に加わる受
信信号のビツトクロツクと同期したクロツク供給
装置が設けられている。
従来技術
このような装置は、「エラー訂正コード」
（Error Correcting Codes）ダブリユウ、ウエズ
リイ・パターソン、イ・ゼ、ウエルドン・ジユニ
ア（W.Wesley Peterson，E.J.Weldon，Jr.）
著、MIT出版、マサチユーセツツ州ケンブリツ
ジ、1972年第364〜370頁により公知である。
（Error Correcting Codes）ダブリユウ、ウエズ
リイ・パターソン、イ・ゼ、ウエルドン・ジユニ
ア（W.Wesley Peterson，E.J.Weldon，Jr.）
著、MIT出版、マサチユーセツツ州ケンブリツ
ジ、1972年第364〜370頁により公知である。
巡回ブロツクコードで長さｂのバーストエラー
を訂正する場合には、いわゆる「エラートラツピ
ング（Error−Trapping）法が普通の訂正方法と
して用いられる。巡回ブロツクコードは、その生
成多項式ｇ（ｘ）によつて表わされる。
を訂正する場合には、いわゆる「エラートラツピ
ング（Error−Trapping）法が普通の訂正方法と
して用いられる。巡回ブロツクコードは、その生
成多項式ｇ（ｘ）によつて表わされる。
送信側では、ｒ段のシンドローム・レジスタに
よつて情報部分に検査部分が付加される。従つ
て、数学的に２進係数を有する多項式として表わ
されるコード語が発生する。このコード語の伝送
時に誤りが生ずることがある。コード語は受信側
においてｖ（ｘ）で表わされる。
よつて情報部分に検査部分が付加される。従つ
て、数学的に２進係数を有する多項式として表わ
されるコード語が発生する。このコード語の伝送
時に誤りが生ずることがある。コード語は受信側
においてｖ（ｘ）で表わされる。
受信側では、ｒ段のシンドローム・レジスタに
よつて復号が行なわれる。受信コード語の入力
後、エラーが無い場合にはシンドローム・レジス
タは０のみを有する。エラーが存在する場合は、
シンドローム・レジスタに１が現われる。コード
語が入力した後のシンドローム・レジスタにおけ
るビツトパターンは、シンドロームと呼ばれる。
よつて復号が行なわれる。受信コード語の入力
後、エラーが無い場合にはシンドローム・レジス
タは０のみを有する。エラーが存在する場合は、
シンドローム・レジスタに１が現われる。コード
語が入力した後のシンドローム・レジスタにおけ
るビツトパターンは、シンドロームと呼ばれる。
通常、復号が終つた後すぐにエラーの訂正を行
なうために、ｎ桁の多項式として表わされる受信
コード語ｖ（ｘ）は多項式xrと自動的に事前に乗
算される。回路的に言えば、シンドローム・レジ
スタの最終段の後で受信コード語が排他的論理和
ゲートを介して入力する。入力が終了した後でエ
ラー訂正が始まる。そのためにシンドローム・レ
ジスタの内容は、最初のｒ−ｂ段の内容が０だけ
になるまで、閉帰還ループの中を巡回する。ｒ−
ｂ段の内容が０だけになると、最後のｂ段はエラ
ーパターンを有する。
なうために、ｎ桁の多項式として表わされる受信
コード語ｖ（ｘ）は多項式xrと自動的に事前に乗
算される。回路的に言えば、シンドローム・レジ
スタの最終段の後で受信コード語が排他的論理和
ゲートを介して入力する。入力が終了した後でエ
ラー訂正が始まる。そのためにシンドローム・レ
ジスタの内容は、最初のｒ−ｂ段の内容が０だけ
になるまで、閉帰還ループの中を巡回する。ｒ−
ｂ段の内容が０だけになると、最後のｂ段はエラ
ーパターンを有する。
ブロツクコードをibitだけ短縮するには、各コ
ード語の情報部分の最初のｉビツトを０にセツト
し、符号化した後で除去する。復号時には、短縮
されたコード語にｉ個の０を付加する。ただし、
受信コード語を多項式xiと付加的に乗算すれば、
０の付加は避けられる。つまり短縮形ブロツクコ
ードにおいては、多項式p1（ｘ）と乗算された受
信コード語ｖ（ｘ）の多項式のシンドロームを算
出できるのである。この事前乗算を実施するに
は、事前乗算多項式p1（ｘ）を算出しなければな
らない。事前乗算多項式p1（ｘ）は多項式xr+iを
生成多項式ｇ（ｘ）で除算した時の商の余りであ
り、次式で表わされる。
ード語の情報部分の最初のｉビツトを０にセツト
し、符号化した後で除去する。復号時には、短縮
されたコード語にｉ個の０を付加する。ただし、
受信コード語を多項式xiと付加的に乗算すれば、
０の付加は避けられる。つまり短縮形ブロツクコ
ードにおいては、多項式p1（ｘ）と乗算された受
信コード語ｖ（ｘ）の多項式のシンドロームを算
出できるのである。この事前乗算を実施するに
は、事前乗算多項式p1（ｘ）を算出しなければな
らない。事前乗算多項式p1（ｘ）は多項式xr+iを
生成多項式ｇ（ｘ）で除算した時の商の余りであ
り、次式で表わされる。
p1（ｘ）＝Ｒ｛xr+i÷ｇ（ｘ）｝
ただしＲは剰余を表わす記号である。
p1（ｘ）の係数は、排他的論理和ゲートを介し
てシンドローム・レジスタへ入力する受信コード
語の桁を決定する。
てシンドローム・レジスタへ入力する受信コード
語の桁を決定する。
発明の解決すべき問題点
公知の短縮形ブロツクコード用訂正装置では、
数ビツトしか短縮しない場合でも、非短縮コード
用の訂正装置に比べて付加的な排他的論理和ゲー
トを多数必要とする。
数ビツトしか短縮しない場合でも、非短縮コード
用の訂正装置に比べて付加的な排他的論理和ゲー
トを多数必要とする。
本発明の課題は、従来のものに比べて少数の排
他的論理和ゲートしか必要としない短縮形ブロツ
クコード用訂正装置を提供することである。
他的論理和ゲートしか必要としない短縮形ブロツ
クコード用訂正装置を提供することである。
発明の解決するための手段
本発明によればこの課題は、冒頭に記載した訂
正装置を基礎にして次のように解決される。すな
わち、装置全体の入力側が、シンドローム・レジ
スタの段の間に配置された少くとも１つの排他的
論理和ゲートを介してシンドローム・レジスタと
接続され、前記排他的論理和ゲートの配置される
位置が事前乗算多項式p2（ｘ）の係数から導出さ
れ、事前乗算多項式p2（ｘ）は、多項式xb+iを生
成多項式ｇ（ｘ）で除算した時の商の余りとして
発生し、ゼロ検出装置がシンドローム・レジスタ
の後方のｒ−ｂ段と接続され、シンドローム・レ
ジスタの出力側が第ｂ段の後に設けられているよ
うにするのである。
正装置を基礎にして次のように解決される。すな
わち、装置全体の入力側が、シンドローム・レジ
スタの段の間に配置された少くとも１つの排他的
論理和ゲートを介してシンドローム・レジスタと
接続され、前記排他的論理和ゲートの配置される
位置が事前乗算多項式p2（ｘ）の係数から導出さ
れ、事前乗算多項式p2（ｘ）は、多項式xb+iを生
成多項式ｇ（ｘ）で除算した時の商の余りとして
発生し、ゼロ検出装置がシンドローム・レジスタ
の後方のｒ−ｂ段と接続され、シンドローム・レ
ジスタの出力側が第ｂ段の後に設けられているよ
うにするのである。
本発明の実施例によれば、ゼロ検出装置とし
て、ｒ−ｂ個の入力側を有するNORゲートを設
けると有利である。
て、ｒ−ｂ個の入力側を有するNORゲートを設
けると有利である。
また別の実施例は、次のように構成すると有利
である。すなわち、シーケンス制御部にANDゲ
ートを設け、このANDゲートの１つの入力側を
ゼロ検出装置の出力側と接続し、もう１つの入力
側を自由にアドレス指定可能な固定メモリの出力
側と接続し、この固定メモリの複数の入力側を２
進カウンタの複数の出力側と接続し、またシーケ
ンス制御部の中に４段シフトレジスタを設け、こ
のシフトレジスタの入力側および各段の出力側を
ORゲートの複数の入力側と接続し、このORゲ
ートの出力側を介して第２のスイツチを直接に制
御し、インバータを介して第１のスイツチを制御
するのである。
である。すなわち、シーケンス制御部にANDゲ
ートを設け、このANDゲートの１つの入力側を
ゼロ検出装置の出力側と接続し、もう１つの入力
側を自由にアドレス指定可能な固定メモリの出力
側と接続し、この固定メモリの複数の入力側を２
進カウンタの複数の出力側と接続し、またシーケ
ンス制御部の中に４段シフトレジスタを設け、こ
のシフトレジスタの入力側および各段の出力側を
ORゲートの複数の入力側と接続し、このORゲ
ートの出力側を介して第２のスイツチを直接に制
御し、インバータを介して第１のスイツチを制御
するのである。
本発明による装置は、バーストエラー長をｂ＝
１にセツトすれば、単一エラー訂正能力を有する
巡回ブロツクコードの訂正にも使用できる。
１にセツトすれば、単一エラー訂正能力を有する
巡回ブロツクコードの訂正にも使用できる。
実施例
次に、図面を参照しながら実施例について本発
明を詳しく説明する。
明を詳しく説明する。
第１図は本発明によるエラーバースト訂正装置
の実施例を示している。この装置には、シンドロ
ーム・レジスタ１５、出力側３１を有するゼロ検
出装置２４、出力側３２，３３を有するシーケン
ス制御部２５、バツフアメモリ２６、スイツチ２
７、排他的論理和ゲート２８、装置全体の入力側
１６、シーケンス制御部のリセツト入力側１７、
装置全体の出力側２９、およびクロツク入力側３
０を有している。
の実施例を示している。この装置には、シンドロ
ーム・レジスタ１５、出力側３１を有するゼロ検
出装置２４、出力側３２，３３を有するシーケン
ス制御部２５、バツフアメモリ２６、スイツチ２
７、排他的論理和ゲート２８、装置全体の入力側
１６、シーケンス制御部のリセツト入力側１７、
装置全体の出力側２９、およびクロツク入力側３
０を有している。
シンドローム・レジスタ１５は、ｒ＝ｎ−ｋ段
のシフトレジスタを有している。ここで、ｎはブ
ロツクコードビツト長、ｋは情報部分のビツト
長、ｒは検査部分のビツト長である。シンドロー
ム・レジスタの最後の段の出力側は、スイツチ２
３を介して先行する各段の入力側と結合されてい
る。入力側１６は排他的論理和ゲート１８を介し
てシンドローム・レジスタ１５と接続されてい
る。シンドローム・レジスタの出力側はスイツチ
２７と接続されている。
のシフトレジスタを有している。ここで、ｎはブ
ロツクコードビツト長、ｋは情報部分のビツト
長、ｒは検査部分のビツト長である。シンドロー
ム・レジスタの最後の段の出力側は、スイツチ２
３を介して先行する各段の入力側と結合されてい
る。入力側１６は排他的論理和ゲート１８を介し
てシンドローム・レジスタ１５と接続されてい
る。シンドローム・レジスタの出力側はスイツチ
２７と接続されている。
スイツチ２３，２７はゲートとして構成でき
る。
る。
なお第１図〜第３図において対応する部分に同
一参照番号が付けられている。
一参照番号が付けられている。
次に、第１図に示す訂正回路の動作について説
明する。この場合、入力信号が誤つているものと
する； 入力側１６にはｎ桁のコード語が入力される。
従つてこのコード語は、その入力前にゼロにセツ
トされたシンドローム・レジスタ１５およびバツ
フアメモリ２６に入力される。シンドローム・レ
ジスタ１５の内容は、すべてのコード語が入力す
るまで帰還ループ内を巡回する。いま入力側１６
を介してｎ個の０信号が連続して入力すると、ゼ
ロ検出装置２４が第（ｂ＋１）段〜第ｒ段の中に
０のみを検出するようになるまで、シンドロー
ム・レジスタ１５の内容はレジスタの中を巡回す
る。続いて、シーケンス制御部２５を介してスイ
ツチ２３が開放され、スイツチ２７が閉成され
る。この時第ｂ段の後にあるシンドローム・レジ
スタ１５の出力側から、エラーバーストを有する
ｂ段の内容が、スイツチ２７を介して排他的論理
和ゲート２８へ供給される。ゲート２８では、コ
ード語のエラー部分がバツフアメモリ２６から読
出されたビツトによつて訂正される。
明する。この場合、入力信号が誤つているものと
する； 入力側１６にはｎ桁のコード語が入力される。
従つてこのコード語は、その入力前にゼロにセツ
トされたシンドローム・レジスタ１５およびバツ
フアメモリ２６に入力される。シンドローム・レ
ジスタ１５の内容は、すべてのコード語が入力す
るまで帰還ループ内を巡回する。いま入力側１６
を介してｎ個の０信号が連続して入力すると、ゼ
ロ検出装置２４が第（ｂ＋１）段〜第ｒ段の中に
０のみを検出するようになるまで、シンドロー
ム・レジスタ１５の内容はレジスタの中を巡回す
る。続いて、シーケンス制御部２５を介してスイ
ツチ２３が開放され、スイツチ２７が閉成され
る。この時第ｂ段の後にあるシンドローム・レジ
スタ１５の出力側から、エラーバーストを有する
ｂ段の内容が、スイツチ２７を介して排他的論理
和ゲート２８へ供給される。ゲート２８では、コ
ード語のエラー部分がバツフアメモリ２６から読
出されたビツトによつて訂正される。
訂正期間の間にｋ回のシフトを行つてもゼロ検
出装置２４が応答しない場合、訂正不可能なエラ
ーが存在するか検査部分にエラーがある。この場
合、ｎ回目のシフトの後でシンドローム・レジス
タ１５はゼロにセツトされ、次のコード語が入力
される。検査期間をｎクロツク周期に延長するこ
とによつて検査部分におけるエラーも訂正でき
る。情報部分におけるエラーのみを訂正する場合
バツフアレジスタはｋ個の段で十分である。
出装置２４が応答しない場合、訂正不可能なエラ
ーが存在するか検査部分にエラーがある。この場
合、ｎ回目のシフトの後でシンドローム・レジス
タ１５はゼロにセツトされ、次のコード語が入力
される。検査期間をｎクロツク周期に延長するこ
とによつて検査部分におけるエラーも訂正でき
る。情報部分におけるエラーのみを訂正する場合
バツフアレジスタはｋ個の段で十分である。
訂正不可能なエラーが存在するのは、エラーバ
ーストがｂより長い場合、または１つのコード語
に複数のエラーバーストが生じる場合である。
ーストがｂより長い場合、または１つのコード語
に複数のエラーバーストが生じる場合である。
コード語が直接に連続して伝送される場合、つ
まりレジスタ１５およびバツフアメモリ２６のシ
フトクロツクが入力コード語のビツトクロツクに
等しい場合には、交互に動作する２つのシンドロ
ーム・レジスタが必要になる。
まりレジスタ１５およびバツフアメモリ２６のシ
フトクロツクが入力コード語のビツトクロツクに
等しい場合には、交互に動作する２つのシンドロ
ーム・レジスタが必要になる。
リセツト入力側１７に加わるリセツト信号は、
入力側１６に加わるコード語から何らかの形で派
生して導出することができる。
入力側１６に加わるコード語から何らかの形で派
生して導出することができる。
第２図はｉ＝4bitだけ短縮された、生成多項式
ｇ（ｘ）＝x14＋x11＋x9＋x5＋x2＋x0を有するフア
イヤコード２７９，２６５に対するシンドロー
ム・レジスタ１５ａを有している。なおこの生成
多項式のバーストエラー訂正能力はｂ＝５であ
る。このフアイヤコード全体のビツト長はｎ＝
279、情報部分のビツト長はｋ＝265なので検査部
分の長さはｒ＝14である。従つてシンドローム・
レジスタ１５ａは14個の段を有している。
ｇ（ｘ）＝x14＋x11＋x9＋x5＋x2＋x0を有するフア
イヤコード２７９，２６５に対するシンドロー
ム・レジスタ１５ａを有している。なおこの生成
多項式のバーストエラー訂正能力はｂ＝５であ
る。このフアイヤコード全体のビツト長はｎ＝
279、情報部分のビツト長はｋ＝265なので検査部
分の長さはｒ＝14である。従つてシンドローム・
レジスタ１５ａは14個の段を有している。
生成多項式ｇ（ｘ）の指数に相応して、第14段
の出力側が第１段の入力側および第２，５，９，
11段の後へ帰還結合される。この帰還結合は排他
的論理和ゲート１９〜２２に作用する。
の出力側が第１段の入力側および第２，５，９，
11段の後へ帰還結合される。この帰還結合は排他
的論理和ゲート１９〜２２に作用する。
コード短縮のための事前乗算多項式は次式で表
わされる。
わされる。
p2（ｘ）＝Ｒ｛xb+1÷ｇ（ｘ）｝＝x9
ただしＲは剰余を表わす記号である。
従つて入力側１６は、第９段の後でシンドロー
ム・レジスタ１５ａに接続される。ここでの入力
結合は排他的論理和ゲート１８を介して行なわれ
る。また、ｂ＝５だけコードが短縮されているの
で、シンドローム・レジスタの出力側は第５段の
後に置かれる。
ム・レジスタ１５ａに接続される。ここでの入力
結合は排他的論理和ゲート１８を介して行なわれ
る。また、ｂ＝５だけコードが短縮されているの
で、シンドローム・レジスタの出力側は第５段の
後に置かれる。
入力側１６を出力側第５段に接続したとすれ
ば、コードの短縮は行われない。入力側１６をそ
れぞれ１段後に設けることにより、コードがビツ
ト毎に短縮される、最終段（ｂ＝14）の後では、
短縮は９ビツトになる。この９ビツトまでの短縮
であれば、排他的論理和ゲート１８は１つしか必
要としない。それよりも大きな短縮を行う場合に
初めて、入力側に対する排他的論理和ゲートの数
を増さなければならない。
ば、コードの短縮は行われない。入力側１６をそ
れぞれ１段後に設けることにより、コードがビツ
ト毎に短縮される、最終段（ｂ＝14）の後では、
短縮は９ビツトになる。この９ビツトまでの短縮
であれば、排他的論理和ゲート１８は１つしか必
要としない。それよりも大きな短縮を行う場合に
初めて、入力側に対する排他的論理和ゲートの数
を増さなければならない。
第３図は、第２図に示したフアイヤコード２７
５，２６１用シンドローム・レジスタのシーケン
ス制御部２５ａの実施例である。シーケンス制御
部には次のような素子が設けられている。10段の
２進カウンタ３４、リセツト入力側１７、1024個
の記憶場所と10個のアドレス入力側と出力側３６
とを有するアドレス指定可能な固定メモリ
（ROM）３５、ANDゲート３７、直列入力側お
よび並列出力側を有する４段のシフトレジスタ３
８、５つの入力側を有するORゲート３９、イン
バータ４０、クロツク入力側３０、入力側３１、
２つの出力側３１ａ，３３ａである。端子３２，
３３と出力側３２ａ，３３ａとの間には電気機械
スイツチ（例えばリレー）が配置される。スイツ
チ２３，２７はゲートで置換えてもよい。
５，２６１用シンドローム・レジスタのシーケン
ス制御部２５ａの実施例である。シーケンス制御
部には次のような素子が設けられている。10段の
２進カウンタ３４、リセツト入力側１７、1024個
の記憶場所と10個のアドレス入力側と出力側３６
とを有するアドレス指定可能な固定メモリ
（ROM）３５、ANDゲート３７、直列入力側お
よび並列出力側を有する４段のシフトレジスタ３
８、５つの入力側を有するORゲート３９、イン
バータ４０、クロツク入力側３０、入力側３１、
２つの出力側３１ａ，３３ａである。端子３２，
３３と出力側３２ａ，３３ａとの間には電気機械
スイツチ（例えばリレー）が配置される。スイツ
チ２３，２７はゲートで置換えてもよい。
自由にアドレス指定可能な固定メモリROM３
５の代わりに、ゲートとフリツプフロツプから成
る相応の回路を使用してもよい。
５の代わりに、ゲートとフリツプフロツプから成
る相応の回路を使用してもよい。
第３図のシーケンス制御部２５ａは次のように
動作する。
動作する。
コード語が入力側１６に入力する前に２進カウ
ンタ３４はリセツトされる。コード語が入力して
いる間、２進カウンタ３４により制御される
ROM３５は０だけを出力し、従つて復号プロセ
スの間ANDゲート３７は阻止される。これに対
して後続の261クロツク周期だけ持続する訂正期
間の間、ROM３５が１のみを出力するのでAND
ゲート３７は開放される。訂正期間の間ゼロ検出
装置２４がその入力側で０のみを検出すると、そ
の出力側３１には１つのパルスが発生する。この
パルスはANDゲート３７を介してシフトレジス
タ３８に達する。その時ORゲート３９の出力側
３３ａには、５クロツク周期だけ遅延したパルス
が現われる。このパルスはスイツチ２７を５クロ
ツク周期だけ閉成するので、排他的論理和ゲート
２８に訂正信号が達する。同時に、遅延したパル
スはインバータ４０によつて反転され、出力側３
２ａに現われる反転パルスによつてスイツチ２３
が開放される。
ンタ３４はリセツトされる。コード語が入力して
いる間、２進カウンタ３４により制御される
ROM３５は０だけを出力し、従つて復号プロセ
スの間ANDゲート３７は阻止される。これに対
して後続の261クロツク周期だけ持続する訂正期
間の間、ROM３５が１のみを出力するのでAND
ゲート３７は開放される。訂正期間の間ゼロ検出
装置２４がその入力側で０のみを検出すると、そ
の出力側３１には１つのパルスが発生する。この
パルスはANDゲート３７を介してシフトレジス
タ３８に達する。その時ORゲート３９の出力側
３３ａには、５クロツク周期だけ遅延したパルス
が現われる。このパルスはスイツチ２７を５クロ
ツク周期だけ閉成するので、排他的論理和ゲート
２８に訂正信号が達する。同時に、遅延したパル
スはインバータ４０によつて反転され、出力側３
２ａに現われる反転パルスによつてスイツチ２３
が開放される。
発明の効果
本発明のバーストエラー訂正装置によれば、従
来のものに比べて必要な排他的論理和ゲートの数
を少くできる。
来のものに比べて必要な排他的論理和ゲートの数
を少くできる。
第１図は本発明による訂正装置の実施例を示す
ブロツク図、第２図は4bitだけ短縮されたフアイ
ヤコード２７９，２６５のためのシンドローム・
レジスタとゼロ検出装置のブロツク図、第３図は
このフアイヤコードのためのシーケンス制御部の
ブロツク図である。 １５，１５ａ……シンドローム・レジスタ、１
６……入力側、１７……リセツト入力側、１８，
１９〜２２，２８……排他的論理和ゲート、２
３，２７……スイツチ、２４……ゼロ検出装置、
２５，２５ａ……シーケンス制御部、２６……バ
ツフアメモリ、２９……出力側、３４……２進カ
ウンタ、３５……固定メモリ、３８……シフトレ
ジスタ、３９……ORゲート、４０……インバー
タ。
ブロツク図、第２図は4bitだけ短縮されたフアイ
ヤコード２７９，２６５のためのシンドローム・
レジスタとゼロ検出装置のブロツク図、第３図は
このフアイヤコードのためのシーケンス制御部の
ブロツク図である。 １５，１５ａ……シンドローム・レジスタ、１
６……入力側、１７……リセツト入力側、１８，
１９〜２２，２８……排他的論理和ゲート、２
３，２７……スイツチ、２４……ゼロ検出装置、
２５，２５ａ……シーケンス制御部、２６……バ
ツフアメモリ、２９……出力側、３４……２進カ
ウンタ、３５……固定メモリ、３８……シフトレ
ジスタ、３９……ORゲート、４０……インバー
タ。
Claims (1)
- 【特許請求の範囲】 １ ｉ桁だけ短縮されたｎ桁の巡回ブロツクコー
ドで最大ｂ桁のバーストエラーを「エラートラツ
ピング」法によつて訂正する装置であつて、巡回
ブロツクコードがｒ桁の検査部分とｋ桁の情報部
分から成り、 ｒ個の段１〜１４を有するシンドローム・レジ
スタ１５，１５ａが設けられ、訂正装置全体の入
力側１６が前記ｒ個の段１〜１４の間に配置され
た少くとも１つの排他的論理和ゲート１８と接続
され、該排他的論理和ゲートを配置する位置が事
前乗算多項式の係数から導出され、またシンドロ
ーム・レジスタ１５の最終段１４の出力側が第１
のスイツチ２３を介して第１段１の入力側と接続
され、かつ前記ｒ個の段１〜１４の間に配置され
た別の排他的論理和ゲート１９〜２２を介してシ
ンドローム・レジスタ１５の別の段と接続され、
別の排他的論理和ゲート１９〜２２の配置位置が
コードの生成多項式から導出され、 ｒ−ｂ個の段を有するゼロ検出装置２４が設け
られ、該ゼロ検出装置はシンドローム・レジスタ
１５，１５ａの複数の段に接続され、 ｎ個の段を有するバツフアメモリ２６が設けら
れ、該バツフアメモリは装置全体の入力側１６と
接続され、 さらにべつの排他的論理和ゲート２８が設けら
れ、該排他的論理和ゲートの１つの入力側がバツ
フアメモリ２６の出力側と接続され、他の入力側
が第２のスイツチ２７を介してシンドローム・レ
ジスタ１５，１５ａの出力側と接続され、また前
記排他的論理和ゲート２８の出力側が装置全体の
出力側２９と接続され、 装置全体の入力側１６加わる同期信号によつて
すべてのスイツチ２３，２７を同期制御するシー
ケンス制御部２５が設けられ、 入力側１６に加わる受信信号のビツトクロツク
と同期したクロツク供給装置３０が設けられてい
る、 短縮形巡回ブロツクコードにおけるエラーバー
ストを訂正する装置において、 装置全体の入力側１６が、シンドローム・レジ
スタ１５，１５ａの段１〜１４の間に配置された
少くとも１つの排他的論理和ゲート１８を介して
シンドローム・レジスタ１５ａと接続され、前記
排他的論理和ゲート１８の配置される位置が事前
乗算多項式P2（ｘ）の係数から導出され、事前乗
算多項式P2（ｘ）は、多項式xb+iを生成多項式ｇ
（ｘ）で除算した時の商の余りとして発生し、 ゼロ検出装置２４がシンドローム・レジスタ１
５，１５ａの後方のｒ−ｂ段６〜１４と接続さ
れ、 シンドローム・レジスタ１５，１５ａの出力側
が第ｂ段５の後に設けられている、ことを特徴す
る短縮形巡回ブロツクコードにおけるバーストエ
ラーを訂正する装置。 ２ ゼロ検出装置として、ｒ−ｂ個の入力側を有
するNORゲート２４が設けられている特許請求
の範囲第１項記載の短縮形巡回ブロツクコードに
おけるエラーバーストを訂正する装置。 ３ シーケンス制御部２５にANDゲート３７が
設けられ、該ANDゲートの１つの入力側がゼロ
検出装置２４の出力側３１と接続され、もう１つ
の入力側が自由にアドレス指定可能な固定メモリ
３５の出力側３６と接続され、該固定メモリの複
数の入力側が２進カウンタ３４の複数の出力側と
接続され、 またシーケンス制御部２５の中に４段シフトレ
ジスタ３８も設けられ、該シフトレジスタの入力
側および各段の出力側がORゲート３９の複数の
入力側と接続され、該ORゲートの出力側３３ａ
を介して第２のスイツチ２７が直接に制御され、
インバータ４０を介して第１のスイツチ２３が制
御される、特許請求の範囲第１項記載の短縮形巡
回ブロツクコードにおけるエラーバーストを訂正
する装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| DE3415765 | 1984-04-27 | ||
| DE3415765.4 | 1984-04-27 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS617729A JPS617729A (ja) | 1986-01-14 |
| JPH0221180B2 true JPH0221180B2 (ja) | 1990-05-14 |
Family
ID=6234539
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60089149A Granted JPS617729A (ja) | 1984-04-27 | 1985-04-26 | 短縮形巡回ブロツクコ−ドにおけるエラ−バ−ストを訂正する装置 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US4698813A (ja) |
| EP (1) | EP0159403A3 (ja) |
| JP (1) | JPS617729A (ja) |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2597987B2 (ja) * | 1986-02-08 | 1997-04-09 | ソニー株式会社 | ブロツク化伝送信号のデコード装置 |
| EP0254140B1 (de) * | 1986-07-21 | 1991-04-17 | Siemens Aktiengesellschaft | Verfahren zum Bilden von Datenblocksicherungsinformationen für serielle Datenbitfolgen mittels zyklischer Binärcodes |
| US4916702A (en) * | 1988-06-17 | 1990-04-10 | Cyclotomics, Inc. | Elongated burst trapping |
| US5381423A (en) * | 1989-07-25 | 1995-01-10 | Italtel Societa Italiana Telecomunicazioni S.P.A. | Process and device for the decoding of a shortened, cyclic binary code using error correction |
| US4978955A (en) * | 1989-11-09 | 1990-12-18 | Archive Corporation | Data randomizing/de-randomizing circuit for randomizing and de-randomizing data |
| US5107506A (en) * | 1990-01-25 | 1992-04-21 | Digital Equipment Corporation | Error trapping decoding method and apparatus |
| EP0611054B1 (en) * | 1993-01-22 | 1998-04-08 | Canon Kabushiki Kaisha | Polynomial-set deriving apparatus and method |
| US5473620A (en) * | 1993-09-21 | 1995-12-05 | Cirrus Logic, Inc. | Programmable redundancy/syndrome generator |
| US5936978A (en) * | 1996-12-05 | 1999-08-10 | Telefonaktiebolaget L M Ericsson (Publ) | Shortened fire code error-trapping decoding method and apparatus |
| WO1998026508A1 (de) * | 1996-12-12 | 1998-06-18 | Siemens Schweiz Ag | Verfahren und schaltungsanordnung zur decodierung eines zyklisch codierten signals |
| US7155656B1 (en) * | 2003-05-01 | 2006-12-26 | Hellosoft Inc. | Method and system for decoding of binary shortened cyclic code |
| RU2251210C1 (ru) * | 2003-10-06 | 2005-04-27 | Федеральное государственное унитарное предприятие "Калужский научно-исследовательский институт телемеханических устройств" | Кодек помехоустойчивого циклического кода |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3542756A (en) * | 1968-02-07 | 1970-11-24 | Codex Corp | Error correcting |
| US3801955A (en) * | 1971-12-13 | 1974-04-02 | Honeywell Inf Systems | Cyclic code encoder/decoder |
| US4059825A (en) * | 1976-10-12 | 1977-11-22 | Greene Edward P | Burst/slip correction decoder and method |
| EP0004718A1 (en) * | 1978-03-31 | 1979-10-17 | British Broadcasting Corporation | Method of and apparatus for decoding shortened cyclic block codes |
| JPS5546665A (en) * | 1978-09-30 | 1980-04-01 | Matsushita Electric Ind Co Ltd | Error corrector |
| DE3032468C2 (de) * | 1980-08-28 | 1986-01-23 | Siemens AG, 1000 Berlin und 8000 München | Schaltungsanordnung zur Erkennung des Musters von Fehlerbündeln |
| US4488302A (en) * | 1983-02-11 | 1984-12-11 | At&T Bell Laboratories | Burst error correction using cyclic block codes |
-
1984
- 1984-12-17 EP EP84115564A patent/EP0159403A3/de not_active Ceased
-
1985
- 1985-04-26 JP JP60089149A patent/JPS617729A/ja active Granted
- 1985-04-29 US US06/728,048 patent/US4698813A/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPS617729A (ja) | 1986-01-14 |
| EP0159403A2 (de) | 1985-10-30 |
| EP0159403A3 (de) | 1987-11-11 |
| US4698813A (en) | 1987-10-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US3805232A (en) | Encoder/decoder for code words of variable length | |
| US4584686A (en) | Reed-Solomon error correction apparatus | |
| CA1295744C (en) | Error correction method using reed-solomon code | |
| EP0280013B1 (en) | Device for verifying proper operation of a checking code generator | |
| US5748652A (en) | Apparatus for detecting and correcting cyclic redundancy check errors | |
| US5420873A (en) | Apparatus for decoding BCH code for correcting complex error | |
| JPH0221180B2 (ja) | ||
| US3452328A (en) | Error correction device for parallel data transmission system | |
| JPH0728227B2 (ja) | Ｂｃｈ符号の復号装置 | |
| US4994993A (en) | System for detecting and correcting errors generated by arithmetic logic units | |
| JP2009094605A (ja) | 符号誤り検出装置および誤り検出符号生成装置 | |
| JPS632370B2 (ja) | ||
| US5408476A (en) | One bit error correction method having actual data reproduction function | |
| US4791485A (en) | System for detecting a transmission error | |
| JPH03219725A (ja) | 誤り検査コード生成装置および伝送誤り検出装置 | |
| US4453249A (en) | System for binary data transmission | |
| CA1109160A (en) | Verifying circuit operation | |
| US3671947A (en) | Error correcting decoder | |
| US5003540A (en) | Error correction coding and decoding circuit for digitally coded information | |
| US3487361A (en) | Burst error correction system | |
| JPH0738626B2 (ja) | ワード同期検出回路 | |
| JP3131969B2 (ja) | 演算装置 | |
| SE512145C2 (sv) | Anordning för korrigering av skur- och slumpfel | |
| SU1083237A2 (ru) | Запоминающее устройство с исправлением ошибок | |
| KR100201839B1 (ko) | 병렬 순회 리던던시 코드 인코더 및 디코더 |