ランレングス制限

ランレングス制限またはRLLコーディングは、帯域幅制限のある通信チャネルを介して任意のデータを送信するために使用されるラインコーディング技術です。RLL コードは、 m、n、d、k の4 つの主要なパラメータによって定義されます。最初の 2 つ、m / n はコードの速度を示し、残りの 2 つは連続する 1 の間にある 0 の最小数dと最大数k を指定します。これは、固定された記録ヘッドを媒体が通過する通信システムとストレージシステムの両方で使用されます。^[1]

具体的には、RLL は、信号が変化しない繰り返しビットのストレッチ (ラン) の長さを制限します。ランが長すぎるとクロック回復が難しくなり、短すぎると高周波が通信チャネルによって減衰される可能性があります。データを変調することにより、RLLは、保存されたデータのデコードにおけるタイミングの不確実性を低減します。タイミングの不確実性があると、データを読み戻すときにビットが誤って挿入または削除される可能性があります。このメカニズムにより、ビット間の境界を常に正確に検出できる (ビット スリップを防ぐ) と同時に、メディアを効率的に使用して、指定されたスペースに最大量のデータを確実に保存できます。

初期のディスクドライブでは、RLL (0,1) FM コード、その後 RLL (1,3) MFM コードなどの非常に単純なエンコード方式が使用されていました。これらのエンコード方式は、1980 年代半ばまでハードディスクドライブで広く使用され、現在でもCD、DVD、MD、Hi-MD、Blu-rayなどのデジタル光ディスクで使用されています。1990 年代初頭までに、より高密度の RLL (2,7) および RLL (1,7) コードは、ハードディスクの事実上の業界標準となりました。

ハードディスク ドライブでは、情報はディスク上の磁場の方向の変化によって表され、磁気メディアでは、再生出力は磁束遷移の密度に比例します。コンピューターでは、情報はワイヤの電圧によって表されます。定義されたグランド レベルに対してワイヤに電圧がない場合はバイナリ ゼロになり、グランドに対してワイヤに正の電圧がある場合はバイナリ 1 になります。一方、磁気メディアは常に磁束 (「北」極または「南」極) を運びます。磁場をバイナリ データに変換するには、何らかのエンコード方法を使用して両者を変換する必要があります。

最も単純な実用的なコードの 1 つである、修正非ゼロ復帰反転 ( NRZI ) は、単に 1 を磁気極性遷移 (「磁束反転」とも呼ばれる) としてエンコードし、0 を遷移なしとしてエンコードします。ディスクが一定速度で回転すると、各ビットには、そのビットを表す磁気信号に対して等しい時間間隔 (「データ ウィンドウ」) が与えられ、磁束反転 (ある場合) はこのウィンドウの開始時に発生します。(注: 古いハード ディスクでは、ディスク全体のデータ ウィンドウとして 1 つの固定時間長が使用されていましたが、最近のディスクはより複雑です。詳細については、ゾーン ビット記録を参照してください。)

この方法はそれほど単純ではありません。再生出力は 1 の密度に比例するため、ゼロが長く続くと再生出力がまったくなくなるからです。

簡単な例として、データ ウィンドウが 1 ns (1 ナノ秒、つまり 10 億分の 1 秒) のバイナリ パターン 101 を考えてみましょう。これは、ディスク上に変更として保存され、その後変更なし、そして別の変更が続きます。前の磁気極性がすでに正だった場合、結果のパターンは次のようになります: −−+。値 255、つまりバイナリがすべて 1 の場合は、−+−+−+−+ または +−+−+−+− と書き込まれます。ゼロ バイトは、++++++++ または −−−−−−−− と書き込まれます。ゼロの 512 バイト セクターは、同じ極性を持つ 4096 個の連続ビットとして書き込まれます。

ディスク ドライブは物理的なハードウェアであるため、モーター速度の変化やディスク プラッターの熱膨張により、ドライブの回転速度がわずかに変化することがあります。フロッピー ディスクの物理メディアが変形してタイミング エラーが大きくなった場合もあり、コントローラ自体のタイミング回路の速度がわずかに変化することがあります。問題は、ゼロの長い文字列では、ディスク ドライブのコントローラが読み取りヘッドの正確な位置を把握できず、したがってゼロがいくつあるかを正確に把握できないことです。実際のフロッピー ドライブよりも正確な 0.1% の速度変化でも、4096 ビットのデータ ストリームに 4 ビットが追加されたか、または 4096 ビットのデータ ストリームから 4 ビットが削除される可能性があります。何らかの同期とエラー修正を行わないと、データは完全に使用できなくなります。

もう 1 つの問題は、磁気メディア自体の制限によるものです。つまり、一定量のスペースに書き込める極性の変化の数は限られているため、連続して書き込める数にも上限があり、これは線速度とヘッド ギャップに依存します。

この問題を防ぐため、データは単一のバイナリ値の長い繰り返しが発生しないようにコード化されます。連続して書き込まれるゼロの数を最大kに制限することで、ドライブ コントローラの同期を維持できます。1 行に書き込まれるゼロの数を、ゼロ間の最小dに制限することで、極性変更の全体的な頻度が減り、ドライブは同じ量のスペースにより多くのデータを保存できるようになり、同じ量のデータでより小さなパッケージになるか、同じサイズのパッケージでより多くのストレージが実現します。

磁気ディスクに記録するために使用されるすべてのコードは、遷移のない実行の長さが制限されているため、技術的には RLL コードとして特徴付けられます。最も初期の最も単純なバリアントには、修正周波数変調(MFM) などの特定の名前が付けられており、「RLL」という名前は、そのような特定の名前が付けられていないより複雑なバリアントに対してのみ一般的に使用されますが、技術的にはその用語はすべてに適用されます。

この最も単純なバージョン以外で、ハード ドライブで最初に使用された RLL コードは RLL (2,7) で、IBM のエンジニアによって開発され、1979 年に IBM 3370 DASDで初めて商用使用されました( ^{[2] [3] [4] 4300 シリーズ}メインフレーム用)。1980 年代後半には、PCハード ディスクで RLL 本来 (MFM などの独自の固有名が付けられたものよりも複雑なバリエーション) が使用され始めました。RLL コードは、1980 年以降、光ディスク記録の実践においてほぼ普遍的に使用されています。民生用電子機器では、EFM コード(レート = 8/17、d  = 2、k = 10) などの RLL がコンパクト ディスク(CD) やミニディスク(MD) で採用され、EFMPlusコード (レート = 8/16、d  = 2、k  = 10) はDVDで使用されています。パラメーターdとk は、許容される最小および最大のラン レングスです。ストレージ技術の詳細については、この記事で引用されている参考文献が役立ちます。^{[5] [6]}

一般的に、ランレングスは信号が変化しないビット数です。ビット 1 のランレングスが 3 の場合、シーケンス 111 を表します。たとえば、ディスク上の磁気分極のパターンは +−−−−++−−−++++++ で、ランの長さは 1、4、2、3、6 です。ただし、ランレングス制限コーディング用語では NRZI エンコードが想定されているため、1 ビットは変化を示し、0 ビットは変化がないことを示します。上記のシーケンスは 11000101001000001 と表現され、0 ビットのランのみがカウントされます。

少々紛らわしいですが、ランレングスは隣接するゼロ間のゼロの数（前述の 0、3、1、2、5）であり、信号が実際に変化しないビット数より 1 少ない数です。ランレングス制限シーケンスは、シーケンスで発生する可能性のある最小および最大のゼロビットランレングスを規定するdとk という2 つのパラメータによって特徴付けられます。したがって、RLL コードは一般に ( d、k ) RLLと指定されます（例：(1,3) RLL）。

エンコードされた形式では、「1」ビットは磁束遷移を示し、「0」はディスク上の磁場がその時間間隔で変化しないことを示します。

一般的に、「RLL コード」という用語は、より複雑なエンコードを指すために使用されますが、差動マンチェスターエンコードとも呼ばれる元の周波数変調コードは、単純なレート 1/2 RLL コードとして考えることができます。追加された 1 ビットはクロック ビットと呼ばれます。

例：

データ: 0 0 1 0 1 1 0 1 0 0 0 1 1 0
エンコード: 1010111011111011101010111110
時計: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

最大ランレングスを2つの隣接する0ビットに拡張することで、データレートを4/5に向上できます。これは、IBMグループコード化記録の元のバリエーションです。

可能な場合（16 個のコードのうち 11 個）、ビット パターンは、aabcdの補数を前に付けてエンコードされます: 。これが規則の 1 つに違反する 5 つのケース（または）では、11 で始まるコードに置き換えられます（、ただしe = a ∨ d）。 aabcd000dab0011bea

例：

データ: 0010 1101 0001 1000
エンコード: 1001001101111111010

(0,2) RLL の定義を満たすには、各 5 ビット コードに連続する 0 が 2 つ以上含まれていないだけでは不十分であり、5 ビット コードの任意のペアを順番に組み合わせた場合に連続する 0 が 2 つ以上含まれていないことも必要であることに注意してください。つまり、任意の 2 つのコードについて、最初のコードの最後の 1 ビットと 2 番目のコードの最初の 1 ビットの間に 0 が 2 つ以上あってはいけません。これが必要なのは、どの RLL コードでも、ランレングス制限 (この場合は 0 と 2) が、プレーン データ ビットの離散シーケンスを表すコンポーネントだけでなく、変調ビットストリーム全体に適用されるためです。 (この規則は、入力データが任意のビット シーケンスである可能性があるため、例外なく任意のコード ペアに当てはまります。) 上記の IBM GCR コードは、この条件を満たしています。これは、任意の 5 ビット コードの先頭のゼロの最大ラン レングスが 1 であり、同様に任意のコードの末尾のゼロの最大ラン レングスが 1 であるため、隣接するコード間の接続部で合計ラン レングスが 2 になるからです。(コード間で発生する最大ラン レングスの例は、上記の例で確認できます。この例では、データ "0010" のコードはゼロで終わり、次のデータ "1101" のコードはゼロで始まり、これら 2 つの 5 ビット コードの接続部で 2 つのゼロのランが形成されます。)

修正周波数変調は、その特殊な特性により、任意のビット ストリームの 2 倍の密度で磁気媒体にビットを書き込むことができるため、興味深くなり始めています。読み取り機器が磁束遷移を検出できるほど磁束遷移が時間的に近接できる範囲には制限があり、これにより媒体にビットをどれだけ近接して記録できるかが制限されます。最悪の場合、任意のビット ストリームでは、連続する 2 つのビット ストリームがあり、時間的に連続する 2 つの磁束遷移が生成されるため、ビットは、リーダーが磁束遷移を検出できるように十分な時間間隔を空けて配置する必要があります。ただし、このコードでは、d  = 1、つまり、2 つの 1 の間には最低 1 つのゼロがあるという制約が課せられます。つまり、最悪の場合、磁束遷移は 2 ビット時間離れているため、リーダーの能力を超えずに、ビットを任意のビット ストリームの 2 倍に近づけることができます。

この 2 倍の記録密度は、このコードの 1/2 コーディング レート (実際の情報 1 ビットを表すのに 2 ビット必要) を補正し、レート 1 コードと同等にします。

エンコーディングは FM エンコーディングと非常に似ています。

ここで、「x」はストリームの以前にエンコードされたビットの補数です。

クロック ビットが常に 1 ではないことを除けば、これは FM テーブルと同じであり、このコードの名前の由来となっています。挿入されたクロック ビットは、2 つの 0 データ ビットの間を除いて 0 です。

前のn-1ビットと組み合わせると、各データ ビットnの結果のエンコード テーブルは実質的に次のようになります。

例：

データ: 0 0 1 0 1 1 0 1 0 0 0 1 1 0
エンコード: x010010001010001001010010100
時計: x 1 0 0 0 0 0 0 0 1 1 0 0 0

(1,7) RLLは2ビットのデータをディスク上の3ビットにマッピングし、エンコードは2ビットまたは4ビットのグループで行われます。エンコードのルールは次のとおりです。( x、y )は(NOT x、x AND y、 NOT y )になりますが、( x、 0、 0、y )は(NOT x、x AND y、 NOT y、 0、 0、 0)になります。^[7] 下の表に従ってエンコードする場合、最長(表の最後)の一致を使用する必要があります。これらは、前のルールを適用するとコード制約に違反する状況を処理する例外です。

例：

データ: 0 0 1 0 1 1 0 1 0 0 0 1 1 0
エンコード: 101 001 010 100 100 000 001

(2,7) RLL はレート1 ⁄ 2 のコードで、 MFM と同様にnビットのデータをディスク上の 2 nビットにマッピングしますが、最小ランレングスが 50% 長くなるため (2 ビット時間ではなく 3 ビット時間)、ビットの書き込み速度が速くなり、有効データ密度が 50% 高くなります。エンコードは 2、3、または 4 ビットのグループで行われます。

ウエスタンデジタル WD5010A、WD5011A、WD50C12

シーゲイト ST11R、IBM

パースターシステムズADRC

エンコードされた形式は最大 4 ビットで始まり、最大 3 ビットのゼロで終了し、最大ラン長は 7 になります。

例：

データ: 1 1 0 1 1 0 0 1 1
エンコード: 1000 001000 00001000

HHH(1,13) コードは、16 MB/s IrDA VFIR 物理層で使用するために 3 人の IBM 研究者 (Hirt、Hassner、Heise) によって開発されたレート 2/3 コードです。^[8]磁気エンコーディングとは異なり、これは赤外線送信機用に設計されており、0 ビットは「オフ」、1 ビットは「オン」を表します。1 ビットは送信に多くの電力を消費するため、1 ビットの密度を 50% 未満に制限するように設計されています。特に、これは (1,13|5) RLL コードであり、最後の 5 は、最大 5 つの連続する「10」ビット ペアが存在するという追加の制約を示します。

最初の 8 行は、標準の (1,7)-RLL コードを表します。追加の 6 つの例外により、ゼロの最大連続数が 13 に増加します (有効なパターンは 100 000 000 000 001 で、これは 10 11 10 11 の後に 01 が続くことを表します) が、平均 1 の最大密度は1 ⁄ 3に制限されます。1 と 0 のペアの最長連続数は 000 101 010 101 000 です。

このコードは、 1 の密度を1 ⁄ 12から1 ⁄ 3の間に制限し、平均は 25.8% になります。

例えば、ビットシーケンス10110010を異なるエンコードでエンコードしてみましょう。

磁気テープには、1 インチあたり最大 3200 の磁束反転を含めることができるとします。修正周波数変調、または (1,3) RLL エンコードでは、各データ ビットをテープ上に 2 ビットとして保存しますが、1 (磁束反転) ビットの間には必ず 1 つの 0 (磁束反転なし) ビットがあるため、テープ上に 1 インチあたり 6400 エンコード ビット、つまり 1 インチあたり 3200 データ ビットを保存できます。(1,7) RLL エンコードでも、テープ上に 1 インチあたり 6400 エンコード ビットを保存できますが、2 つのデータ ビットを保存するには 3 つのエンコード ビットしか必要ないため、1 インチあたり 4267 データ ビットになります。(2,7) RLL エンコードでは、各データ ビットを保存するために 2 つのエンコード ビットが必要ですが、1 ビットの間には必ず 2 つの 0 ビットがあるため、テープ上に 1 インチあたり 9600 エンコード ビット、つまり 1 インチあたり 4800 データ ビットを保存できます。

ハード ドライブの磁束反転密度は大幅に高くなりますが、異なるエンコーディング システムを使用することで、ストレージ密度も同様に向上します。

• 8b/10bエンコーディング
• ビットスリップ
• 8 対 14 変調と EFMplus は、それぞれ CD と DVD で使用される DC フリー (2,10) RLL コードです。
• エラー訂正コード
• ラインコード
• 変調
• 物理層
• ＰＲＭＬ
• ランレングス符号化
• 自己同期コードとビット同期
• ソースコーディング

• デジタル磁気テープ録音