JPH0821957B2

JPH0821957B2 - コード化方法

Info

Publication number: JPH0821957B2
Application number: JP63319681A
Authority: JP
Inventors: ラズミツク・カラベド; ポール・ハワード・シイーゲル
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1988-03-18
Filing date: 1988-12-20
Publication date: 1996-03-04
Anticipated expiration: 2011-03-04
Also published as: EP0333324A2; EP0333324A3; JPH01256251A; US4888779A

Description

【発明の詳細な説明】 A.産業上の利用分野本発明は、最尤列検出（PRML）を用いてパーシャル・
レスポンス・チャネルを介して２進ディジタル・データ
を伝送する技術に関する。具体的には、ハードウェア要
件を軽減しながら高いコード化率でかなりのコード化利
得をもたらす、PRMLチャネル用トレリス・コードに関す
る。

B.従来技術及び発明が解決しようとする問題点以下に示す従来技術の参照文献は、本発明者等が本発
明に最も関係があると考えるものである。

［Ａ］J.K.ウォルフ（Wolf）及びG.ウンガーブック（Un
gerboeck）、「パーシャル・レスポンス・チャネル用ト
レリス・コーディング（Trellis coding for partial−
response channels）」、IEEE Trans.Comm.、Vol.COM−
34、No.8、1986年８月、pp.765−773. ［Ｂ］T.A.リー（Lee）及びC.ヘーガード（Heegard）、
「１−D^Nチャネル用の２進たたみこみコードの設計のた
めの反転技術（An Inversion Technique for the Desig
n of Binary Convolutional Codes for the 1−D^N Chan
nel）」、IEEE地域会議議事録、Johns Hopkins、1985年
２月．［Ｃ］A.R.カルダーバンク（Calderbank）、C.ヘーガー
ド及びT.A.リー、「磁気記録用２進たたみこみコード
（Binary convolutional codes with application to m
agnetic recording）」、IEEE Trans.Info.Th.、Vol.IT
−32、No.6、1986年11月、pp.797−815。

［Ｄ］H.タパル（Thapar）及びA.パテル（Patel）、
「磁気記録の記憶密度を増加させるパーシャル・レスポ
ンス・システムのクラス（A Class of Partial Respons
e Systems for Increasing Storage Density in Magnet
ic Recording）」、1987年Intermag、日本国東京。

［Ｅ］R.ウッド（Wood）、「テープ・チャネル上のミラ
ー方形コードのビテルビ受信（Viterbi Reception of M
iller−Squared Code on a Tape Channel）」、IEREビ
デオ及びデータ記録会議議事録、英国サザンプトン、19
82年。

［Ｆ］K.インミンク（Immink）及びG.ベンカー（Beenke
r）、「ゼロ周波数で高次のスペクトル・ゼロをもつ２
進伝送コード（Binary transmission codes with highe
r order spectral zeros at zero frequency）」IEEE T
rans.Info.Th.、Vol.33、No.3、1987年５月、pp.452−4
54。

参照文献［Ｅ］は、フル・レスポンス・テープ・チャ
ネル上でコード化率が1/2のミラー方形コードと一緒に
単純化したビテルビ検出器を使用することを記載してい
る。このコードは、ゼロ周波数でスペクトル・ゼロをも
ち、有界累積電荷を意味する。受信機は、累積電荷だけ
を追跡する縮退状態図に従って動作する。コードが、非
コード化２進データの最小距離１に対して、最小自由ハ
ミング距離２をもつことから、コード化利得が得られ
る。

参照文献［Ｆ］は、コード・パワー・スペクトル密度
とその低次の導関数がゼロ周波数で消滅し、Ｋ次のゼロ
・ディスパリティ・コードの最小ハミング距離が少なく
とも２（Ｋ＋１）であるという２進コードを記載してい
る。

上記の参照文献［Ａ］、［Ｂ］、［Ｃ］、［Ｅ］及び
［Ｆ］は含めて、これまでに開示された技術は、パーシ
ャル・レスポンス・チャネルを介する信頼性の高い高い
コード化率での伝送を可能にする、Ｋ次のスペクトル・
ゼロをもつトレリス・コードの適用を教示していない。
また、パーシャル・レスポンス・チャネル機能に固有の
メモリを開発することにより高いコード化利得を得る方
法も記載していない。

特定のコード化利得のために、特に最尤度検出器にお
いて、ハードウェア要件をかなり軽減させることによ
り、従来技術に比べて改善された高いコード化率のコー
ドを提供できる技術が求められている。さらに、こうし
た技術は、従来技術では対象となっていない、参照文献
［Ｄ］に開示されたようなパーシャル・レスポンス・チ
ャネルに適した大きなコード化利得をもつ高いコード化
率のコードを提供する必要がある。

C.問題点を解決するための手段本発明により、パーシャル・レスポンス・チャネルの
コード化利得を向上させ信頼性の高い出力を提供するた
めに、高いコード化率で入力列をコード化する改良され
た方法が開発された。この方法は、パーシャル・レスポ
ンス・チャネルの伝達関数がゼロになる各周波数を決定
し、こうした各周波数ごとに入力列を、ゼロのパワー・
スペクトル値をもつ２進コード列にコード化することを
伴っている。（本明細書では、パワー・スペクトル値が
ゼロである周波数を、「スペクトル・ヌル周波数」、す
なわち、エネルギーが伝送されない周波数と定義す
る。）チャネルを介するコード列の伝送に応答して、チ
ャネル出力列が生成される。チャネル出力列から最確コ
ード列が計算され、復号されて出力をもたらす。

D.実施例本発明により、パーシャル・レスポンス・チャネル用
の高いコード化率（すなわち、2/3、3/4、4/5）のトレ
リス・コードを構成する改良された方法が開示される。
現在磁気及び光学データ記録で最も関心が集まってい
る、ダイコード（１−Ｄ）、クラス４（１−D²）、拡張
クラス４（１−Ｄ）（１＋Ｄ）²、クラス１（１＋Ｄ）
及びクラス２（１＋Ｄ）²を中心にして、（１−Ｄ）
^M（１＋Ｄ）^Nの形の伝達多項式をもつチャネル用のいく
つかの新しいコードについて説明する。この改良方法
は、（１−Ｄ）²パーシャル・レスポンス・チャネルに
も適用できる。

この改良方法は、本明細書では「整合スペクトル・ヌ
ル」と呼ぶ固有の原理を利用している。すなわち、トレ
リス・コード・スペクトルは、チャネル伝達関数がゼロ
になる周波数がゼロになるように設計されており、した
がって、コード化利得が向上し、ビテルビ検出器の複雑
さが軽減される。

第１図に示すように、２進記号列などの形の入力デー
タが、バス10から符号器11に送られる。符号器11は、パ
ーシャル・レスポンス・チャネル12への入力となる２進
コード記号列を生成する。このコードは、チャネル12の
伝達関数中にゼロがある各周波数に対してゼロのパワー
・スペクトルをもつ。すなわち、このコード列は、パー
シャル・レスポンス・チャネルのスペクトル・ヌルと一
致するスペクトル・ヌルをもつ。パーシャル・レスポン
ス・チャネル12によってチャネル出力列が生成され、チ
ャネル出力端で検出器13によって検出される。この検出
器は、チャネル出力列から最確コード列を計算する。検
出器13は、チャネル出力列の周波数スペクトル内容だけ
を追跡することにより、計算及びハードウェアの要件を
軽減させ、バス10を介して供給される元の送信データ列
の近最尤推定値（または最確コード列）を生成する。次
いで復号器14が、検出された列から、バス15上に整合す
るスペクトル・ヌル・コード出力データを生成する。

このコード形式及びコード検出技術は、次に簡単に説
明する整合スペクトル・ヌル拘束条件を満たす入力によ
って生成された、パーシャル・レスポンス出力列のユー
クリッド距離特性の分析に基づいている。

スペクトル・ヌル拘束条件をもつ２進列は、文献で
は、第２図ないし第４図に相当するいわゆる「標準状態
図」によって記載されている。特に、周波数f₁,...,f_n
では、標準図G^f1,...,^fnは、以下の要件を満足する２進
アルファベットからのエッジ・ラベルをもつカウント可
能な状態図である。

1.あらゆる有限サブダイアグラムは、f₁,...,f_nでスペ
クトル・ヌルをもつ１組の列を生成する。

2.f₁,...,f_nでヌルを生成する任意の有限状態図が、ラ
ベルを保存する形でG^f1,...,^fnのサブダイアグラムに適
切に「分解」できる。

ゼロ周波数、ｆ＝０でのヌルに対する、G⁰と名付けた
標準図を、第２図に示す。ナイキスト周波数の半分、ｆ
＝1/2Tでのヌルに対する、G^1/2Tと名付けた図（ただ
し、Ｔはコード記号周期）を第３図に示す。ｆ＝０及び
ｆ＝1/2Tでの同時ヌルに対する、G^0,1/2Tと名付けた標
準図を第４図に示す。

▲G⁰ _N▼と▲G^1/2T _N▼は、連続するＮ個の状態を含むG
⁰とG^1/2Tのサブダイアグラムを示す。表記▲G^0,1/2T _N▼
は、Ｎ×Ｎ方形を形成する状態をもつG^0,1/2Tのサブダ
イアグラムを指す。

付録に、チャネル出力列の自由ユークリッド距離▲d²
_free▼上での新しい境界の誘導方法を示す。これらの列
は、加法ホワイト・ガウス・ノイズの存在下で整合スペ
クトル・ヌル・コードによってもたらされるコード化利
得に変換される。これらの境界は第１図に示すコード化
技術を有効にする。具体的には、これらのコード化利得
の境界は以下の通りである。

境界１（単純チャネル空白）：ダイコード（及びクラ
ス１）パーシャル・レスポンス・チャネルでは、入力拘
束図▲G⁰ _N▼（及び▲G^1/2T _N▼）によって生成される出
力列を記述する最小トレリスは、以下の状態を満足す
る。

Ｎ＝３では、ただし、Ｎ≧４では、▲d² _free▼＝４（利得3.0dB）ただし、注意：以下の境界についても同時にdB利得が計算され
る。

境界２（１次チャネル・ヌル）：（１−Ｄ）²（及び
クラス２）パーシャル・レスポンス・チャネルでは、入
力拘束図▲G⁰ _N▼（及び▲G^1/2T _N▼）によって生成され
る出力列を記述する最小トレリスは、以下の状態を満足
する。

Ｎ＝３では、Ｎ＝4,5では、Ｎ≧６では、境界３（同時ヌル）：拡張クラス４パーシャル・レス
ポンス・チャネルでは、入力拘束図▲G^0,1/2T _N▼によっ
て生成される出力列を記述する最小トレリスは、以下の
条件を満足する。

これらの境界は、整合スペクトル・ヌル拘束条件をも
つ高いコード化率のトレリス・コードによって実現でき
るコード化利得を指定する。実際にこのコード化利得を
実現するには、任意の２進データを第２図、第３図及び
第４図に示す拘束図によって生成されたコード列に変形
させる、好ましくは、11などの有限状態符号器と14など
のスライディング・ブロック復号器を伴う同期コードが
必要である。

前述したように、第２図は、列が１つの座標（ｘ）方
向に生成されるゼロ周波数でスペクトル・ヌルをもつ２
進列の標準状態図を示す。第３図は、1/2Tでスペクトル
・ヌルをもつ２進列の標準状態図を示す。第４図は、ゼ
ロ周波数と1/2Tでスペクトル・ヌルをもつ２進列の標準
状態図を示す。第４図は、列が２つの座標方向に生成さ
れる標準状態図であり、本出願人に譲渡された米国特許
第4567464号に開示されているＫ方向インターリーブ技
術を利用する。

列の拘束システムの容量は、指定された拘束条件を満
足させるコードの達成可能な最高のコード化率である。
公開されているこのAdler−Coppersmith−Hassner及びK
arabed−Marcusのスライディング・ブロック・コード構
成方法は、本発明の一部分をなすものではないが、それ
を使って、この容量に近いコード化率でコードを構成す
ることができる。図▲G⁰ _N▼、▲G^1/2T _N▼及び▲G^0,1/2T
_N▼の容量C_Nは、次式で与えられる。

したがって、任意の所望のコード化率k/n＜１に対し
て、Ｎの値を、そのコード化率をもつコード化率がk/n
のスペクトル・ヌル・コードを構成するのに十分な大き
さに選択することができる。

標準図によって生成された出力列に対応する最小トレ
リスを、ビテルビ検出のための基礎的トレリス構造とし
て使用する場合、コード化利得は上記の境界１、２及び
３によって与えられる。

検出中のタイミング及び利得制御の判断を改善するた
め、その出力チャネル列の連続するゼロの数が所定の数
以下のコード列だけが生成されるように、コードにゼロ
出力サンプルの最高ランレングスに関する制限条件が組
み込まれていることに留意されたい。また、所定のレベ
ルの信頼性をもつコード列だけが生成され、有限状態符
号器とスライディング・ブロック復号器は、コードがゼ
ロ・サンプルに関するこれらの最高ランレングス拘束条
件を満足し、かつ最悪時コード化利得を低下させる虞の
ある「疑似カタストロフィ」列を除去するように構成さ
れている。（疑似カタストロフィ列とは、拘束条件を記
述する状態図中で複数の個別経路で表わされる列であ
る。） 2/3、3/4及び4/5コード用の複雑さが軽減されたビテ
ルビ検出器が、標準状態図から誘導された基礎的トレリ
ス構造と共に示されている。しかし、他の選択可能なコ
ードと共に使用される検出器も、本明細書に例示された
方法により容易に誘導できる。検出器をさらに単純に
し、検出サイクルごとに複数ビットが検出される高速検
出を可能にするために、状態図のｐ乗からトレリスを誘
導する。（状態図Ｇのｐ乗は、Ｇと同じ状態と、s_iから
s_jまでのＧ中の長さｐの各経路の状態s_iからs_jまでのエ
ッジをもつ状態図Ｈである。Ｈのエッジ・ラベルは、Ｇ
の対応する長さｐの経路によって生成されたｐ個の記号
の列である。）今問題にしている本例では、冪数ｐは、
図の周期になるように選択され、それは図のサイクル長
の最大公約数である。図▲G⁰ _N▼と▲G^1/2T _N▼では、周
期は２である。図▲G^0,1/2T _N▼では、周期は４である。

同様な技術を使って、より高次のスペクトル・ヌルを
もつ、すなわち、パワー・スペクトルとその低次の導関
数の列にゼロを含むコードを利用することによって、よ
り大きなコード化利得をもつ整合スペクトル・ヌル・ト
レリス・コードを生成することができる。付録に、整合
スペクトル・ヌル・コードまたはパーシャル・レスポン
ス・チャネルあるいはその両方が、整合空白周波数で高
次のスペクトル・ヌルをもつときの、チャネル出力列の
自由ユークリッド距離に対する新規な一般境界について
の証明を示す。

境界４（高次空白）：ゼロ周波数または1/2ナイキス
ト周波数でｋ次のヌルをもつチャネルでは、次数Ｌの整
合スペクトル・ヌルをもつ列に対する拘束図によって生
成された出力列を記述する最小トレリスは、次の条件を
満足する。

この境界は、整合スペクトル・ヌル・コードが、チャ
ネル伝達関数空白によってもたらされる距離特性を利用
していることを示している。というのは、その結果生成
された最小距離が、コードの次数とチャネル・ヌルの合
計の線形関数であるからである。この結果が、高次の整
合スペクトル・ヌルによって実現されるコード化利得に
対する境界に変換される。たとえば、ダイコード・チャ
ネル上の次数１の整合スペクトル・ヌルは、4.8dBの最
小コード化利得をもたらす。

1/2、2/3、3/4及び4/5コードの適用次に、（１±D^N）及び（１±Ｄ）²チャネル用のコー
ド化率が2/3、3/4及び4/5で、第１グループのチャネル
ではコード化利得が3dB、第２グループでは利得が4dB、
3dB及び1.8dBのコードを実現する方法を詳細に示す。ま
た、これらのコードを、インターリーブによって（１−
Ｄ）（１＋Ｄ）²チャネルに適用して、3dB、1.8dB及び
1.8dBのコード化利得を得ることもできる。

（１±D^N）チャネルの場合、新しいコードは、参照文
献［Ａ］及び［Ｃ］で提案されている以前の方法によっ
て得られたコードに比べて、約3dBのコード化利得を実
現するのに必要なビテルビ復号器の構成の複雑さをかな
り軽減させる。さらに、このユニークな方法は、初期の
方法、すなわち、（１±D^N）以外の伝達多項式を用いる
方法では対象とされなかったチャネル用の一連の高いコ
ード化率のコードを構成する方法を提供する。

コード化率1/2のコード参照文献［Ｃ］で以前に発表されたダイコード・チャ
ネル用の双位相コードは、整合スペクトル・ヌル技術に
よって直接生成され、その特別な場合である。具体的に
は、双位相コードは、サブダイアグラム▲G⁰ ₃▼によっ
て正確に記述される。このサブダイアグラムは正確に0.
5の容量をもち、この場合、双位相コードは、特に単純
なブロック・コード構造をもつ効率100％（コード化率1
/2）のコードをもたらす。非コード化チャネルに対する
コードのコード化利得、すなわち、4.8dBは境界１によ
って与えられる。境界２は、（１−Ｄ）²チャネル上の
双位相コードの新しい適用分野をもたらし、非コード化
チャネルに比べて7dBのコード化利得をもたらす。この
場合、▲G⁰ ₃▼の２乗から誘導されたトレリス図は、こ
のコードが効率100％なので、完全最尤度復号器の構造
を提供する。

コード化率2/3のコードダイコード及び（１−Ｄ）²チャネルと共に使用され
る、ゼロ周波数でスペクトル・ヌルをもつコード化率2/
3のコードでは、十分な容量をもつ最小状態図は▲G⁰ ₄▼
であり、その容量はＣ＝0.694である。

表１に、▲G⁰ ₄▼の６乗から誘導された３状態拘束シ
ステムを示す。表のｉ行目ｊ列目のボックスは、状態ｉ
から始まり状態ｊで終わる許容可能な６ビット・コード
ワードのリストを識別する文字を含む。括弧内の数は、
リスト中のコードワードの数を示す。リスト中の６ビッ
トのコードワードを、表の下に示す。

ダイコード・チャネルまたは（１−Ｄ）²チャネルで
は、コード化率4/6の有限状態符号器は、各状態から出
た16個のコードワードを選択し、16個の個別の４ビット
・データ・ワードを対応するコードワードに指定するこ
とによって誘導される。好ましい実施例を、表２に示
す。これは、リストＡのコードワードを１行目から除去
して、特定の方式で、16個の個別の４ビット・データ・
ワードを各状態から出た16個のコードワードに割り当て
ることによって表１から誘導される。本明細書で指定さ
れた割当ては、データとコードワードの対応をもたらす
ブール関数が単純になるように選択した。

この表の項目は、c₁c₂c₃c₄c₅c₆／t₁t₂の形であり、c₁
c₂c₃c₄c₅c₆は生成されたコードワードであり、t₁t₂は次
の符号器状態である。

対応するスライディング・ブロック復号器を、表３に
示す。この表の項目は、c₁c₂c₃c₄c₅c₆/Lの形であり、c₁
c₂c₃c₄c₅c₆は受信したコードワードであり、Ｌはルック
・アヘッド判断ビットを表わす。このビットは、コード
ワードc₇c₈c₉c₁₀c₁₁c₁₂の関数であり、次式で与えられ
る。

記号「−」は、「どうでもよい」値を示す。データ欄
で、b₁b₂b₃b₄は復号化されたデータを表わす。

この符号器と復号器は、ROMをベースとする方法また
はブール論理のインプリメンテーションを用いて、従来
の技術によりハードウェアに還元することができる。

第５図は、チャネルの効果を組み込むことにより、▲
G⁰ ₄▼の２乗から誘導されるダイコード・チャネル上の
コード化率4/6の複雑さが軽減された検出器トレリスを
示す。この３状態トレリスは、従来技術によって誘導さ
れたビテルビ検出アルゴリズムの構造を提供する。この
コードは、3dBのコード化利得をもたらす（境界１を参
照）。

このコードは、インターリーブ・ダイコード・チャネ
ル上にインターリーブ方式で印加でき、3dBという同じ
コード化利得をもたらす。

第６図は、（１−Ｄ）²チャネル上で使用するときの
ビテルビ検出器のトレリス構造を示す。このコードは、
4dBのコード化利得をもたらす（境界２を参照）。

第７図と第８図は、それぞれ修正コードのクラス１と
２の適用分野用のビテルビ検出器トレリス構造を示す。
クラス１と２のチャネルでは、整合スペクトル・ヌル・
サブダイアグラム▲G^1/2T ₄▼は、ナイキスト周波数の半
分で必要なスペクトル・ヌルを生成する最小の状態図で
ある。上記に誘導されたコードは、ベクトルｖ＝01010
1...またはｖ＝101010...を表１の符号器の出力に加え
る（モジュロ２）ことにより、クラス１または２のチャ
ネルで使用できるように変換できる。この修正コード
は、同じベクトルｖを検出されたコード・ストリームに
加え（モジュロ２）、その結果を表２の元の復号器にパ
スすることによって復号される。この修正コードは、ク
ラス１では3dB、クラス２では4dBのコード化利得をもた
らす。

この修正コードは、インターリーブされたクラス１の
チャネルにインターリーブ方式で印加でき、3dBという
同じコード化利得をもたらす。

第９図は、15状態ビテルビ検出器トレリスを表の形で
表わしたものである。これが必要なのは、コードがイン
ターリーブ方式で伝達多項式（１−Ｄ）（１＋Ｄ）²と
共に拡大クラス４チャネルに印加されるときである。こ
れは図▲G^0,1/2T ₄▼の４乗に基づいている。このコード
は、3dBのコード化利得（境界３を参照）をもたらす。

コード化率3/4コードダイコード及び（１−Ｄ）²チャネルと共に使用され
る、ゼロ周波数でスペクトル・ヌルをもつコード化率3/
4のコードでは、十分な容量をもつ最小状態図は▲G⁰ ₅▼
であり、その容量はＣ＝0.792である。

表４に、▲G⁰ ₅▼の８乗から誘導された２状態拘束シ
ステムを示す。表のｉ行目ｊ列目のボックスは、状態ｉ
から始まり、状態ｊで終わる許容可能な８ビット・コー
ドワードのリストを識別する文字を含む。括弧内の数
は、リスト中のコードワードの数を示す。リストＡ中の
各コードワードをビットごとに補数化する（すなわち、
11111111のモジュロ２加算）ことによって得られるリス
トをで示すと、Ｃ＝及びＤ＝であることがわか
る。各リスト中の８ビット・コードワードを、16進数で
表の下に示す。各コードワードは１対の16進数記号で記
載される。

表の１行目と２行目にはそれぞれ65個の異なるワード
がある。コード化率6/8のコードでは、各行から任意の2
⁶＝64個のコードワードが選択される。選択されたコー
ドワードとデータ・ワードの指定とは独立して、対応す
る復号器がブロック復号器になり、各８ビット・コード
ワードを一義的な６ビット・データ・ワードに直接復号
する。

ダイコード・チャネルまたは（１−Ｄ）²チャネルに
ついて、表５に、それぞれ１対の８進記号によって表さ
れる64個の異なる６ビット・データ・ワードを、表の１
行目の64個のコードワードからなる特定の部分集合に割
り当てる特定のケースを示す。16進記号CCで表されるコ
ードワードは省略してある。この表で、表記「UV x WY
Z」は、ワード「UV UW UY VW VY VZ」を指定の順序で指
す。

状態２を表わす、２行目のサブセット及び割当ては、
１行目のコードワードをビットごとに補数化することに
よって得られる。16進数記号を用いると、これは、次の
ように変換される。

０←→F;1←→E;2←→D;3←→C; ４←→B;5←→A;6←→9;7←→８次の状態情報は表４から誘導される。

ブロック復号器も、表５の割当てから右から左に読む
ことによって誘導される。符号器と復号器は、ROMをベ
ースとする方法またはブール論理のインプリメンテーシ
ョンを用いて、従来の技術でハードウェアに還元するこ
とができる。

第10図は、チャネルの効果を統合することによって▲
G⁰ ₅▼の２乗から誘導される、ダイコード・チャネル上
のコード化率6/8のコードの複雑さが軽減された検出器
トレリスを示す。この５状態トレリスは、ビテルビ検出
アルゴリズムの構造をもたらす。このコードは、3dBの
コード化利得をもたらす（境界１を参照）。

このコードは、インターリーブされたダイコード・チ
ャネルにインターリーブ方式で印加でき、3dBという同
じコード化利得をもたらす。

（１−Ｄ）²チャネル上で使用するとき、ビテルビ・
トレリス構造は、上記のトレリス誘導と同様にして▲G⁰
₅▼の２乗から誘導される。このコードは、3dBのコード
化利得をもたらす（境界２を参照）。

クラス１及びクラス２のチャネルでは、整合スペクト
ル・ヌル・サブダイアグラム▲G^1/2T ₅▼が、ナイキスト
周波数の半分で必要なスペクトル・ヌルを生成する最小
状態図である。このコード化率6/8のコードは、ベクト
ルｖ＝010101...またはｖ＝101010...を表３の符号器の
出力に加える（モジュロ２）ことにより、クラス１また
はクラス２チャネル上で使用できるように変換される。
この修正コードは、同じベクトルｖを検出されたコード
ストリームに加え（モジュロ２）、その結果を表４の元
の復号器に渡すことによって復号される。

当業者にとっては、クラス１とクラス２のアプリケー
ションに対するビテルビ検出器トレリスを誘導する方法
は自明である。クラス１及びクラス２のチャネル上での
修正6/8コードのコード化利得は3dBである。

修正されたコードは、インターリーブされたダイコー
ド・チャネルにインターリーブ方式で印加でき、3dBと
いう同じコード化利得をもたらす。

このコードは、インターリーブ方式で拡張クラス４チ
ャネルに印加されると、1.8dBのコード化利得をもたら
す（境界３を参照）。当業者にならもう理解できるよう
に、拡張クラス４のアプリケーションに対するビテルビ
検出器トレリスは、コード化率2/3のコードの説明の最
後の所で説明したのと同じ方法で誘導できる。

コード化率4/5のコードダイコード及び（１−Ｄ）²チャネルと共に使用され
る、ゼロ周波数でスペクトル・ヌルをもつコード化率4/
5のコードでは、十分な容量をもつ最小状態図は▲G⁰ ₆▼
であり、その容量はＣ＝0.833...である。ただし、スラ
イディング・ブロック・コードを簡単にするために、状
態図▲G⁰ ₇▼を使用する。その容量はＣ＝0.885…であ
る。コード化率4/5のコードは、符号器の複雑さを軽減
するために、疑似カタストロフィ列の大部分（全てでは
ない）を除去する。

表６に、G⁰ ₇の10乗から誘導された４状態拘束システ
ムを示す。表のｉ行目ｊ列目のボックスは、状態ｉから
始まり、状態ｊで終わる許容可能な10ビット・コードワ
ードのリストを識別する文字を含む。括弧内の数は、リ
スト中のコードワードの数を示す。リストＡ中の各コー
ドワードをビットごとに補数化する（すなわち、111111
1111のモジュロ２加算）ことによって得られるリストを
表記で示す。リストＡ、Ｂ及びＤ中の10ビット・コー
ドワードを、表の下に示す。

２進ｘ＝x₁x₂...,x₁₀が与えられているものとして、
ｗ（ｘ）をｘのハミングの重みと呼ぶ。すなわち、ｘ中
の記号１の数である。

Ｓ＝｛x|xは状態３から状態５への▲G⁰ ₇▼中のワード
である｝Ｂ＝｛ｘεS|w（x₁，x₂,...,x₈）＝４｝Ａ＝Ｓ−Ｂ（Ｓ中のＢの補集合）Ｄ＝｛x|xは状態３からそれ自身への疑似カタストロ
フィ・ワードを表わす｝リストの大きさは、|S|＝190、|A|＝128、|B|＝62、|
D|＝162である。

コード化率8/10の場合は、任意の2⁸＝256個のコード
ワードが各行から選択される。表７は、256個の異なる
８ビット・データ・ワードを、表の各行から選択された
256個のコードワードからなる特定の部分集合に構造的
に割り当てるケースを示す。集合DDは、リストＤ中の16
2個のワードから選んだ132個のワードの任意の部分集合
である。

この復号器も、表７の割当てから誘導される。あるコ
ードワードのルックアヘッドを含む復号規則を、表８に
示す。この復号器は、スライディング・ブロック復号器
であり、２つの10ビット・コードワードから成る各スラ
イディング・ブロックごとに８データ・ビットを生成
し、したがって最高エラー長は２データ・バイトである
と示唆される。

次の表８では、現在のコードワードをy_n-1と名付け、
次のコードワードをy_nと名付ける。この復号規則は、符
号器表のどの項目を使って現在のコードワードY_n-1と復
号するかを決定する。例えば、表８の条件（１）が満た
されるならば、現在のコードワードY_n-1は、表６に示さ
れたＢの補数、即ち、の要素である。この現在のコー
ドワードは、表７の第４行、第１列に示されたデータ割
当に従って復号する必要がある。表８の１番右の列にお
ける記号中の矢印の左側及び右側に示された数字は、そ
れぞれ、現在のコードワードに関する正しいデータ割当
の行及び列を表わしている。

符号器11と復号器14は、従来技術によりROMに基づく
手法またはブール論理のインプリメンテーションを用い
て、ハードウェアに還元することができる。

例を挙げると、表７に示す有限状態符号器は、入力シ
フト・レジスタ51、状態シフト・レジスタ52、及び読取
り専用メモリ（ROM）53から成る、第11図に示すような
形式のものでよい。シフト・レジスタは、フィードフォ
ワード経路をもつ２端末入出力マシンである。入力シフ
ト・レジスタ51は、各クロック・サイクルＣで入力とし
て８入力ビットx₁，x₂,...,x₈を受け取り、そのサイク
ルＣ中にy₁，y₂,...,y₁₀を出力する。状態レジスタ52
は、クロック・サイクルＣごとに入力として２ビットの
状態情報s₁とs₂を受け取り、そのサイクルＣ中にs₁とs₂
を出力する。ROM53は、クロック・サイクルＣごとに10
ビット（８入力ビット＋２状態ビット）のアドレス入力
を受け取り、サイクルＣごとに12ビット（２更新状態ビ
ット＋10出力ビット）の出力を供給する。更新状態ビッ
トは、次のサイクルＣのため54を介して状態レジスタに
送られる。

例を挙げると、スライディング・ブロック復号器14
（表８に示した規則に従う）は、第12図に示す形式のも
のでよい。この復号器14は、入力シフト・レジスタ61、
ROM62、遅延シフト・レジスタ63、カウンタ64、判断論
理回路65及び「排他的OR」論理ゲート66を含む。ROM62
は、10ビット入力アドレスを受け取り、８ビットのデー
タ出力を供給する。各クロック・サイクルＣごとに、遅
延レジスタ63は、次のクロック・サイクルで使用するた
めROMの出力を記憶する。各クロック・サイクルＣごと
に、入力シフト・レジスタ61は10入力ビットy₁，
y₂,...,y₁₀を受け取る。入力シフト・レジスタ61のその
サイクル周期中の出力は、y₁，y₂,...,y₁₀である。この
出力は、カウンタ64に供給される。カウンタ64の２つの
４ビット出力ｖとｖ′は、同じクロック・サイクルで計
算され、それぞれy₁,...,y₁₀及びy₁,...,y₈中の１の数
を表わす。判断論理回路65の出力ｕは、入力ｖとｖ′に
応じて１またはゼロである。判断論理回路65は、次の規
則に従って出力変数ｕを作成するように指定される。

変数ｕは排他的ORゲート66への入力の１つであり、そ
のもう１つの入力は、以前のクロック・サイクルで記憶
された遅延シフト・レジスタ63の８ビットの内容であ
る。最後に、入力シフト・レジスタ61の出力は、ROM62
をアドレスして、８ビットのデータ出力を生成する。そ
の出力は、次のクロック・サイクルのため遅延レジスタ
63に記憶される。

第13図は、チャネルの効果を統合することによって▲
G⁰ ₇▼の２乗から誘導される、ダイコード・チャネル上
のコード化率8/10のコードの複雑さが軽減された検出器
トレリスを示す。この６状態トレリスは、ビテルビ検出
アルゴリズムの構造をもたらす。このコードは、3dBの
コード化利得をもたらす（境界１を参照）。

本発明によれば、コード化率2/3及び3/4のコードの場
合、前述のように、疑似カタストロフィ列を除去するこ
とができた。しかしながら、コード化率4/5のコードの
場合には、これらの疑似カタストロフィ列を完全に除去
することはできなかった。即ち、そのようにすること
は、改善点との兼合いで是認しえないような複雑さを伴
うからである。

（１−Ｄ）²チャネルで使用するとき、ビテルビ・ト
レリス構造は、上記のトレリス誘導と同様にして▲G⁰ ₇
▼の２乗から誘導される。このコードは、1.8dBのコー
ド化利得をもたらす（境界２を参照）。

クラス１及び２のチャネルでは、整合スペクトル・ヌ
ル・サブダイアグラム▲G^1/2T ₆▼が、ナイキスト周波数
の半分で必要なスペクトル・ヌルを生成する最小状態図
である。ダイコードの場合と同様に、この状態図▲G
^1/2T ₇▼は、その結果得られるコードを単純化するのに
使用される。この図の容量は、Ｃ＝0.885...である。ダ
イコード・チャネル用のこのコード化率8/10のコード
は、ベクトルｖ＝010101...またはｖ＝101010...を第11
図の符号器の出力に加える（モジュロ２）ことにより、
クラス１またはクラス２チャネル上で使用できるように
変換される。この修正コードは、第12図に詳細に示すよ
うに、同じベクトルｖを検出されたコードストリームに
加え（モジュロ２）、その結果を復号器14に渡すことに
よって復号される。

当業者にとっては、クラス１と２のアプリケーション
のビテルビ検出器トレリスを誘導する方法は自明であ
る。クラス１及びクラス２のチャネル上での修正された
コード化率8/10のコードのコード化利得はそれぞれ、3d
B及び1.8dBである。

このコードは、インターリーブ方式で拡張クラス４チ
ャネルに印加されると、1.8dBのコード化利得をもたら
す（境界３を参照）。拡張クラス４アプリケーションの
ビテルビ検出器トレリスも、コード化率2/3のコードに
関連して説明した方法で誘導される。

要約−従来技術のコードとの比較参照文献［Ａ］は、コード化率2/3、3/4及び4/5で3dB
のコード化利得を実現する、（１−Ｄ）チャネル用のコ
ードを記述している。表９に、3dBのコード化利得を実
現するためのこれらの従来技術のコードのパラメータ
を、同じコード化利得をもたらす本明細書で提示した対
応するコードと比較する。ゼロ・ランレングス制限（ZR
L）と名付けた、ゼロ出力サンプルの最高ランに対する
制限が、新しいコードで大幅に軽減されることがわか
る。検出器を基礎となるトレリス図の１つの段中でのエ
ッジの数によって近似的に評価したビテルビ検出器の複
雑さが、新しいコードでは大幅に軽減される。検出サイ
クルごとに検出されるサンプルの数は、各コードに対す
る「サンプル／エッジ」入力で与えられる。

本明細書に記載されたコード化利得を改良する方法と
技術に様々な変更を加えることができることを了解され
たい。例示した実施例は、例示的なものにすぎず、本発
明を制限するものではない。

E.発明の効果上記のコード列は、チャネル伝達関数が消滅する周波
数でコード・パワー・スペクトルが消滅するという特性
をもつ。スペクトル・ヌル周波数が「整合」されている
ため、チャネルの固有のメモリを開発することにより追
加のコード化利得が得られる。追加のコード化利得は、
これらの周波数でのコード列のスペクトル・ヌルの次数
を増加されることによって得られる。

ハードウェア要件は、コード列の周波数スペクトル内
容だけを記録する検出器を用いて、軽減される。この単
純化した検出器は、コードの完全な最尤度検出器の性能
をほぼ実現する。

付録以下の定理が、整合スペクトル・ヌル・トレリス・コ
ードのコード化利得に対する境界の基礎となる。

とする。ただし、e_nは整数の値をとる係数であり、e₀は
非ゼロである。ｅ（Ｄ）が（１−Ｄ）^kで割り切れる場
合、次式が成立する。

すなわち、|e|²で示されるｅ（Ｄ）の係数列のユークリ
ッド重みは2K以上である。

これを証明するため、以下に示す補助定理１を使用す
る。

とする。ただし、e_nは整数の値をとる係数であり、e₀は
非ゼロであると仮定する。ｅ（Ｄ）が（１−Ｄ）^kで割
り切れる場合、係数列｛e_n｝＝e₀e₁,...,e_nは少なくと
もＫ回符号が変わる。その証明には、帰納法を使用す
る。

Ｋ＝１の場合を考える。ｅ（Ｄ）が（１−Ｄ）で割り
切れる場合、次式が成立する。

すべての非ゼロ係数が同じ符号である場合、ｅ（１）
は、その符号をもつ非ゼロになる。したがって、係数列
｛e_n｝は、少なくとも１回符号が変わらなければならな
い。

ｅ（Ｄ）が（１−Ｄ）^kで割り切れ、整数多項式ｅ
（Ｄ）＝ｆ（Ｄ）（１−Ｄ）^kに因数分解されるものと
する。ｇ（Ｄ）＝ｆ（Ｄ）（１−Ｄ）^k-1は（１−Ｄ）^k-1で割り切れる。帰納仮説
により、ｇ（Ｄ）の係数列｛g_n｝は、少なくともＫ−１
回符号が変わる。ｅ（Ｄ）＝ｇ（Ｄ）（１−Ｄ）なの
で、すべてのｎについて、次式が成立する。

e_n＝g_n−g_n-1 多項式によって明示的に定義されない係数は、ゼロと見
なされる。ｇ（Ｄ）の非ゼロ係数の下記の部分列を考え
る。

ただし、は最初の非ゼロ係数であり、その他は符号が変わるとき
のｇ（Ｄ）の非ゼロ係数である。この場合、対応する係
数は次式を満足する。

これは、ｅ（Ｄ）の係数が、少なくともＫ−１回符号
が変わることを意味する。ただし、g_Mがｇ（Ｄ）の最後
の非ゼロ係数である場合、となることに留意されたい。

これは、追加の符号変化があり、総数が少なくともＫ
となることを意味する。したがって、補助定理は証明さ
れた。

以下の補助定理２は、チャネル入力の符号変化が、チ
ャネル出力のユークリッド重みにどのように寄与するか
を示す。

１−Ｄチャネルに対する整数多項式入力をとし、g₀と非ゼロとする。ｇ（Ｄ）の係数はＬ回符号が
変わるものとする。対応するチャネル出力をｅ（Ｄ）＝
ｇ（Ｄ）（１−Ｄ）とすると、出力列のユークリッド重
みは次式を満足する。

|e|²≧２（Ｌ＋１）（A2）その証明として、出力列のユークリッド重みを、次式の
ように書くことができる。

ｇ（Ｄ）が係数列の符号が変わらない場合、方程式（A
3）の最初の非ゼロ係数に対応する項の方程式（A3）に
対する寄与は少なくとも１であり、かつ最後の非ゼロ係
数の後にくるゼロ係数に対応する寄与も同じなので、 |e|²≧２となることがわかる。

ここで、ｇ（Ｄ）は下記の係数列で符号がＬ回変わる
（Ｌ≧１）と仮定する。

また、方程式（A3）で指標ｎ＝０からｎ＝ｊまでの部分
和をＥ（ｊ）と置くと、次式が成立する。

ここで、Ｅ（Ｎ＋１）が総計|e|²を示すと仮定すると、
次式が成立する。

Ｅ（０）≧１（A5）Ｅ（n_i）−Ｅ（n_i-1）≧2,i＝1,...,L （A6）Ｅ（Ｎ＋１）−Ｅ（n_L）≧１（A7）方程式（A5）と（A7）の不等号は、最初の非ゼロ係数及
び最後の非ゼロ係数の後にくる最初のゼロ係数に対応す
る寄与から生じる。方程式（A6）の不等号を証明するに
は、２つの場合を考慮しなければならない。

まず、の前の係数が非ゼロであると仮定する。そうすると、n_i
が、n_i-1の後で最初に変化が起こる位置なので、g_ni-1
の符号は、g_ni-1の符号と同じで、g_niの符号と逆でなけ
ればならない。したがって、この場合、次式が成立す
る。

もう１つの場合、と仮定し、g_jがの前の最後の非ゼロ係数であるとする。ただし、である。そうすると、次式が成立することがわかる。

かつなので、方程式（A6）の不等号が成立する。

方程式（A5）、（A6）及び（A7）を組み合わせると、
次式が得られる。

|e|²＝Ｅ（Ｎ＋１）≧２（Ｌ＋１）これで、第２の補助定理の証明を終える。

定理を証明するには、（１−Ｄ）^kで割り切れる多項
式ｅ（Ｄ）から始めた場合、ｅ（Ｄ）＝ｇ（Ｄ）（１−
Ｄ）で定義される多項式ｇ（Ｄ）は（１−Ｄ）^k-1で割
り切れることに留意されたい。補助定理１から、ｇ
（Ｄ）がその係数列で少なくともＫ−１回の符号が変わ
ることになる。補助定理２から、方程式（A1）で記述さ
れるように、ｅ（Ｄ）は、少なくとも2Kのユークリッド
重みをもたなければならないと結論できる。これで定理
の証明を終える。

次にこの定理を適用して、整合スペクトル・ヌル・ト
レリス・コードのコード化利得に対する境界を確認する
ことができる。

境界１については、Ｎ＝３の場合は、直接計算によっ
て確認される。Ｎ≧４の場合は、定理から直接導かれ
る。

境界２については、Ｎ＝3,4,5の場合は、直接計算に
よって確認される。Ｎ≧６の場合は、定理と、非コード
化２進（１−Ｄ）²チャネルの最小自由距離が４である
ことから導かれる。

境界３については、Ｎ＝3,4の場合は、直接計算によ
って確認される。Ｎ≧５の場合は、定理と、非コード化
２進拡張クラス４チャネルの最少自由距離が４であるこ
とから導かれる。

最後に、境界４は、定理から直接導かれる。

【図面の簡単な説明】

第１図は、本発明によるトレリス・コード化技術を利用
する記録システムの構成図である。第２図は、ゼロ周波数、ｆ＝０でスペクトル・ヌルをも
つ２進列の標準状態図である。第３図は、ナイキスト周波数の半分、すなわち、ｆ＝1/
2T（Ｔはコード記号周期）で、スペクトル・ヌルをもつ
２進列の標準状態図である。第４図は、ゼロ周波数（ｆ＝０）とナイキスト周波数
（ｆ＝1/2T）の半分で同時にスペクトル・ヌルをもつ２
進列の標準状態図である。第５図は、ダイコード（１−Ｄ）チャネル上のコード化
率2/3のトレリス・コードの検出器トレリスである。第６図は、（１−Ｄ）²チャネル上のコード化率2/3のト
レリス・コードの検出器トレリスである。第７図は、クラス１（１＋Ｄ）チャネル上のコード化率
2/3のトレリス・コードの検出器トレリスである。第８図は、クラス２（１＋Ｄ）²上のコード化率2/3のト
レリス・コードの検出器トレリスである。第９図は、「拡張」クラス４（１−Ｄ）（１＋Ｄ）²チ
ャネル上のコード化率2/3のトレリス・コードの検出器
トレリスの表である。第10図は、ダイコード（１−Ｄ）チャネル上のコード化
率が3/4のトレリス・コードの検出器トレリスである。第11図は、ダイコード（１−Ｄ）チャネル上のコード化
率が4/5のトレリス・コードの符号器構造である。第12図は、ダイコード（１−Ｄ）チャネル上のコード化
率が4/5のトレリス・コードの復号器構造である。第13図は、ダイコード（１−Ｄ）チャネル上のコード化
率が4/5のトレリス・コードの検出器トレリスである。 10……データ入力バス、11……符号器、12……パーシャ
ル・レスポンス・チャネル、13……検出器、14……復号
器、15……データ出力バス。

───────────────────────────────────────────────────── フロントページの続き (56)参考文献特開昭61−108226（ＪＰ，Ａ) 特開昭59−117847（ＪＰ，Ａ) 「データ通信」電子通信学会（Ｓ．58. ５．20）Ｐ．66−74

Claims

【特許請求の範囲】

【請求項１】所与の伝達関数を有するパーシャル・レス
ポンス・チャネルへの入力列をコード化する方法であっ
て、上記伝達関数がゼロになる周波数をそれぞれ決定し、上記入力列を、各上記周波数においてゼロのパワー・ス
ペクトル値を有する２進コード列にコード化する、コード化方法。
【請求項２】所与の伝達関数を有するパーシャル・レス
ポンス・チャネルへの入力列をコード化する方法であっ
て、上記伝達関数がゼロになる周波数をそれぞれ決定し、上記入力列を、各上記周波数においてゼロのパワー・ス
ペクトル値を有すると共にパワー・スペクトルの低次の
導関数もゼロになるコード列にコード化する、コード化方法。