JPS5813020A - 符号器 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 技術分野 本発明は非拘束データを拘束された形式に反転可能な方
式で変換する逐次符号化装置に関する。

本発明は動的記憶装置において特に有用である。

磁気ディスク又は磁気テープ等の媒体及び他の同様の媒
体に記録されるデータ密度を増加させるために過去にお
いて種々の方法が提案されて来ｆＣ６その１つの方法は
ラン・レングス制限符号化法（ｒｕｎ−１ｅｎｇｔｈ−
１ｉｍｉｔｅｄ　　ｃｏｄｉｎｇ）として知られ、これ
は符号化されたビット系列中の各「１」がその最近接の
「１」から特定の数のｒＯＪによって隔てられなければ
ならない事を要求する。

その数は、符号量干渉により少なくとも最小値ｄ゛でな
ければならず、またセルフ・クロックのために必要な最
大値ｋを越えてはならない。この形式に従う符号バー役
に（ｄ％ｋ）ラン・レングス制限符号と呼ばれる。本発
明はｄ＝１及びに＝７であるような、磁気記録チャネル
に適したある特定の符号に関する。非拘束データｋ　（
ａ　％　ｋ）拘束形式に変換するには、一般にｍ個の拘
束されないビットをｎ個の拘束され九ビットに写像する
必要がある。但しｍ＜ｎである。このｍ／ｎの比ｉ普通
コード・レートあるいは符号化効率と呼ばれる。

明らかにこのコード・レートを最大化する事が望ましい
。このレートを量大化する際に普通考暉されるトレード
・オフは復号ルック・アヘッド及びハードウェアの複雑
晩である。

復号ルック・アヘッドを犠牲にして符号化効率を高める
事は、一般に誤り伝播の増加をまねく。

但し誤り伝播とは、符号ストリーム中に生じた１ピツト
の誤りにより、符号化アルゴリズムが追己訂正的になる
前に、その後のある数のビットにも誤りを生じる事であ
る。誤り伝播を減少させる事は常に望ましい。（１，７
）符号の場合は２／６の符号化効率が最適である事が見
い出されている。

米国特許第５６８９８９９号明細書は２つの可能な（ｄ
ｌｋ）符号、（１′、、８）符号及び（２，７）符号ｔ
ｍ示している。生じ得るデータ符号は可変長で、固定レ
ートである状態独立な（ａｔａｔｅｉｎｄｅｐｅｎｄｅ
ｎｔ）ブロック符号である。（１，８）符号のコード・
レートは２／３で、その符号辞書ハ長さが３の倍数の形
で５ビツトから９ビツトまで変化する１６＠の符号語か
ら成る。（２，７）符号は１／２のコード・レートを有
し、七の符号器＄１４２の倍数の形で２ビツトから８ビ
ツトまで長さが変化する７個の語から成る。

次の２つの参考文献は、ラン・レングス・パラメータが
（１，７）でコード・レートが２／３の（ｄ、ｋ）符号
を開示している。これらの２つの文献は、’　Ｅｆｆｉ
ｃｉｅｎｔ　Ｃｏｄｅ　　ｆｏｒ　　ＤｉｇｉｔａｌＭ
ａｇｎｅｔｉｃ　　Ｒｅｃｏｒｄｉｎｇ”、Ｐ−Ａ・Ｆ
ｒａｎａｓｚｅｋＸＩ　ＢＭ　　Ｔｅｃｈｎｉｃａｌ　
　Ｄｉｓｃｌ’ｏｓｕｒｅＢｕｌｌｅｔｉｎ、Ｖｏム２
３．４９、Ｆｅｂｒｕａｒｙ１９８１、ｐ、４５７５及
びＡｎ　Ｏｐｔｉｍｉｚａｔｉｏｎｏｆ　Ｍｏｄｕｌａ
ｔｉｏｎ　Ｃｏｄｅ＠　　ｉｎ　　Ｄｉｇｉｔａｌ　　
ＳＲｅｃｏｒｄｉｎｇ　”、Ｔ、Ｈｏｒｉｇｕｃｈｉ及
びＫ。

Ｍｏｒｉｔａ、Ｉ　ＥＥ’Ｅ　　Ｔｒａｎｓａｃｔｉｏ
ｎｓ　　ｏｎ゛　■ Ｍａｇｎｅ　ｔ　ｉ　ｃ　ｓ　、　ＶｏＬＭ　Ａ　Ｇ−
１２、屋６、　　　　　　　　　いＮｏｖｅｍｂｅｒ　
　１９７６、ｐ、７４０である。これらの文献に記載さ
れ几符号化法は本発明と同じ（ａ、ｋ）値及び同じコー
ド・レート２／Ｉｔ有する符号を生じるが、符号化表が
異なり、吐つ符号化法も多くの点で異なる。

Ｆｒａｎａｓｚｅｋによって構成さ゛れた（１．７）符
号は有限のルック・アヘッド符号器及び可変長符号器を
有する。符号器は、２つの付加的なデータ・ビットのル
ック・アヘッドを用いる事によって２つのデータ・ビッ
トを５つの拘束されたビットに変換する。従って符号化
出力は現在の２データ・ビット及び将来の２データ・ビ
ットの関数である。復号器は３つの拘束されたビットを
現在のチャネル状態の関数として２つのデータ・ビット
に写像する。特定のチャネル状態に関してこの依存性は
以前のチャネル状態に及ぶ。この符号の誤り伝播は６ビ
ツトである。Ｈｏｒｉｇｕｃｈｉ外によって構成された
符号は可変長の固定レートの符号である。この符号の誤
り伝播は６ビツトである。

発明の要約 本発明の主な目的は、（１，７）ラン・レングス制限符
号を生成するための改良された装置を提供する事である
。

本発明の他の目的は、２つの非拘束データ・ビットが３
つの拘束チャネル・ビットに写像されるような、コード
・レートが２／３の符号の符号器を提供する事である。

本発明において、復号器における誤り伝播は５データ・
ピッｌ越えない。この誤り伝播け、先行技術の６ビツト
の誤り伝播を上回る改善を示している。本発明の他の利
点は、有限状態機械である符号＠ヲ、その初期状態に独
立な既知の固定された状態にリセットするリセット・デ
ータ・ブロックの存在であるこの特徴は先行技術には存
在しない。

本発明の他の目的は、そのような（１，７）ラン・レン
グス制限符号を生成するための非常に効率的な符号器／
復号器の設計を提供する事である。

本発明の目的１ハ、反転可能な方式で非拘束データを拘
束形式に写像するための新規な逐次アルゴリズム（後述
する）ヲ′用いる事によって満足される。一般に、特定
の（ｄ、ｋ）パラメータの組に関して、このアルゴリズ
ムはそのような写像を実限する有限状態機械である符号
器及び復号器を特定する。

ｄ＝１、ｋ＝７という特定のパラメータの兵且の場合、
このアルゴリズムは、内部状態の表現に６ピツト必要で
あってＸ＝（ｘ２、Ｘｌ、ｘＯ）で表わされる有限状態
機械である符号器を特定する。

この符号器は２つのプール関数、即ち入力５＝（Ｓｌ、
ａＯ）及び現在の状態Ｘ　＝　（ｘ　２、ｘｌ、ｘＯ）
ｉ次の次の状態Ｘ’＝（ｘ２、ｘｌ、ｘＯ）に写像する
次状態遷移関数、並びに入力５＝（ａｌ、ｓＯ）及び現
在の状態Ｘ＝（ｘ２、ｘｌ、Ｘｏ）ｆ：出力Ｙ’＝（ｙ
２’、ｙ１′、ｙｏ′）に写像する出力関数によって記
述される。復号器は、各々３ビツトから成る２つのチャ
ネル記号のルック・アヘッドを必要とする。・これらは
ｆｌ　＝＝　（ｙ２“、ｙ１′′、ｙＯ“）及びｙ　＃
　＝＝　（ｙ２　＃、ｙ１／ＩＩ　、　ｙｏ　＃　）に
よって表記される。復号器はＹ′＝（ｙ２′、ｙ１′、
ｙＯ′）及びＹ′及びＹ＃の関数であるプール方和式に
よって特定される。

従って復号＠はチャネル状態に独立であり、これは先行
技術に欠けていた好ましい特徴である。

第３図及び第７図に示されている符号器及び復号器のハ
ードウェアの実施例は、必要な論理回路の総量及び達成
可能な最高速度の両者において非常に効率的である。

良好な実施例の説明 本発明の（１，７）ラン・レングス制限符号を実現する
ための適当なハードウェア実施例の詳細な説明を与える
前に、発明の数学的基礎についての一般的説明を行なう
。

以前に説明したように、動的記憶装置は、２つの「１」
の間に存在する「０」のラン・レングスに対して下限と
上限□とを課すデータ符号を必要とする。ここで説明す
１．ｂ数学的アルゴリズムは、下限及び上限のパラメ」
りが各々ｄ＝１及びに＝７　　　　　　１によって特定
されたチャネルに関する有限状態機械符号器及び復号器
の設計を可能にする。コード・レートは２／３であって
、２つの非拘束データ・ピットが３つの拘束されたチャ
ネル・ビットに写像される。復号器における誤り伝播は
５データ・ピッ）ｔ−越えない。その他の特徴はリセッ
ト・データ・ブロックの存在である。例えばデータ・ブ
ロック００は符号器を固唾された状態（以下の説明中ア
用いられる表記法における状態０）にリセットする。

ここで開示する方法は、（１，７）チャネルに適用され
る（１．７）データ符号を生成するために用いられる数
学的に証明可能なアルゴリズムに関する。このアルゴリ
ズムはＲ，Ｌ、Ａｄｌｅｒ及びＢ、Ｍａｒｃｕａによる
論文−ＴｏｐｏｌｏｇｉｃａｌＥｎｔｒｏｐｙ　　ａｎ
ｄ　Ｅｑｕｉｖａｌｅｎｃａ　　ｏｆＤｙｎａｍｉｃａ
ｌ　　Ｓｙｓｔｅｍｓ”、Ｍｅｎ、　Ａ、　Ｍ、　Ｓ、
、２１９（１９７９）に説明されている。

このアルゴリズム入力は拘束された（１．７）チャネル
の状態遷移行列Ｔである。

ａｂ　　　　　ｃ　　　　　ｅ　　　　　ｆこの状態遷
移行列は、その行及び列ｔ−４１１ている２進数ブロツ
ク（ａ、ｂ、ｃ、ｅ、ｆ　）の許される連結を指定する
。（文字ｄは、それが上記文字−２進数ブロツク対応の
中の許されないブロック０１１に対応するので省略【７
た。）ここで説明するアルゴリズムにより適した行列Ｔ
の記述は下記の継承表（５ａｃｃｅｓｓ’ｏｒ　　ｔａ
ｂｌｅ）である。

ａ−＋ｂｃｅｔ　ｆ ｂ　　−＋　　ａ　　ｂ　　ｃ Ｃ→　ａｂｃｅｆ ｅ　　　→ａ　　　ｂ　　　ｃ　　　ｅ　　　ｆｆ　　
→　ａｂｃ コード・レートへ行列Ｔの最大固有値λ１のベース２ア
ルゴリズムとして与えられるチャネル容量ＣＴによって
決定される。この数は一般に〇−１行列の固有＠を計算
する手続から得られる。

データのエントロピーは１０ｇ２２Ｍ、と表わす事がで
きる。但し非拘束２進データ・ソースの場合λ　＝２で
ある。λ　３〉λ　２＝４の関係がＭ　　　　　　　　
　　　　ＴＭ 存在し、従ってコード・レー）　１４２　／　５である
。

継承衣以外の、符号化アルゴリズムへの第２の入力は次
式全満足する右近似固有ベクトル（ｒｉｇｈｔ　　ａｐ
ｐｒｏｘｉｍａｔｉｎｇ　ｅｉｇｅｎｖｅｃｔｏｒ）Ｌ
である。

Ｔｒ＞ｒ 一般にこのベクトルは整数計画法（ｉｎｔｅｇｅｒｐｒ
ｏｇｒａｍｍｉｎｇ）問題の解として得られる。本発明
の場合、このペクト−はｒ＝［４３５５６〕　であって
、不等式は実際には等式である。

アルゴリズムは、チャネル状態（ａ、　ｂ、　ｅ。

ｅ、ｆ）ｔ＝、ベクトルエの成分に従って、以下に示す
ような適当な順序（ｏｒｄｅｒ　）に分割する。

Ｃｉ＞は分割を表わす） ａ＝臣　ａＯａｌ　　　ａ２　　　ａ５ｂ　→　ｂｏ　
　　ｂｌ　　　　　　　　　　ｂ４ｃ’：＝＞　　ｃｏ
　　　ｅｌ　　　ｃ２　　　ｃ３　　　ｃ４ｅ　φ　ｅ
Ｏｅｌ　　　ｅ２　　　ｅ３　　　ｅ４ｆ　啼　ｆＯｆ
ｌ　　　　　　　　　　ｆ４（注：上で用いたラベリン
グは符号化装置の複雑性を単純化している。） チャネル状態を上のように分割する事は、あらゆる新し
いチャネル状態が正確に４つの継承者（８ｕｅｅｅ８１
１０ｒ　）を持つような新しい継承衣の構成を可能にす
る。この表の多くの行は同一であり、従って等しい状態
を一緒にまとめる事ができる。

そのようにまとめた表は下記の通りである。

；マ ａＯｌｂＯｌｃｏ、ｅＯｌｆＯ→　ｃｏ　　　ｃｌ　　
ｃ２．　　　ｃ３ａ１、ｂｌ、ｃｌ、ｅｌ、ｆｌ　　−
＋　　ｂｏ　　　ｂｌ　　　ｂ４　　　ｃ４ａ２　　　
　　ｃ２、ｅ２　　　　−＋ｅＯｅｌ　　　ｅ２　　ｅ
３ａ５　　　　　ｃ３、ｅ３　　　　−＋ｆＱ　　　ｆ
ｌ　　　ｆ４　　　ｅ４ｂ４、ｃ４、ｅ４、ｆ４　　→
　ａｏ　　　ａｊ　　　ａ２　　ａ３この表は符号器及
び係号器の両方の構成に必要な全ての情報を含んで腟る
。これを、よシ適切な形式に置＠換える。

符号化表 Ｏｎ　　１０　０１　１１ ０−）　ｅ、　Ｏｃ、　１　ｃ、　２　ｃ、　３１→ｂ
ｔＯｂ、１　ｂ、４　ｃ、４ ２→ｅ、Ｏｅ、１　ｅ、２　ｅ、３ ３→ｆ、　Ｏｆ、　１　ｆ、　４　’　ｅ、　４４→ａ
、Ｑａ、１、ａ、２ａ、３ この表には５つの異なった状態（０，１，２，５，４）
が現われる。到来したデータは一度に２ビツトが継承状
態に写像される。例えば００は１番目の状態の列によっ
て符号化され、一方１１は４番目の列に従って符号化さ
れる。状態遷移に関連する文字（ａＸｂ、ｅ、ｅ、ｆ　
）はそれによって生じた出力である。例えば００列の２
→ｅ、　　１は２Ｌ１Ｚム１のように読む事ができる。

但し００は入力であり、ｅは２→１の遷移から生じた出
力である（Ｍｅａｌｙ−Ｍｏｏｒｅオートマトンと等価
）。

状態遷移及び出力衣は第４図に示されている。

５つの異なった内部状態が存在するので、その表現には
３ピツトＸ＝Ｃｘ２、ｘｌ、Ｘｏ）７Ｉ）Ｘ必要である
。また入力は５＝（Ｓｌ、ＳＯ）、次状態はＸ’　＝（
ｘ２’、ｘ１’、ｘｏ’　　）、次出力はＹ’　＝（ｙ
２／、ｙ１’　　、ｙＯ’　　）で表わされる。

第４図の状態遷移及び出力衣から、００及び１０の両者
は符号器を各々初期状態０及び１にリセットするリセッ
ト・ブロックである車がわかる。有限状態機械符号器の
ハードウェア的実現ｉ！：＠３図に示されている。

復号器の構成は第４図の表の特別な構造に基づく。次の
性質が観察される。

（１）　　次状態は現在の状態の偶奇性にだけ依存する
。

（Ｉｔ）　　出力関数は８０ρｓ１の値にだけ依存する
。

復号器は次状態および出力関数を記述する２つのプール
表から導かれたプール方程式によって特定される。

ｘＯｓｌ　　　ｓｏ　　　　ｘ２’　　　ｘ１’　　　
ｘｏ’ｏｏｏｏｏ。

０１０１０ ０’１０００１ ０１１０．１１ ０００００ １　　０　　１　　　　１　　．０　　　０□ １１０　　　　０．０．１ １１１　　　　１　　　０　　　０ ｘ２　　ｘｌ　　ｘＯｓ０１’ｌｓ１　　　ｙ’２：’
　　ｙ１１ｙ／（３ｔ０００　　　０　　　　　０　　
　１　　　０　　　　ｃｏｏｌｏ　　　　　　００１ｂ ０１０　　　０　　　　　１　　　０　　　０　　　　
ｅｏｌｌ、０　　　　　１０１ｆ １００　　　０　　　　　０　　　０　　　０　　　　
ａｏｏｏ　　　　１　　　　　０　　　１　　　０　　
　　ｃｏｏｌ　　　　　１”０１０ｃ ０１０　　　　１　　　　　１　　　０　　　０　　　
　ｅｏｌｌ　　　　　１　　　　　１　　　０　　　０
　　　　ｅｌｏｏ　　　　　１　　　　　０　　　０　
　　０　　　　ａ本発明に従って構成きれた復号器はチ
ャネル状態に独立である、即ちチャネル状態に独立に復
号を行なう。チャネル状態からの独立性ζ、現在のもの
を含む３つのチャネル記号を必要とするルック・アヘッ
ド機能によって達成される。もし表記法Ａ　’　＝Ｙ２
　’ｌ”ｌ　ｙ　１　”ｌ”’Ｓ　ｙ　Ｏ”を用イルナ
らば、プール表から導かれｔ復号器方程式は次のように
なる。但し上式でｉは１〜３個のプライム記号を意味す
る。

Ｘ２’＝Ａ“ ｘ１ε−ｙ２“ ｘＯ’　＝ｙＱ“＋Ｊ　ＡＮ ａｌ：＝ｘＯ’す（ｘ２’ｌ″ｌ了） ｓ　Ｏ＝　ｘ　１　’　ＩＪ　ｘ　２ これらの式は次のチャネル状態Ｘ’−（Ｘ２’、ｘｉ’
、ｘＯ’　）及び復号された出力Ｓ　＝　（ｓ　１、ｓ
Ｏ）を、次のチャネル記号Ｙ′＝（ｙ２′、ｙ１’　、
ｙＯ’　　）、ｙ　＃　　＝＝　（、２＃、ｙｌ“、ｙ
　Ｏ／り及びｙ／／／＝＝（ｙ２／／／、）’　１＃、
Ｖ　Ｏ’　）　ニよッテ表わすものである。チャネル状
態の独立性１’１．　ｘ　２　’、ｘ１’、ｘＯ’に関
する式をＳＯ及びｓｌに関するプール方程式に代入する
事によって達成される。

最終結果のプール方程式は下記の通りである。

ｇｏ＝ｙ２”すＡＩＦ ｓｌ−（ｙＯ“ＵＡ／″　）ｕ（Ａ’ｌ”ｌ　ｙＯ’　
　）従って復号器はチャネル状態に独立になる。８０及
びｓｌに関するプール方程式のハードウェア的実現は第
７図に示される。

誤りが発生した場合、この誤りは２つの付加的チャネル
記号よりも遠くへは伝播しない。チャネル記号は２デー
タ・ピットに対応するので、復号器の誤り伝播は６デー
タ・ピラトラ越えない。実際の誤り伝播は５ピツトであ
る。

これまで本発明の符号化方式の基礎をなす概念を説明し
て来交が、以下本発明のハードウェアによる実現の良好
な実施例を詳細に説明する。

説明を行なうスライディング・ブロック符号（−ｓｌｉ
ｄｉｎｇ　　ｂｌｏｃｋ　　ｃｏｄｅ）は復号器におい
てルック・アヘッドを用いる逐次的方式の符号である。

これらの符号は符号器においてルック・アヘッドを行な
うｐ、Ｆｒａｎａｓｚｅｋの限界遅延符号（ｂｏｕｎｄ
ｅｄ　　ｄｅｌａｙ　　ｃｏｄｅ　）とは異なる。

第１図を参照すると、非拘束データを拘束された符号に
変換する典型的な符号化／復号装置の高レベルの機能的
ブロック図が示されている。ソース１０は符号器１２に
一度に２ビツトずつ供給される２進データの源である。

符号器の出力は、サイズ５の拘束嘔れたリストの形の６
ビツトのワードの連鎖によって作られ友系列である。符
号化された系列はチャネル１４の特性に適合されている
。

以前に述べ友ように、本発明の実施例におけるチャネル
は磁気ディスク、磁気テープ等の磁気記録媒体であるが
、当業者の認めるように、チャネルは伝送路等であって
も良い。

チャネル１４からの符号化データを元の形式に□ 復号する事が望まれる時、符号化された（拘束された）
データは一度に６ビツトずつ復号器１６に供給される。

復号器は、良く知られているように符号器の逆の機能を
実行し、２ビツトの非拘束データ群（データ・セグメン
ト）の系列を作る。

第２図を参照すると、符号器の機能ブロック図が示され
ている。符号器は図から明らかなように６つのレジ不り
ＲＥＧｌ、ＲＥＧ２及びＲＥＧ３並びに次状態及び出力
倫理回路２０から構成される。このブロックは第３図に
詳細に示すように最小量の論理回路から成る有限状態機
械を具体化している。第２図から明らかなようにレジス
タＲＥＧ１ｆｌピッ）ｓＯ及びｓｌから成るデータ人カ
ベクトルｓｔ−記憶するために用いられる。レジスタＲ
ＥＧ２はビットｘＯ１ｘ１、Ｘ２から成る状態ベクトル
Ｘを記憶するために用いられる。同様にレジスタＲＥＧ
５はビットｙＯ″′！　ｙ１′、ｙ２′から成る拘束さ
れたチャネル・ベクトルｙ”を記憶するために用いられ
る。データ・ベクトルを構成する各ビットは下記の通り
である。大文字は複数ビットから成る≠−タ・ベクトル
を表わし、小　　　　　　（７文字は各ピッ）ｆ表わす
。例えば２ビツトの入力ベクトルＳは２つのビットＢ１
及びｓＱから構成される。

入力　　　　５＝ｓｌ　　ｇ。

ＳＬは最下位ビット（ＭＳＢ） 状態　　　　Ｘ＝ｘ２　　ｘｌ　　ｘＯｘ２はＭＳＢ 次の状態　　Ｘ’＝ｘ２’　　ｘ１’　　ｘｏ’ｘ　２
　／はＭＳＢ 出力　　　　ＹＬ−ｙ２′ｙ１′ｙＯ′ｙ　２　／はＭ
ＳＢ 符号器内のデータの流れは第２図から明らかであろう。

２つの非拘束データ・ビットから成る入力ベクトルＳは
論理回路２０に左上から入力される。同時に、５ビツト
から成る状態ベクトルＸが論理回路２０の左下から入力
される。そして回路２０からの出力は出力チャネル・ビ
ットＹ′及び次状態ピッ）Ｘ’ｉ構成する。

データの流れ、次状態及び論理回路２０の詳細は第３図
に示されている。この符号器のハードウェアの設計の単
純さはこの図から明白である。総計１０＠の通常の論理
回路が符号化動作全体を実行する。この回路と例えば従
来技術において符号化動作を実行するのに必要な回路と
を＋を較すれば、回路貴の大幅な節約が容易に認められ
るであろう。

必要な１０個の論理回路蝶、２＠のインバータ２２及び
２４．２個のＮＡＮＤ回路２６及び２８．１個のＮ０Ｒ
Ｉ５］＃３０ならびに５個のＡＮＤ回路３２．３４．３
６．３８及び４０である。論理回路２０においてＳベク
トル及びＸベクトルに関するピット線並びに２つの出力
Ｙ′ベクトル及びＸ′ベクトルに関するビット線に表示
が付されている。

第４図を参照すると、コード・レート２／３の（１，７
）符号器に関する状態遷移表が示されている。この表は
符号器に入力されるあらゆる可能な入力の組合せ（Ｓ及
びＸ　）　ｅ％定し、任意の与えられ几入力の組に関し
て作られる正確な出力（Ｙ′及びＸ′　）も同様に特定
する。左端の列は可能な状態ベクトル、即ち３ビツトの
状態ベクトルＸの可能な全ての具体的構成を示す。表の
最上行には、２ピツトの入力ベクトルＳの可能なビット
構成が示されている。

表の各位置の対角線の上側ζ次状態Ｘ′を示し、対角線
の下側は次の出力ベクトルＹ′を示す。両入力に関する
具体的なビット構成は行及び列の見出しに書かれている
。出力ベクトルに関するビット構成は下記の通りである
。

ａ＝０　　０　　０ ｂ＝０　　０　　１ ｃ　＝０　　１　　０ ｅ＝１００ ｆ＝１　　０　　１ 表の使用法の例を示すために、人力状態ベクトルＸが０
１０に等しいものとする。従って表の行２が指定される
。次にデータ・ベクトルＳが１１に等しいとする。この
時は１表、、の列６が指定される。

表の行２及び列３の記入事項は５　／　ｅである。これ
は次の状態ベクトルＸ′が０１１であり、出力Ｙ′がｅ
即ち１００の２進ビツト・パターンである事を意味する
。

この符号器は入力ベクトルＳ及び状態ベクトルＸの＊Ｅ
に無関係に正確に同じ方式で作動する。

全てのそのような許されたベクトルはこのハードウェア
において完全に評価され処理される。

しかしながら表の行５．６及び７に示す３つの状態は現
実には存在せず、それらは不必要である事に注意され交
い。しかしながらそれらの位置は、次状態ベクトルＸ′
の全ての可能な構成を完全に評価するために示しである
。

表の内容に注意すると、次状態ベクトルが５．６又は７
であるような記入事項は存在しない。従って例えこれら
のベクトルの１つが符号器への状態ベクトル入力■への
初期設定入力として使われたとしても、表の一部はその
後決して使われないであろう。

種々のＳベクトル□文・カビットの組み合せ及びＸ□ ベクトル入力ビットの組み合せの具体的なラベル及び順
序は参照の便宜だけのものである。

表の意味のある内容は実際の２進ビツト構造である。言
い換えると、第４図の表の意味のある内容は「１」及び
「０」の系列である。従って００１というＸベクトル入
力及び１０というＳベクトル入力を仮定すると、この表
の意味のある情報は次の状態ベクトルＸ′が００１で次
の出力ベクトルＹ′が００１である事であって、この情
報が表の行１及び列１に存在するか否かは無関係である
。

第５図の（１，７）符号器の状態図は、符号器内で生じ
得る状態遷移を図式的に説明するために与えたもの４で
ある。番号を付した円あるいはノードの各々は、第４図
の表で特定された具体的な２進数構成を表わす。従って
ノード４は状態ベクトルＸが２進数構成１００を有する
ような状態である。ノード４から出る４本の矢印は０／
ａ、１／ａ、２／ａ及び３／ａと標熾されている。これ
らの矢は各々ノード０．１．２及び３を指す事に注意さ
れたい。矢に付した数字は次のような意味を持つ。例え
ば２　／　ａの矢の２はデータ・ベクトルＳが１０であ
る事ｋ、ａは次の出力ベクトルＹ′が０００である事を
意味する。また次の状態ベクトルＸ′はノード１であり
、これは２進値ｏｏ１を意味する。矢印を定義する数の
あるものが第４図のＳベクトルのラベルに指定されたよ
うに同じノードを指すように見えるのは偶然の一致であ
る。

第５図において３つのノード５．６及び７は他のノード
に写像されるが、ノード０〜４はノード５．６又は７へ
は写像されない。従ってノード５．６又は７は状態ベク
トルを初期設定する時に用いる事ができるが、その後の
動作は全て状態ノード０〜４によって指定された表の部
分内で起こる。

第６図を参照すると、（１，７）復号器の機能的ブロッ
ク図が示されている。この図は第２図の符号器に少し似
ているが、復号動作の場合は状態情報を発生し保持する
必要がない。復号器の出力は現在のチャネル記号及び将
来の２つのチャネル記号だけの関数である。従って符号
器と違って、復号器は計算され且つ入力にフィードバッ
クされなければならない内部状態を持たない。

レジスタＲＥＧ４〜ＲＥＧ６は各々種々のチャネル・ビ
シトの群を記憶する。レジスタＲＥＧ　４は次々回のチ
ャネル記号ｙ　ＩＩ　ヲ含み、レジスタＲＥＧ５１ｄ次
回のチャネル記号ｙ　Ｎ　＋含み、レジスタＲＥＧ６は
現在のチャネル記号Ｙ′の１つのビットｙｏ’ｌ含む。

これらのピットは直接に第７図の復号器論理回路１６に
ゲートされ、２個の出力データ・ビットｓＯ及びｓｌを
発生する。

復号器は有限状態機械ではなく、２つのプール方程式に
よって簡潔に特定′２！れるので、（８１、ｓ’１）ｋ
ｃｙＯ’、ｙ２’Ｘｙ１’、ｙＯ’、ｙ２＃、ｙ１″′
、ｙｏ　ＩＩＩ　）の関数として特定するプール表をあ
えて示す必要はないであろう。それらの式は第４図の状
態遷移表から導かれる。従って第４図は符号器と復号器
の両者を記述しているのである。

童業上の利用可能性 本発明による符号化及び復号法並びに符号器及び復号器
は、特に磁気記録チャネル等の動的記録装置において有
用である。そこではこの（１，７）ラン・レングス制限
符号が磁気記録チャネルにおいて優秀な記録結果を与え
る事が知られている。

これまでの説明から明らかなように、そのハードウェア
は回路量が少ない点で非常に効率的であり、論理同格に
おいて少数のレベルしか必要でないので、非常に速く動
作する。

従来技術で用いら・れていたラン・レングス制限符号の
符号器／復号器ハードウェアと比絞する時、上記装置の
経済的利点は明らかである。またこの符号に特有の５ビ
ツトの誤り伝播は従来の符号よりも短く、従ってより有
益である。

【図面の簡単な説明】

第１図は符号器及び復号４のブロック図、第２図は本発
明に於て使用するのに適した符号器のブロック図、 ｆ４３図は第２図の次状態及び出力論理回路ブロックの
論理回路図、 第４図は符号−の状態遷移及び出力を表わす図、第５図
は第４図で定義された符号器の別の状態　　　　　：ゼ
遷移図、 第６図は本発明において使用するのに適した復号器のブ
ロック図、 第７図は第６図の復号器論理回路ブロックの論理回路図
である。 出願人　　インターナショナル・ビジネス・マシー７．
ズ・コーポレークタン０ ネタ→ し− ５ｌｓｏ： ５　００　　０１　　１Ｇ ２１ Ｘ２）ＩＩＩＯ：　　　　　　　　　０　　　　　１　
　　　　２ｏｏｏ　　ｏ　　。　。 １４ ００１　１　　、　　。 ０１０２　　°　１２ ・　　　　・ ０　　１　　４ ０１１　３　　、　　。 ０　　１　　２ １００４　　。　。 ０　　１　　４ ０１５ｂｂ 、１８６　°　１　、′ 　　　　Ｏ １４ １１１７６、＞

Claims (1)

1. 【特許請求の範囲】 隣りあった１の間に量小限１個且つ最大限７個の０を有
   する、コード・レートが２／３のラン・レングス制限符
   号を作るための符号器であって、所定の符号化動作のた
   めに入力ベクトルとして２個の新しいメツセージ・ビッ
   ト及び直前の符号化動作によって生じた３ビツトの状態
   ベクトルを受は取る手段と、 上記ラン・レングス制限符号の規則に従うチャネル・ベ
   クトル及び次の符号化動作において用いられる次の状態
   ベクトルを、上記５ピツトの入力の関数として形成する
   ための論理回路手段とを含む符号器。