JPS5949618B2 - 巡回ブロック符号のための直列エンコ−ダ - Google Patents

Description

【発明の詳細な説明】 発明の背景 １、発明の分野 本発明は、一般にＢｏｓｅＣｈａｕｄｈｕｒｉＨｏｃ一
ｑｕｅｎｇｈｅｍ（ＢＣＨ）形の巡回ブロツク符号のた
めのエンコーダに関し、特に単一誤り訂正機能を持つた
直列エンコーダに関する。

２．従来技術の説明 ＢＣＨ形のエンコーダ及びデコーダに関する ！ほとん
どの従来技術は、エンコーダに卦いてパリテイチエツク
ビツトを発生するために２進除算技術を用い、またデコ
ーダではシンドロームとそのシ７卜された形式を用いて
いる。

従来技術では、エンコーダにおいて作られる符号語の
ｌビツトと、デコーダで順次受信されるデータブロツク
を処理するための同期機能との間の同期を維持するため
に必要な論理機能については無視されていた。１９７２
年以前に卦いては、２進除算は、直 １列接続されたシ
フトレジスタに、一連の排他的論理和ゲートを分散させ
る方法によつて行われるのが普通であつた。

この構成では、エンコーダでの除算において、入カデー
タの拡張データが被除数として用いられ、符号ジエネレ
ータ語 ２が除赦として用いられた。除算の各スナツプ
において、部分剰余の先頭ビツトが、シフトレジスタ列
内に、設けられた多数の排他的論理和ゲートに、フイー
ドバツクされる。この従来の構成では、多数の排他的論
理和回路を必要とし、 〉これは特に符号ジエネレータ
語では顕著である。高速の磁気バルブ素子が進歩するよ
うになつて、多数の排他的論理和ゲートや複雑な論理回
路を用いるのは効率が悪くなつた。代りに、直列エンコ
ーダ装置に対して単一の排他的論理和３Ｃゲートを用い
る手法が取り入れられ、その最初のものは、ＢｅｌｌＳ
ｙｓｔｅｍＴｅｃｈｎｉｃａｌＪｏｕｒ−ｎａｌ誌の１
９７２年２月号の論文゛ＴｈｅＤｅｓｉｇｎａｎｄＥ）
Ｔ１ｂｏｄｉｍｅｎｔｏｆＭａｇｎｅｔｉｃＤｏｍａｉ
ｎＥｎｃｏｄｅｒｓｆｏｒＳｉｎｇ１ｅ−ＥｒｒｏｒＣ
ｏｒｒｅｃｔ−゛ｉｎｇＤｅｃｏｄｅｒｓｆｏｒＣｙｃ
１１ｃＢｌｏｃｋＣｏｄｅｓ″”に示されて訃り、また
この論文は、関連する従来技術の文献を示している。こ
の論文は単一の排他的論理和ゲートを用いた回路を示し
ている。しかしこの回路は磁気ドメイン技術を対象とす
るものであつた。この技術では、情報のすべてのビツト
は１つのクロツクサイクルの１周期において伝搬しなけ
ればならないという制約条件があつた。従つて、磁気ド
メイン技術は安価な蓄積装置を与えるにもかかわらず、
半導体回路の瞬間的な動作に較べると、すべての動作（
発生、伝搬、センス、削減等）に長い時間を必要とした
。さらに、半導体のシフトレジスタでは、シフト入力を
ある速度で行い、シフト出力を別の速度で行うことがで
きるのに対し、上記の回路ではこのようなことはできな
かつた。また、−ヒ記の論文で示されているエンコーダ
回路は、パリテイビツトの数がデータビツトの数に比較
した時に十分な大きさを持つという特殊な場合に対する
ものであつた。

チヤネル容量を効率良く用いるためには、パリテイビツ
トの数はデータビツトの数に較べて小さいことが望まし
い。上記の論文はこのようなチヤネルの効率的な使用に
ついて触れてもおらず、また従来技術について参照する
こともしていない。上の論文は、デコーダで用いられる
２進除算の処理についても述べている。

一連の排他的論理和ゲートがシフトレジスタ列とともに
用いられている従来の形のデコーダを明確にするととも
に、磁気ドメイン技術の制約のもとで用いられる直列デ
コーダの設計についても記されている。上記の、磁気ド
メインエンコーダに関する制約はデコーダについても成
立する。さらに、上記の論文は、伝送システムを構成す
るエンコーダーデコーダ対の相互間の同期技術の必要性
については言及しているが、具体的な同期手法について
は記されていない。

発明の要旨 以上のような従来技術における制約条件、効率の悪さ、
及び限界は、本発明に従い、エンコーダに｝いてパリテ
イビツトを発生するために直列２進除算を用いるととも
にデコーダにおいてシンドロームの繰返しシフトを用い
、シンドロームを繰返しシフトしたものを符号の特性語
と直列比較することによつて誤り訂正情報を得る同期型
単一誤り訂正データ伝送゛？ステムによつて解決された
。

一般的に述べると、このエンコーダはジユネレー語及び
データ語シフトレジスタ並びに入力及びバツフアシフト
レジスタと、排他的論理和回路と、ゲート及びクロツク
手段とを含んでいる。レジスタへのシフト入力はデータ
語の速度及びその整数倍で行われ、シフト出力は符号語
の速度で行われる。パリテイビツトの数が小さい時には
エンコーダが正しく動作するために、バツフアレジスタ
の１つがセグメントに分割されている。これらのセグメ
ント化されたレジスタは、データ同期要求を満足すると
ともに、エンコードサイクル内に蓄積手段の各々のシフ
ト入力及びシフト出力が行われるというシフトレジスタ
要求をも満足する長さを持つている。デコーダは２つの
実質的に同じ部分から成り、その各々は２つの動作モー
ドを持つている。

その第１のモードでは、到来するデータブロツクが直列
除算によつて処理されて、シンドロームが作られる。一
方の部分がこの第１のモードで動作している時、他方の
部分は第２のモードで動作して、前″に受信されたブロ
ツクのシンドロームを処理し、シンドロームをシフトし
たものが作られる。順次シフトされたシンドロームを評
価する前に、これが一定パターンの特性語と比較され、
誤りが生じたか否かが決定される。第１のモードはデー
タ語の速度及びその整数倍で動作し、第２のモードは
Ｃ符号語の速度及びその整数倍で動作する。デコーダの
該部分の各々は、ジエネレータ語、中性語及びシンドロ
ームシフトレジスタ及び受信データバツフアレジスタと
、２つの排他的論理和回路と、ゲート及びクロツク手段
とを含んでいる。２つの部分は２つの動作モードを交互
に実行するため、２つの連続して受信されたブロツクは
任意の時間間隔において処理される。

直列エンコーダ・デコーダ伝送システムにより多くの利
点及び特徴が得られる。

１つの主栗な利点は、パリテイビツトの数が少い場合に
効率の良いブロツク符号が使えることである。

他の利点は、排他的論理和ゲートの数が減少したことで
あり、特に符号ジエネレータ語に対する高密度のゲート
が大幅に減少している。また他の利点として、（１）エ
ンコーダにおけるデータ及び符号語内のビツトと、（ｉ
ｉ）デコーダにおける受信語と訂正された語内のビツト
、との間の同期が容易に達成されている。また１つの特
徴としてはブロツクによつてジエネレータ語を変える能
力があり、伝送の機密性を増大させることができる。

【図面の簡単な説明】

第１図は、（７、４）・・ミング符号の処理の例を示す
ための、従来技術による直列除算処理装置の回路図であ
り、第２図は、ｐ≧Ｏ．４１４ｋを満足する一般的な（
ｎ．ｋ）ブロツクコードのための従来技術による直列エ
ンコーダの回路図であり、第３図は第２図のエンコーダ
の種々の処理間隔を示すタイミング図であり、第４図は
、ｐく０．４１４ｋである一般的なブロツク符号の直列
エンコーダの本発明に従つた一実施例を示す回路図であ
り、第５図は、一般的な（ｎ．ｋ）ブロツク符号のため
の直列デコーダの本発明に従つた一実施例を示す回路図
であり、第６図は、第５図のデコーダの種々の処理間隔
を示すタイミング図である。 詳細な説明説明を明確にするために、実施例の説明に当
つては、機能の理論的基礎について述べる。 種々の可能なＢＨＣコードの１つの特定のコードを表わ
す（７、４）・・ミングコードを理論的概念を示すため
の例とする。また基本的概念を例示するために、前述の
論文に記されている特殊なデコーダについて論じる。エ
ンコーダ、デコーダ及びこれらの組合せに関する一般的
な実施の説明は機能の基礎の説明の後に行う。１．機能
の理論的基礎 ここで述べる説明の主たる目的は、巡回ブロツク符号に
付随する用語を確立することど、このようなコードの数
学的取り扱いを定義することにある。 これらの概念のより完全な定義は１９６１年にＪｏｈｎ
Ｗｉ１ｅｙａｎｄＳｏｎｓ社から出版されたＷ．Ｗ．Ｐ
ｅｔｅｒｓｏｎ著の本ＥｒｒｏｒーＣｏｒｒｅｃｔｉｎ
ｇＣｏｄｅｓに示されているｏブロツク符号は、ｋケの
情報ビツトからなる２進ブロツクと、これに付随するｐ
＝ｎ−ｋビツトのパリテイビツトから成る２進ブロツク
とから形成される（ｎ１ｋ）ブロツク符号によつて表わ
される一連の符号からなる。ここで、ｋビツトブロツク
をデータ語と呼び、またｎビツトブロツクをチヤネル語
、ｐビツトブロツクをパリテイチエツク語と呼ぶ。（注
意すべきことは、ここで１語１と呼ぶものは一定のビツ
ト長を持たない。よつて、例えば、データ語はｋビツト
から成り、チヤネル語はｎビツトから成るというふうに
使う。）取扱いのために（さらに高度な数学的な目的の
ために）、種々の符号語に多項式を対応させると都合が
良い。 一例として、あるｎビツトチヤネル語が１０１００１１
で表わされるビツト流を持つ時、その多項式表示はとな
ｂ１これは第１、第３、第６及び第７の２進位置の１に
対応している。 巡回符号の各々に対し、そのすべてのチヤネル語を除算
する多項式ｇωが存在する。 この多項式は符号のジエネレータと呼ばれ、その長さは
（Ｐ＋１）ビツトである。多項式ｇ（ｘ）はこれが定義
される体において既約であり素因数であるＯ符号語のジ
エネレータ多項式での除算の例を示すために、上のｃω
をそのジエネレータｇ（ｘ）＝ｘ３＋ｘ＋１（１０１１
）で除算すると次のようになる。 すなわち剰余は図のように３桁の２進ゼロとなる。 上の除算の過程において、５プラス″゛記号は排他的論
理和操作を表わす。除算をこのような規則で行うと、多
項式除算のビツトの扱いのみによ）、よク短い形式で行
うことができる。すなわち上の除算を次のように行うこ
とができるＯ一般に、ｃ（ｘ）の最初のｋビツトはデー
タ多項式を表わし、これをｄ（ｘ）と記すものとし、ま
たｃ（ｘ）の最後のｐ＝ｎ−ｋビツトはパリテイチエツ
ク多項式を表わし、これをｐ（ｘ）と記すものとする。 各ｄ（ｘ）に対してｐ（ｘ）を得るために、各ｄ（ｘ）
にｐケのゼロを付加することによつて、ｅ（ｘ）と記す
拡張データ多項式を作る。上のｃ（ｘ）については、ｄ
ω及びｅ（ｘ）はそれぞれビツト列１０１０及び１０１
００００によつて表わされる。ｅ（ｘ）をｇ０ｃ）で除
算することにより、予想される通り０１１が得られる。
上の議論に従えば、エンコーダの一般的機能は、データ
源からの連続するブロツクから情報ｄ（ｘ）を受信し、
チヤネル語ｃ（ｘ）を作ク出すことである。 これを２つの機能に分割すると、次のようになる。（１
）拡帳データ語ｅ（ｘ）を作つてこれをジエネレータ関
数ｇ（ｘ）で除算する。（１１）剰余ｐ（ｘ）をｄ（ｘ
）に付加してｃ（ｘ）を形成する。チヤネル語ｃ（ｘ）
がシステム内を伝送されると、誤りがランダムに発生し
て受信ビツトパタンを変えてしまう可能性がある。単一
誤り訂正システムでは、デコーダはｄ（ｘ）の元の情報
（ビツト）を復元する。受信されたチヤネル語をｒ（ｘ
）と記す０誤りを検出し訂正するために、デコーダは先
ずｒ（ｘ）をｇ（ｘ）で除算する。この時得られる長さ
ｐビツトの剰余をシンドロームと呼び、８（ｘ）で表わ
す。このシンドロームは、ｒ６ｃ）で表わされる符号の
特性多項式と比較される。特性多項式はｘｎ−１をｇ（
ｘ）で除算した時の商として与えられる。もし、シンド
ロームがｒ（ｘ）に一致していると、誤）が第１のビツ
ト位置、すなわちｘｎ−１に対応する位置で発生してい
ることが示される。一致しない時には、シンドロームが
シフトされ、すなわちｘが乗算されて、ｘｓ侵）が得ら
れる。このシフトされた多項式がｇ（ｘ）で除算され、
その剰余がｒ（ｘ）と比較される。一致すると、ｘｎ−
２に対応する位置に誤りのあることが示される０一致し
なければ、さらにシフト及び除算が繰り返えされる。シ
フト、除算及び比較が繰返えされて一致が検出されるか
、あるいは誤りがない場合には、次に受信された語ｒ６
ｃ）の処理へと進む。デコーダの機能に関する上の議論
の例を示すために、上記のチヤネル語ｃ（ｘ）の３番目
のビツ卜位置に誤りが生じたものとし、ｒ（ｘ）＝ｘ６
＋ｘ＋１（１００００１１）とする。 ジエネレータ語１０１１に対する特性語ｒ（ｘ）は次の
ように計算できる。すなわち、ｒ（ｘ）＝ｘ２＋１とな
る。 ｒ（ｘ）をｇ（ｘ）で割ると、より、ｓ（ｘ）＝ｘ２
＋ｘとなる。 このｓ（ｘ）はｒ（ｘ）とは一致しないため、シンドロ
ームはシフトされて、さらに除算される。 これらの繰返しを簡略化して記すと、次のようになる。
ｘ２ｓ（ｘ）の剰余とｒ（ｘ）とが一致するため、 ３
番目のビツト位置が訂正（反転）され、ｄ（ｘ）を表わ
す始めのｋビツトがデコーダによる後処理のために抽出
される。 上記の除算処理を回路で行う方法を示すために、（７、
４）ハミングコードのエンコーダを表わす第１図の回路
について考える。 この回路は前記の論文に示された符号器を修正したもの
である。ｇ（ｘ）（１０１１）の下位ｐビツトをｇ″ω
（０１１）で表わすものとすると、これは循環シフトレ
ジスタ１００に蓄えられる。 循環の前及び後のいずれに訃いても、レジスタ位置１０
１が最上位ビツト（０）を蓄え、レジスタ位置１０２が
次の上位ビツト（１）を蓄え、レジスタ位置１０３が残
りのビツトを蓄えている。シフトレジスタ２００は２つ
の働きをする。すなわち、（１）最初、レジスタ位置２
０１乃至２０４はｄ（ｘ）で表わされるデータ語を受信
して位置２０１が最上位ビツトとなるようＫ該語を蓄え
る。次に（ｉｉ）除算過程が進行する時、レジスタ位置
２０１乃至２０４は部分剰余を蓄え、ｋ（４）回の循環
で得られる剰余がパリテイチエツク語ｐ（ｘ）を表わす
ようになる。スイツチＳ４はレジスタ２０１の内容に応
動し、レジスタ２０１の内容が論理１の場合にのみ閉じ
る。シフトレジスタ１００及２００の内容は最初それぞ
れｇ′６ｃ）及びｄ（ｘ）によつて初期化された後は、
同期して循環して排他的論理和回路１５０によつて比較
される。レジタ１００は時計方向に循環するのに対して
、トランジスタ２００は反時計方向に循環する。次のデ
ータ語の最初のビツトが現れる前にパリテイチエックビ
ツトを計算してその結果を出力バツフアに送出すること
ができるようＫ１循環時間が決定される。エンコーダ１
０は、前のサイクルの終了後、空にされた後、次のよう
に動作する。 最初の３ビツト（１０１）がレジスタ２００及び出力バ
ツフア３００にシフトして入れられパリテイチエツクビ
ツトがバツフア３００に送り出され、シフトレジスタは
空となる。 次にステツプ１に戻り、次のデータ語に対する処理が繰
返えされる。一般化した（ｎ．ｋ）ブロツク符号で、ｐ
〉０．４１４ｋを満足する符号に対する従来技術の直列
エンコーダ１０が第２図に示されている。 このエンコーダは第１図と同様の除算回路を用いている
。第２図の回路で、到来するデータビツトはｎｔ秒ごと
にリード２０１１に一様に現れ、符号化された情報はｋ
ｔ秒ごとにリード２０１２へ送出される。符号情報はシ
フトレジスタ２４００、２５００及び２６００に分割さ
れて蓄積される。これらのレジスタは、ｋｔ秒ごとにそ
れぞれスイツチＳ６、Ｓ７及びＳ８によつて空にされる
。ある時点に｝いて、これらのスイツチの１つのみが閉
じられる。シフトレジスタ２４００（Ｒ１）は長さｐで
あり、パリテイチエツクビツトを蓄える。シフトレジス
タ２５００（Ｒ２）も長さｐであり、現在のデーるＯシ
フトレジスタ２００がもう１度シフトされ、データの最
上位ビツトが位置２０１に入り、４＋１番目のデータビ
ツト（０）が位置２０４及び出力バツフア３００に同時
に入れられる。 シ７トレジスタ１００及び２００は１回だけ完全に循環
する。 シフトレジスタ２００は１回だけシフトされて、位置２
０２のビツトが位置２０１に入り、位置２０４にばＯ″
゛ビツトが入る。 ステツフ）。３及び４はさらに３回繰返えされ、その各
々においてレジスタ位置２０１の内容がスイツチＳ４の
セツトのために用いられる。 これで除算は完了する。レジスタ２３００においてｎｔ
／ｐ秒ごとにレジスタ位置間を伝搬する。 ｄ′（ｘ）のビツト（ｐ＋１）の到着は、ｄ′（ｘ）の
最初のビツトがレジスタ位置２２０２から位置２にある
スイツチＳ５を介して位置２２０１へ動き、第２のビツ
トのビツトの位置２２０３から位置２２０２への動き、
等と同期しており、ビツト（ｐ＋１）は位置１にあるス
イツチＳ１を介してレジスタ位置２２０７へ入れられる
。 レジスタ２２００の内容のレジスタ２１００の内容（ｇ
′（ｘ））による除算のための循環は、次のｋ回のｎｔ
間隔にふーいて行われる。レジスタ２１００及び２２０
０におけるレジスタ位置間の循環伝搬はｎｔ／ｐ秒ごと
に行われる。スイツチＳＡ．．Ｓ４及びＳ５の動作は、
第１図のスイツチＳ４、Ｓ３及びＳ５の動作と同じであ
る。２進除算処理は、データ語ｄ′（ｘ）のビツト（ｐ
＋１）乃至ｋの到着に同期して行われる。 これらの（ｋ−ｐ）ビツトは、各ビツトがｎｔ秒ごとに
到着してレジスタ位置２２０７に蓄えられる度にスイツ
チＳ１からレジスタ２６００に蓄えられる。さらに、除
算処理中において、レジスタ２５００に蓄えられていた
データは（２ｎ−ｋ）ｋｔ秒の遅延の後、空にされ、続
いてレジスタ２６００の内容が送シ出される。レジスタ
２２００に入つているｐケのパリテイビツトはレジスタ
２６００の最後の送り出し動作に先立つてｎｔ間隔中に
シフトレジスタ２４００にシフトされる。 また、シフトレジスタ２３００は、この同じｎｔ間隔に
おいて、次のデータ語ｄ゛（ｘ）のｐビツトを累積する
。レジスタ２４００、２５００及び２６００が適切な時
点で空にされれば、上のサイクルは無限に繰返すことが
できる。第２図のエンコーダ１０の動作は、第３図のタ
イミング図のように要約することができる。 行（１）はデータ語ｄ′（ｘ）及びｄ゛（ｘ）の到着間
隔を示している。行（ｉｉ）はこれらのビツトがレジス
タ２３００からレジスタ２２００及び２５００ヘシフト
される間隔を示している。行（１１１）は、２進除算処
理が行われる間隔を示している。行（ｖ）はパリテイビ
ツトがシフトされる時刻を示している。最後の行（Ｖ）
はセグメント化された符号情報がシフトレジスタ２４０
０、２５００及び２６００からシフト出力される順番を
示しているＯ２．エンコーダの実施例 第２図及び第３図を詳細に見るとわかるように、レジス
タ２４００、２５００、及び２６００の構成は、ｐがｋ
に較べて小さい場合には不適切なものとなる。 特にｐ〈（ｘ／２−１）ｋであると、第２図の従来技術
によるエンコーダは機能しない。これは、ビツト（ｐ＋
１）がレジスタ内をレジスタ位置２６０１へ伝搬する前
にｐケのビツトのすべてがレジスタ２５００からシフト
して出力されてしまうためである。このときレジスタ２
６００はまだシフト入力されているため、シフト出力を
始めるための正しいビツトパタンを蓄えられない。多く
の実用的な符号では、チヤネル容量を効率良く利用する
ために、ｐを小さくする必要があるため、ｐ〈（ｓＶ′
２ー１）ｋの条件はシステム設計の制約条件となる。従
来技術の効率の悪さを改善する本発明に従つたエンコー
ダの実施例が第４図に示されている。この構成では、ビ
ツト（Ｔ５＋１）乃至ｋを蓄えるレジスタ（第２図では
レジスタ２６００）は、セグメントレジスタ４６００、
４７００及び４８００に分割されている。この新しい構
成はデータ同期の要求を満足するとともに、シフトレジ
スタはエンコードサイクルに｝いて予め定めた期間内に
シフト入力及びシフト出力ができるという規約を満足し
ている。デコーダ１２の実施例において、セグメントを
分割するのに一般に２つの方法がある。 その最初の方法では、−般後のセグメントを除くすベて
のセグメントの長さをｐにし、最後のセグメントの長さ
は、（ｋ−ｐ）ビツトと、長さｐのセグメントに割当て
られたビツト数との差とする。第２の方法では、セグメ
ント長を幾何級数に比例して定める。これらの原理を例
示するために、（１５、１１）ブロツク符号について考
える。 この符号の時ｐ＝４であり、ｐ〈（ＶΣ−１）ｋ＝４．
５となる。レジスタ４６００、４７００及び４８００は
、次のようにして、間隔（ｐ＋１）（ｎｔ）乃至ｋ（ｎ
ｔ）中に蓄えるために、７（＝ｋ−ｐ）ビツトを分割す
るようセグメント化される。上記第１の方法では、レジ
スタ４６００は長さ４となり、レジスタ４７００は長さ
３となり、レジスタ４８００は不必要となる。幾何級数
的構成では、レジスタ４６００は長さ４となり、レジス
タ４７００は長さ２となり、また最後に到着する１ビツ
トがレジスタ４８００に蓄えられる。３１，２６符号の
場合には、第１の方法では長さ５の４ケのセグメントレ
ジスタと、長さ１の１ケのレジスタを必要とする。 幾何級数的構成では、長さ、１、２、４、８及び６のレ
ジスタを必要とし、このうち最後のレジスタは幾何級数
的には割当てられなかつたビツトに対するものである。
第４図の素子のうち、レジスタセグメント４６００、４
７００及ひ４８００以外のすべての素子の動作は第２図
のものと同じである。 （第２図の参照番号は第４図では２０００だけ増分され
ている。）レジスタ４６００、４７００及び４８００の
動作においては、シフト入力は間隔（ｐ＋１）（ｎｔ）
乃至ｋ（ｎｔ）中に生じ、シフト出力は間隔（ｐ＋１）
（ｎｔ）乃至ニｋ（ｎｔ）中に生じる。具体的には、レ
ジスタ４６００は、（ｐ＋１）（ｎｔ）乃至ｍ（ｎｔ）
にシフト入力され、レジスタ４７００は（ｍ＋１）（ｎ
ｔ）乃至ｅ（ｎｔ）に駆動されて、以下同様であり、レ
ジスタ４８００は（ｅ＋１）（ｎｔ）ニ乃至ｋ（ｎｔ）
にシフト入力される。値ｍ１ ｅ１・・・、は、一株分
布又は幾何級数技術によつて決められる。スイツチＳ９
及びＳ１０はビツトのチヤネル４０１２への伝搬を同期
させる。ここで述べたエンコーダとこれに付随する方５
法論は、例として示した特定の形式に限定されるもので
はなく、添付の請求範囲のみによつて限定される他の実
施例についても適用できることはいうまでもない。 ３．デコーダの実施例 ｊ第
５図に示した回路図は、本発明に従つて実現されたデコ
ーダの一実施例を示している。 一般的に、デコーダ操作は次の３ステツプから成る。（
１）受信された語ｒ仮）のシンドロームｓ（ｘ）の計算
。（６）シンドロームｓ（ｘ）に対するシフトと除。算
の処■すなわちｓ（ｘ）にｘｅ ｅ＝ｏ、１、ｋ−１を
乗算し、次いで除算ＸｅＳ（Ｘ）／ｇ（Ｘ）を行う。０
１１）シフト及び除算の後、その部分剰余を特性多項式
ｒ（ｘ）＝ｘｎ−１／ｇ（ｘ）と比較する。 第５図のデコーダ２０は、ともに長さｐの２つのシンド
ロームシフトレジスタ５２００（ＳＲ１）及び６２００
（ＳＲ２）を持つている。 レジスタ５２００はｒ゛″（ｘ）又はｒ゛（ビツトｒ，
″゛、ｉ＝１、２、・・・、ｎとする）と記す１つの受
信語を処理して対応するシンドロームを決定し、レジス
タ６２００は、前に受信された語ｒ′ωのシンドローム
に対してシフトと除算を行う。長さｐのシフトレジスタ
５１００（ｇ″（ｘ））及びレジスタ５２００は、排他
的論理和回路５０３０及びスイツチＳＡ１、及びＳＢ１
とともに基本的直列除算回路を構成する。 シンドロームの計算中に、この直列除算回路はｋｔ秒ご
とに１回循環する。このとき、レジスタ位置からレジス
タ位置への伝搬時間はｋｔ／ｐである。シフトレジスタ
５４００（ｒ″゛（ｘ））は、ｒ゛″ωのシンドローム
が計算されているのと同じ時間中にリード５０１１に到
着するｒ゛（ｘ）の最初のｋビツトを蓄える。長さｐの
シフトレジスタ５３００は物性多項式ｒ（ｘ）を計算す
る。 レジスタ５３００に付随したデコーダ部がシフト及び除
算モードで動作する時、レジスタ５３００の内容は排他
的論理和回路５０３１によつてレジスタ５２００の内容
とビツト毎に比較される。この比較モードにおける循環
のために、ｎｔ期間を必要とし、これはレジスタ位置間
の伝搬時間ｎｔ／ｐに対応している。この比較循環と同
期してレジスタ５４００のシフト出力動作が行われる。
第ｅ回目のシフト及び除算動作の後のレジスタ５２００
の内容であるｐビツトのすべてがｒωのｐビツトのすべ
てに一致すると、『″ω内のｅ番目のビツトが排他的論
理和ゲート５０２２で反転されて、誤り訂正が行われる
。 この訂正は、インバータ５０２０及びトグル回路５０２
１の助けによつて達成される。比較の各ビツトは回路５
０２０で反転され、トグル５０２１は、ｅ番目のデータ
ビツトに対応してｎｔ間隔中に受信されたｐビツトのす
べてが論理１のときにのみ論理１出力を発生する。シフ
トレジスタ５２００に対応する部分に対して行つたのと
同様の構造及び動作の説明が、レジスタ６２００に付随
したもう一方のデコーダ部に対してもそのまま適用でき
る。 後者の部分の参照番号は前者の部分に対して１０００だ
け増分されている。データの同期はスイツチＳＣ，．Ｓ
Ｄ．．ＳＥ及びＳＦによつて行われる。 これらのスイツチは一連の受信語に対して位置１と２の
間で切り換えられる。訂正されたデータ語は、排他的論
理和ゲート５０２２の出力であるリード５０１２へ現れ
る。第５図のデコーダ２０のタイミング図が第６図に示
されている。 行（１）は受信語ｒ′ω及びｒ゛″ωが、ブロツク長ｎ
で、各ビツト毎にｋｔ秒の間隔で到着することを示して
いる。荏１１）は最初のｐ（ｋｔ）間隔において、受信
されるデータビツトｒ？′ レジスタ６２００に入れら
れることを示している。ビツト（ｐ＋１）が到着すると
、ｋステツプの除算が開始されて、次のｋ（ｋｔ）秒だ
け続く。ｒ゛″が受信中でありそのシンドロームを決定
するためにレジスタ５２００で処理されている（行（Ｖ
））時に、ｒ′０）シフトされて除算されたシンドロー
ムの比較が行われるｏ行０１１）は、ｒ゛の最初のｋビ
ツトのみがレジスタ６４００に蓄えられることを示して
おり、これはｋｔ秒の入力速度で行われる。レジスタ６
４００は間隔（ｎ−ｋ）ｋｔ乃至ｎｋｔにおいては消勢
されている。次にレジスタ６４００はｎｔ秒に１ビツト
の割合いでシフト出力を行う。行４ｖ）及び〜）は、行
（１１）及び（Ｊｉｌ）と同様のタイミングで、もう一
方のデコーダ部で行われる動作を示している。行（ＶＩ
）は、正しい同期を行うためのスイツチＳＣ１ＳＤ１Ｓ
Ｅ及びＳＦ（Ｄ股定を示している。最後に、行（Ｖ：ｌ
）は、第１及び第２のデコーダ部に付随した直列除算ス
イツチＳＡ１、ＳＢ１、及びＳＡ２、ＳＢ２の駆動を示
している。以上で述べたデコーダ及びそれに付随する方
法論は、例として示した特定の形式に限られるものでは
なく、添付した請求の範囲のみによつて限定される他の
実施例にも適用できることはいうまでもない。

Claims (1)

1. 【特許請求の範囲】 １ 入力のｋビットデータ語から巡回符号化されたｎビ
   ットチャネル語を発生するために、ｐ個のバリテイビッ
   トを発生するための直列シフト除算手段を含むエンコー
   ダにおいて、予め定めた長さに従つて該データ語のビッ
   ト（ｐ＋１）乃至ｋを蓄えるために該予め定めた長さを
   持つ並列構成のレジスタセグメントに分割されたシフト
   レジスタ手段を有することを特徴とするエンコーダ。 ２ 請求の範囲第１項記載のエンコーダにおいて、複数
   個の予め定めた長さのレジスタセグメントが実質的に等
   しいことを特徴とするエンコーダ。 ３ 請求の範囲第１項記載のエンコーダにおいて、複数
   個の予め定めた長さのシフトレジスタセグメントが幾何
   級数に比例することを特徴とするエンコーダ。 ４ 入力のにビットデータ語４０１１から巡回符号化さ
   れたｎビットチャネル語４０１２を発生するためのエン
   コーダ（第４図）と、語チャネル語を表現する受信語５
   ０１１の誤り訂正行うためのデコーダ２０との組合せに
   おいて、該エンコーダが、ｐ個のパリテイビットを発生
   するための直列シフト除算手段４１００、４１５０、４
   ２００、ＳＡ、Ｓ３、Ｓ４、Ｓ５と、該バリテイビット
   を蓄え、さらに予め定めた長さに従つて該データ語のビ
   ット（ｐ＋１）乃至にを蓄えるために、該予め定めた長
   さ（ｍ−ｐ、Ｌ−ｍ、Ｋ−Ｌ）を持つレジスタセグメン
   ト４６００−４８００を含む並列構成のレジスタに分割
   されたシフトレジスタ手段４４００−４８００とを含ん
   でおり、前記デコーダが、該受信語のシンドロームを繰
   返しシフトしたものを発生するために、該受信語を直列
   にシフト及び除算するための手段５１００、５０３０、
   ５２００、ＳＡ１、ＳＢ２と、直列にシフト及び除算す
   るための該手段と交互に動作し、符号の特性多項式を該
   シンドロームを繰返しシフトしたものと比較するための
   手段６１００、６０３０、６２００、ＳＡ２、ＳＢ２と
   、該比較手段からの予め定めた出力に応動し、該シンド
   ロームを繰返しシフトしたものを発生するために行われ
   た繰返し回数に従つて該受信語の訂正を行うための手段
   ５０２０、５０２１、５０２２、６０３１、６３００、
   ＳＦ）とを含んでいることを特徴とするエンコーダーデ
   コーダ回路。