JPH038604B2 - - Google Patents

Description

【発明の詳細な説明】 〔本発明の技術分野〕 本発明は有限状態の機械（ステート・マシー
ン）の記述及び記号持続時間パラメータによつて
制限された記号の流れを発生し、回復する事、さ
らに具体的にはデータ伝送、磁気記録等に見出さ
れる如き、パイロツト信号挿入に適した選択可能
な周波数ノツチ（谷部）を有するランレングス制
限符号に関する。

〔本発明の背景〕

米国特許第3689899号はデータがデイスク上に
記録され、ランレングス制限（RLL）符号技法
によつて現在のチヤンネルを介して信頼性をもつ
て伝送される際のデータ密度を増大する方法を説
明している。この技法は通常の２進データ流を可
変数の０によつて分離された１より成るシーケン
スに変換する。即ち、記録もしくは伝送中に記号
間干渉をなくするために、通常の２進データ流中
の各１は少なく共最小の量ｄに等しい個数の０に
よつて一番近い隣接１から分離されなければなら
ない。しかしながら０の個数は自己クロツキング
の目的に必要とされる最大数ｋを越えてはならな
い。この様な符号は（ｄ、ｋ）RLL符号と呼ば
れる。符号情報は可変長の符号群もしくは符号語
として処理される。符号語の長さは対応する原デ
ータ語の夫々の長さに対して一定の比率をなして
いる。さらにIBM Journal of Rearch and
Developement、1970年６月刊第376−83頁は２
進データ流が状態従属もしくは状態独立変換を使
用して一定比率もしくは可変率でRLL符号の形
にマツプ（map）される事を開示している。

IEEE Transaction on Information Tbeory、
Vol.IT26、1980年１月刊第1525頁の“Ａ
General Minimum Redundancy Source
Coding Algorithm”と題するGuazzo著の論文
にはハフマン解読器を使用して原データ流を可変
率のRLL記号流の形にマツプする方法を開示し
ている。原データ流の回復はRLL記号流をハフ
マン符号器に印加する事によつて行われている。
この様にして、ハフマン解読器は原データ流を
RLL流に伸長し、他方符号器がRLL流の圧縮に
よつて原データ流を回復している。

相対的にシフトされた有限なデータ流のビツト
対を算術的に組合せるために１対の繰返しを使用
するビツト流の圧縮方法はIBM Journal of
Research and Development、Vol.23、1979年３
月刊第149−62頁のRissanen and Langdonの論
文に開示されている。この方法は２つの繰返し方
法を使用している。１つの繰返は算術的に或るイ
ンクレメントを圧縮された符号流の保持された部
分に組合せている。第２の繰返しは圧縮された流
れの長さの増大を制御している。完全にするため
に、算術符号（コード）は確率型のものであるか
長さ型のものである事が認められる。例えば、こ
れ等の算術符号は米国特許第4122440号に開示さ
れている。

特開昭58−27238号には繰返し過程を使用して
データ流から一定率のRLL符号を発生し、又逆
に回復する方法及び装置を説明している。この方
法の利点は長さ型算術解読器がデータ流から
RLL流への１対１マツピング記号流に制限され
ていて、対応する算術符号器がRLL流からデー
タ流方向のオンツーマツピング記号流に制限され
る場合に、繰返し符号動作が可能とされ、一定比
率が保持される点にある。

制限的なチヤンネル環境としては、デイスクも
しくはデイスクの如き可動磁性媒体上の情報の記
録が含まれる。これ等の可動磁性媒体上に情報を
記録するには、記録媒体のスペクトル特性と両立
可能なパターンに外部情報源からのビツト流を変
換する事を必要とする。制限チヤンネルもしくは
記録符号のスペクトル特性は記録された１及び０
の分布の関数である。この理由のために、或るビ
ツト流の組合せを含めたり排除したりする事が望
まれる。この特開昭58−27238号は周知の圧縮技
法を逆にする事を前提としている。このためには
情報は圧縮システムによつて変換されたものとし
て特徴付けられる必要がある。即ち情報源からビ
ツト流がDASD記録チヤンネルに印加される場合
には算術解読器に導入される。解読器に関する限
り、このビツト流は圧縮ビツト流として取扱われ
る。実際に解読器はビツト流の長さを伸長する。
この処理によつて符号は推定されたチヤンネルの
スペクトル特性に整合される。従つて上記
Gaazzo著の論文は可変率のRLL流を直結によつ
て発生するのに反転ハフマン解読器／符号器対の
使用を開示しているが、上記特開昭58−27238号
は一定率RLL符号を完全にし、表示可能性を保
持するために適切な変換方向の１対１及びオンツ
ーマツピングの使用を開示している。

米国特許第4328535号はデータ・クロツク周波
数の１部から周波数０（null）を得る望ましさを
説明した後、これを制限すべき周波数のフーリエ
成分のランニング和を制限する事によつて達成し
ている。又この特許は連続的に解読器の出力をモ
ニタし、その関数として変換の選択を再調節する
ことによる適応性調節を開示している。

〔本発明の概要〕

本発明は、符号のスペクトルが選択された周波
数において谷部（ノツチ）を示すようにデータ流
を周波数帯域制限された状態で符号化する方法で
あつて、各データ流をランレングス制限（RLL）
記号流の選択された１つに１対１マツピングし、
各選択されたランレングス制限記号流をNRZ（ノ
ン・リターン・ツー・ゼロ）表示に変換すること
を特徴とするものである。符号からのデータ流の
復原は、NRZ表示をRLL記号流に変換し、各
RLL記号流をデータ流にオンツー（ONTO）マ
ツプすることにより行われる。上記１対１マツピ
ングは、例えば、一定率長さ型繰返し算術的符号
化を含み、この符号化は、格子型有限状態遷移符
号化空間の各遷移にRLL記号を割当て、遷移を
所定のパスに制限することを含む。より具体的に
述べると、各記号がクロツク周波数ｆで発生する
データ記号流をスペクトルがｆ／2k（ｋ＝１、
２、…）において谷部（ノツチ）を有する一定率
ランレングス制限記号流のNRZ表示に変換する
本発明による実施例は、各遷移がRLL記号、シ
フト量（SA）及び試験的被加数（TA）で示さ
れる状態遷移テーブルを形成記憶し（各遷移ベク
トルのRLL記号はｆ／2kにおいてNRZ表示に谷
部（ノツチ）が保存されるように選択される）、
直前に符号化されたRLL記号及び状態遷移によ
つてインデツクスされたときにテーブルからTA
及びSAを選択することにより各RLLを符号化
し、データ流とTAデイジツトとを大きいものか
ら順次比較し、TAがデータ流の大きさより大き
くなるまで差が最小となる方向にデータ流をSA
だけ対シフトする。

本発明による方法はデータ伝送、磁気記録等に
見出される如き、パイロツト信号の挿入に適した
選択可能な周波数ノツチ（谷部）を有するランレ
ングス制限符号を発生する方法である。ｆをビツ
ト率としてｆ／Ｎに周波数ノツチを有するｋ個の
NRZ符号流は上記ソース流にｋ回ビツトをイン
タリーブする事によつてｆ／Nkに周波数ノツチ
を有する流れに変換され得る。しかしながらこの
ｋ回のインタリーブは結果として得られる符号流
中のどこで極性の遷移が生ずるかについての制御
が失われる事によつて（ｄ、ｋ）RLLの制限を
破壊する。ｆ／２にノツチを有する符号のための
ｋ回のインタリーブをｋ次元の有限状態遷移図と
して書換える事によつて、状態の遷移には伸長記
号（多重ビツト）のラベルが付される。即ち、状
態遷移は＋１もしくは−１のラベルが付されるの
でなく、多重ビツトのラベルが付される。定めら
れた状態遷移経路に沿つて、状態から状態へと移
動させる事によつて発生さるパターンはｆ／2k
にあるノツチの保存を保証し、長さ型算術的流れ
の符号化に適したRLL文字の発生及び回復を可
能とする。従つて、本発明は格子状の有限状態遷
移図中の遷移に許容されているランレングスに対
応する伸長記号のラベルを付した後、加数（被加
数）の表を発生する算術符号化技法が実際に
RLL符号化／解読を実行するのに使用される。

RLL符号化データ流のNRZ表示の発生には、
有限状態符号化遷移空間の状態遷移に対して
RLL記号が割当てられた、長さ型算術的繰返し
RLL符号器が使用される。経路、従つて許容さ
れるRLL記号流の組を制限する事によつて、
NRZ表示のスペクトルにおける選択可能な周波
数ノツチが保存される。データの回復はこの過程
の論理的双対性によつて得られる。同様に、もし
各々ｆ／ｎに周波数ノツチを有するｋ個のNRz
のソース符号流がｋ回インタリーブされるなら
ば、NRzビツト流はｆ／knヘルツにノツチを有
する周波数スペクトルを提示する。これはチヤン
ネル符号化の場合はデータ流間で１対１マツピン
グを行つてすべての可能なRLL記号流の部分集
合の形にすること及びチヤンネル解読の場合はオ
ーツーマツピングによつて現わされる。

重要な事は、米国特許第4328535号は解読器の
出力を連続的にモニタし、その関数として変換の
再選択を再調節する事による適応性調節法を開示
しているが、本発明の方法は、ｋ個の因子が格子
状の有限状態遷移図（FSTD）の次元によつての
み制限されるので、（ｄ、ｋ）制限に直交する
ｆ／2kノツチングが可能な点にある。即ち、選
択的にノツチ可能な符号が周知の型の制限チヤン
ネル解読器の表の修正だけで発生される。

〔好ましい実施例の説明、工業的応用及び予備知識〕

上述の如く、制限されたチヤンネル符号化は結
果として得られるスペクトルを一つの実用的なも
のに変更するための１及び０のパターンを挿入す
る事によつてソース・ビツト流を伸長する事を含
む。この様な伸長符号を発生するための新らしい
技法の中には上記特開昭58−27238号に開示され
ている繰返し法を含む。従来技法では０もしくは
１のラベルが遷移に付されるが、算術符号化法で
は多重のビツトのラベルが付される事を理解され
たい。

以下の説明では、(1)周波数ノツチ位置の決定、
(2)ｆ／ｎの関数としての格子の次元の決定、(3)実
際の実行が（２、７）の如き（ｄ、ｋ）制限によ
つて規定される如きより高次元の格子の頂点を取
出して、これ等を伸長記号によつてラベルの付さ
れた遷移で結合する算術符号の発生が説明され
る。最後に遷移図に基づく、特定の符号化／解読
様式が述べられる。

六方格子の形のFSTDはＦ／６にノツチを有す
るデータ流を発生する事が知られている。こゝで
FSTDが１つのランレングス制限によつてどの様
に結合されるかについての疑問が生ずる。遷移に
は１もしくは０（或いは＋１、−１）だけのラベル
が付されるのでなく多重ビツト記号のラベルが付
される。これ等の遷移に従つて状態間を移動する
事によつてパターンが発生される。多重ビツトが
発生されるのはその様に予定されているからであ
る。これによつて、RLLの制限が保証される。
即ち（２、７）制限の場合には、ランは001、…、
00000001となる。次にノツチ周波数スペクトルの
特性について説明する。

上述の特開昭58−27238号には制限が有限状態
機械に従つて説明される制限チヤンネルのための
一定率、長さ型算術符号を使用する方法及び装置
が開示されている。

ｋ回のインタリーブ及び周波数ノツチ 第１図を参照するに、経路１０１に印加される
データ・ビツト流をインタリーブ符号化するｋ個
のランレングス制限符号器１０３，１０５，…１
０７が示されている。原データ流を抽出するため
にインタリーブされたRLLビツト流を分離して
解読するためのｋ個のRLL解読器２０３，２０
５，…２０７が同様に示されている。この実施例
は各々ｆ／ｎにスペクトル・ノツチを有するｋ個
の符号流をスイツチ１０９を介してｋ回互にイン
タリーブしてｆ／knにスペクトル・ノツチを有
する符号流を発生するものである。成分の符号流
のランレングス制限は一般にインタリーブによつ
て保存されない。ビツトに応答する各RLL符号
器は可変長RLL流を割当てる。符号器１，２，
ｋの夫々の出力はインタリーブスイツチ１１１に
よりサンプルされｋ個のチヤンネルのための
NRz検出器１１３に印加される。これによつて
ビツト流は適切なアナログ波形へ変換され、この
波形の電圧／電流の大きさ間の縁もしくは遷移が
テープもしくはデイスクの如き移動する磁気媒体
上に磁束のスポツトの記録を可能とする。勿論記
録チヤンネル以外の伝送路にも適切なデイジタル
−アナログ変換器が与えられ得る。媒体もしくは
制限チヤンネルからの回復はアナログ変動をデイ
ジタル・ビツト流に変換するチヤンネルNRz検
出器２１３によつている。次にこの流れはスイツ
チ２１１によつて分離され、対応するRLL解読
器１，２，…ｋ（２０３，２０５，２０７）に印
加されている。解読器の出力は次いでスイツチ２
０９によつてインタリーブされ、出力経路２０１
に印加されている。

〔ｋ回のインタリーブのフーリエ解析〕

制限チヤンネル・ビツト流の代表的な振幅対周
波数スペクトルは第２Ａ図及び第２Ｂ図に示され
ている。第２Ａ図のスペクトルは、ｆをカツト・
オフ周波数としてｆ／２にノツチ（谷部）Ｎ１を
有する。第２Ｂ図のスペクトルはｋを有理数とし
て、ｆ／k2（すなわちｆ／４と3f／４）に２つの
ノツチＮ２及びＮ３を有する。なお、第２Ａ図及
び第２Ｂ図のスペクトルが０となるのはｆ＝1024
Hzであるｆ／knにノツチを導入する効果は次の
如く説明される。ｙ及びｚを複素数として、次の
関係が成立つ。

｜ｙ＋ｚ｜｜ｙ｜＋｜ｚ｜ (1) これは複素平面上の三角形の任意の辺の長さは
残りの２辺の長さの和よりも小さいという公理か
ら来ている。

第３図を参照するに符号流ｃ（０）、ｃ(1)、ｃ(2)
…及びｄ（０）、ｄ(1)、ｄ(2)…は周波数ｆ／ｎにノ
ツチを有する。即ち、周波数ｆ／ｎにおけるフー
リエ成分Ｓ（ｆ／ｎ；Ｎ）は次式を満足する。

｜_N 〓^k=0 ｃ(k)e^-j2〓^k/n｜Ｂ 及び (2) ｜_N 〓^k=0 ｄ(k)e^-j2〓^k/n｜Ｂ ここでｃ及びｄの符号流が互にインタリーブさ
されると、結果の2N＋２記号迄の流れｃ（０）、
ｄ（０）、ｃ(1)、ｄ(1)、ｃ(2)、ｄ(2)…は次式によつ
て与えられる如く周波数ｆ／2nにおけるフーリ
エ成分Ｓ（ｆ／2n；2N＋１）を有する。

便宜上、Ｓ（ｆ／2n；2N＋１）をＳ（ｆ／2n）
と表わす。モジユラス｜Ｓ（ｆ／2n）｜を境界づ
けるために、ｙを式(3)中の最初の和、ｚを第２の
和として上記の三角形の不等式が使用される。式
(1)から、 右の項のe^-j2〓^/2nは和中のすべての項から因数分
解によつて外に出されるが、これはｘ及びｗを複
素数として ｜ｘ・ｗ｜＝｜ｘ｜・｜ｗ｜ が成立つという事実を使用している。

e^-j2〓^/2nのモジユラスは１であるから、式(2)及び
(4)からＳ（ｆ／2n）のモジユラスは次の様に境界
づけられる事がわかる。

｜Ｓ（ｆ／2n）｜Ｂ＋Ｂ＝2B (5) 但しＢは定数。

式(2)はすべてのＮに対して成立つので、式(5)も
すべてのＮに対して成立ち、互にインタリーブさ
れた符号流がｆ／2nにノツチを有する事を意味
している。

より高次のインタリーブの場合には、上述の三
角形の不等式を３以上の複素数に一般化するため
に数学的帰納法が使用される。即ち ｜ｚ(1)＋ｚ(2)＋…＋ｚ(k)｜｜
ｚ(1)｜＋｜ｚ(2)｜＋…＋｜ｚ(k)｜ 証明により、Ｂによつて絶対値が境界づけられ
たｆ／ｎのフーリエ成分をおのおの有するｋ個の
流れがｋ回互にインタリーブされると、合併され
た流れはkBによつて境界づけられたｆ／knのフ
ーリエ成分を有する。

より多い周波数ノツチを有する場合のフーリエ解
析 上述の如きｆ／ｎに周波数ノツチを有する符号
流のｋ回のインタリーブはしばしばｆ／kn以外
の個所にもノツチを生ずる。これはフイルタの使
用を必要とする様な問題を生じない。この事は合
併された流はｆ／kn以外の周波数ではほとんど
エネルギを有さない事を示している。

これ等のノツチはむしろ利点と考える事が出来
る。即ちこれ等のノツチ周波数に集中する追加の
サーボもしくは他の信号は（丁度ｆ／knにある
サーボ信号がデータから分離される様に）データ
信号から容易に分離される。

これ等の余分のノツチは次の様に説明される。
Ｓ（ｆ／ｎ；Ｎ）を上述の如く符号流ｃ（０）、ｃ
(1)、…ｃ（Ｎ）に対するｆ／ｎのフーリエ成分を
与える和とする。ｆ／ｎにあるノツチは符号流が
次の式を満足する事を確実にする事によつて保証
される。

｜Ｓ（ｆ／ｎ；Ｎ）｜＝｜ 〓^a ｃ(k)e^-j2〓^k/n｜Ｂ (6) こゝでＢは或る定数、すべてのＮは０より大き
いとする。

Ｓ（（ｎ−１）ｆ／ｎ；Ｎ）のモジユラスの表現
形式 ｜Ｓ（（ｎ−１）ｆ／ｎ；Ｎ）｜
＝｜（；）｜Ｂ を調らべ、 (1) 或る複素数のモジユラスはその共役複素数の
モジユラスに等しい。

(2) 複素数の積に共役複素数は各因数の共役複素
数の積に等しい 事を考慮に入れて、上述の如くしてｆ／ｎに発生
されたノツチは常に（ｎ−１）ｆ／ｎにノツチを
伴う事が明らかである。これによつてｆ／４のノ
ツチに加えて3f／４にもノツチがある事の説明が
出来る。この事はkf／ｎにあるノツチは（ｎ−
ｋ）ｆ／ｎにノツチを伴う事を示している。

一般により高次のインタリーブはさらに多くの
ノツチを生ずるが、これは簡単な複素数解析によ
つて容易に説明され得る。例えば周波数ｆ／６に
ノツチを有する２つの符合源を互にインタリーブ
する事によつて、予期される如くｆ／12及び
11f／12に周波数ノツチを有するが同様に5f／12
及び7f／12にもノツチを有する合併符合流を生ず
る。

5f／12のノツチの発生を生ずるためには、上述
の式(3)におけるが如き合併符号流のためのＳ
（5f／12）のモジユラスの式を考慮されたい。

次の事実e^j2〓^k/n＝e^j2〓^r/nここでｒ≡ｋモジユロｎ
を使用すると、最初の和はＳ（11f／12）における
対応する和と同じであり、第２の和はＳ（11f／
12）における対応する和にe^-j2〓

Claims (1)

1. 【特許請求の範囲】 １ 符号化したデータ表現が所望の周波数におい
   て谷部を有するスペクトルを呈するようにデータ
   流を周波数帯域制限符号化する方法において、 各遷移にRLL記号が割り当てられて遷移の系
   列がRLL記号流に関連付けられ、さらに上記遷
   移が所定のパスに制限されて上記RLL記号流の
   各々のNRZ表現のスペクトルが所望の周波数で
   谷部を有するように選択された格子型有限状態遷
   移符号化空間を準備するステツプと、 上記格子型有限状態遷移符号化空間に基づいて
   算術符号化によりデータ流をRLL記号流に一対
   一にマツピングするステツプと、 上記マツピングで得たRLL記号流をNRZ表現
   に変換するステツプとを有することを特徴とする
   データ流符号化方法。