媒体に書込まれるべきデータの符号語を符号化および復号化するための方法
【課題】データのランレングス制限（run-lengthlimited）（ＲＬＬ）コード化に向けられる方法、機器およびシステムを提供する。
【解決手段】実現例では、ｋを超えない０のランレングスを有する連結可能なＲＬＬ符号が任意の比率Ｎ／（Ｎ＋１）について構築される。符号率が増加すると、ｋの値は多くの他の符号の値よりもゆっくりと最小値から離れる。さらに、ｋビットのランレングスの発生は、２つの符号語の接合部でしか発生しない。この特性によって、符号はＬＤＰＣチャネルなどのパリティビット挿入アプリケーションに理想的なものになる。実現例では、表の中の違反シーケンスのビットアドレスを符号語の初めに配置し、表項目が配置される位置を占めているユーザデータが違反シーケンスの位置に移動される。これは、繰返し行なわれ、違反シーケンスがアドレステーブル自体の内部にある場合に備える方法で行なわれる。
【解決手段】実現例では、ｋを超えない０のランレングスを有する連結可能なＲＬＬ符号が任意の比率Ｎ／（Ｎ＋１）について構築される。符号率が増加すると、ｋの値は多くの他の符号の値よりもゆっくりと最小値から離れる。さらに、ｋビットのランレングスの発生は、２つの符号語の接合部でしか発生しない。この特性によって、符号はＬＤＰＣチャネルなどのパリティビット挿入アプリケーションに理想的なものになる。実現例では、表の中の違反シーケンスのビットアドレスを符号語の初めに配置し、表項目が配置される位置を占めているユーザデータが違反シーケンスの位置に移動される。これは、繰返し行なわれ、違反シーケンスがアドレステーブル自体の内部にある場合に備える方法で行なわれる。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野
この発明は概してデータの符号化および復号化に関する。
【背景技術】
【０００２】
背景
磁気記憶チャネルでは、タイミング回復システムの頻繁な更新を保証するためにデータストリームの中の連続する０の数を制限することが望ましい。これは、ランレングス制限と呼ばれ、たとえばデータを「Ｎ」ビットのブロックに分割し、次いで、Ｎ＋１ビットのブロックも連結されたブロックの対も所望の数「ｋ」以上の連続する０を持たないように、選択されたＮ＋１ビットのブロック上に各ブロックをマッピングすることによって達成され得る。典型的な符号には、８ビットの各ブロックを、９ビット（「８／９符号」）および「１６／１７」、「２４／２５」、「３２／３３」などのランレングス制限（run-length-limited）（「ＲＬＬ」）ブロックと置換える符号が含まれる。割合Ｎ／（Ｎ＋１）は、符号の「比率」と呼ばれる。もちろん、コード化率が異なるＲＬＬスキームも存在する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
多くの先行技術の方法の不利な点は、先行技術の方法がルックアップテーブルによって定義され、そのためコストおよび電力消費とともに符号化および復号化の複雑さが符号長に伴って指数関数的に増大することである。別の不利な点は、大半の先行技術の方法がその場その場での処理であり、各比率ごとに符号を開発するために異なるアプローチが必要であることである。先行技術の方法の中には、順次論理を使用して効率的に符号化および復号化でき、したがって複雑さの問題に部分的に対処しているものもある。しかしながら、これらの先行技術の方法は所与の比率に適合させるために相当な創意工夫が必要であることが多く、これらの先行技術の方法を使用して構築され得る符号がない比率が存在する。これは問題である。なぜなら、記録技術が（リード−ソロモン符号などの）バイト指向の誤り訂正から離れて（ターボおよび低密度パリティチェック（low density parity check）（「ＬＤＰＣ」）符号などの）軟復号化方法に移ると、さまざまな比率を有するＲＬＬ符号が必要になるためである。さらに、長い符号を構築するためのいくつかの先行技術の方法が考案されており、これは、符号化されていないブロックを、より短い、ＲＬＬ符号化された語からのブロックで挟むことを伴う。これらの技術は、ある意味では一般的であるが、最適状態に大幅に及ばないｋの値を生じさせることが多い。
【０００４】
上述を鑑みて、効率的なエンコーダおよびデコーダを利用し、ｋの値が最適に近い符号を生成し、任意の所望の符号率に容易に適合する、ＲＬＬ符号を構築するための一般的な方法が当該技術分野において必要である。
【課題を解決するための手段】
【０００５】
概要
範囲を限定するのではなく例示的および例証的であるように意図されるシステム、機器および方法に関連して、以下の実施例およびその局面を記載し、示す。さまざまな実施例において、上述の問題を１つ以上低減または解消した。
【０００６】
記載される実施例は、データのランレングス制限（ＲＬＬ）コード化に向けられる方法
、機器およびシステムを提供する。一実現例では、ｋを超えない０のランレングスを有する連結可能なＲＬＬ符号が任意の比率Ｎ／（Ｎ＋１）について構築され、ここでＮ≦２k-2＋ｋ-1である。符号率が増加すると、ｋの値は多くの他の符号の値よりもゆっくりと最小値から離れる。さらに、ｋビットのランレングスの発生は、２つの符号語の接合部でしか発生しない。このため、符号は大部分はｋ−１である。この特性によって、符号はＬＤＰＣチャネルなどのパリティビット挿入アプリケーションに理想的なものになる。一実現例では、この方法は、表の中の違反シーケンスのビットアドレスを符号語の初めに配置し、表項目が配置される位置を占めているユーザデータが違反シーケンスの位置に移動される。これは、繰返し行なわれ、違反シーケンスがアドレステーブル自体の内部にある場合に備える方法で行なわれる。
【発明を実施するための最良の形態】
【０００７】
上述の局面および実施例に加えて、図面を参照することによっておよび以下の説明を検討することによって、さらなる局面および実施例が明らかになる。
【０００８】
例示的な実施例を図面の参照図に示す。本明細書に開示される実施例および図は限定的ではなく例証的であると考えられることが意図される。
【０００９】
詳細な説明
範囲を限定するのではなく例証的であるように意図されるシステム、機器および方法に関連して、以下の実施例およびその局面を記載し、示す。
【００１０】
図１は、例示的な実施例に従う、媒体に書込まれるべきデータの符号語を符号化するための方法１００を示すフローチャート図である。方法１００は媒体装置のコントローラによって実現されることができ、このコントローラはコード化制約（ｋ）に違反する０の列について符号語をスキャンし、コード化制約を満たすインジケータと違反シーケンスを置換える。この方法は、各符号語の初めに１ビットを先頭に付加することを含む。符号語の中に長さｋの違反する０の列がなければ、符号語に対してさらなる修正が行なわれることはない。コントローラが符号語の中に長さｋの違反する０の列を発見すると、コントローラは先頭に付加されたビットを０に変更し、１（保護ビット）、違反のアドレスを示すｋ−２ビットに続いて、１（終了フラグ）を挿入する。また、コントローラは、違反する０の列を、以前は語の最初のｋビットの中にあったデータと置換える。次いで、コントローラは繰返し、第１の工程における先頭に付加されたビットと同様の態様で第１の置換の際に最後の１を処理する。
【００１１】
違反列（violator）のアドレスがアドレステーブルポインタの値に等しい場合には、移動されるビットはなく、違反列のアドレスがアドレステーブルポインタ未満であるがアドレステーブルポインタ＋ｋよりも大きい場合には、アドレステーブルポインタから最も左の違反列のビットまでであるが最も左の違反列のビットを含まないビットのみが移動されるという点で、上述の置換オペレーション中に例外が生じ得る。この例外は、後の段落に記載する「内部の」違反列に対処する。
【００１２】
最初に、コントローラは、Ｎビットを受取り（１０２）、１ビットを先頭に付加することによって初期の符号語を構築し（１０４）、アドレステーブルポインタ（address table pointer）（「Ａ．Ｔ．ポインタ」）を最初のデータビットアドレスに等しく設定する（１０６）。言い換えると、スキャンビットアドレスが最初のデータビットアドレスに等しく設定される。次に、コントローラは、符号語をスキャンし（１０８）、ｋ制約に違反していたかどうかを判断する（１１０）。違反していなければ、コントローラは、符号語のブロックの最後に到達したかどうかを判断する（１１２）。到達していれば、コントローラは、ブロックを送り（１１３）、次のＮビットを受取る（１０２）。そうでなければ
、コントローラはスキャンビットアドレスを次のデータビットアドレスに等しく設定する（１１４）。
【００１３】
ｋ制約に違反している場合には（１１０）、コントローラは、スキャンビットアドレスを記録し（１１６）、スキャンビットアドレスがアドレステーブルポインタに等しいかどうかを判断する（１２０）。コントローラは、生じた違反列のタイプ、すなわち外部の違反列または内部の違反列に起因して、代替的な処理が必要であるかどうか確かめるためにオペレーション１２０において判断を行なう。より詳細には、オペレーション１２０は、内部の違反列が特に発生したことに対して代替的な処理が必要であるかどうかを判断する。２つのタイプの違反列については後の段落で詳細に説明する。
【００１４】
スキャンビットアドレスがアドレステーブルポインタに等しい場合（１２０）、コントローラは、インジケータを構築し（１２２）、アドレステーブルポインタにおいてインジケータを挿入し（１２４）、前の終了フラグをクリアし（１２６）、アドレステーブルポインタをｋだけインクリメントする（１２８）。次に、コントローラはオペレーション１１２を実行する。
【００１５】
スキャンビットアドレスがアドレステーブルポインタに等しくない場合には（１２０）、コントローラは、スキャンビットアドレスがアドレステーブルポインタ未満でありかつアドレステーブルポインタ−ｋよりも大きいかどうかを判断する（１３０）。そうでなければ、コントローラは、違反列シーケンスの最初のｋビットを、アドレステーブルポインタから開始する最初のｋビットと置換える（１３２）。次に、コントローラは、以前に記載したようにオペレーション１２２〜１２８を実行する。
【００１６】
オペレーション１３０がイエスである場合、コントローラは、アドレステーブルポインタからスキャンビットアドレスまでであるがスキャンビットアドレスを含まないデータビットをインジケータの位置（アドレステーブルポインタ−ｋ）の後ろに移動させる（１３４）。次に、コントローラはオペレーション１２２〜１２８を実行する。また、オペレーション１３０は、内部の違反列の発生に起因して代替的な処理が必要かどうかを判断する。
【００１７】
図１のこの符号化方法１００はｋを超えないランレングスを提供する。なぜなら、生じ得るｋビットのシーケンスが、違反列を排除するために後続のブロックを変形したときに１つのブロックの最後のｋ−１ビットおよび後続のブロックの先頭に付加されたビットのシーケンスになるためである。保護ビットは、さらなる違反を引起し得るインジケータが確実にないようにし、オペレーション１２０（スキャンビットアドレス＝アドレステーブルポインタであるため、移動されるビットがない）の例外は確実に、アドレステーブルから移動する必要があるデータビットが違反列の数または長さを増やし得ないようにする。また、違反列のアドレスはさらなる違反を引起し得ない。なぜなら、たとえアドレスがすべて０であったとしても、常に１である保護ビットの対または保護ビットおよび値が１である終了フラグのいずれかの中に含められるためである。さらに、データパターンおよびｋビットの違反列を含むビットの組合せはいずれも、その違反列が外部の違反列であろうと内部の違反列であろうと、同一の数のビットと置換えられる。このため、初期のデータ語の中の違反列の数から独立して、十分なスペースが符号語の中でインジケータのために維持される。
【００１８】
一実現例では、Ｎ＞２k-2であれば、オフセットビットアドレスが利用される。オフセットビットアドレスは、違反列が残りのＮ−２k-2ビットの中に存在し得ないので、符号語の最初の２k-2ビットのみをアドレス指定する。たとえば、Ｎ＝２１およびｋ＝６であれば、最後の５ビットは、オフセットビットアドレスによってアドレス指定されることは
ない。なぜなら、ｋ（６）個の０の違反列がそれらの最後の５ビットでは生じ得ないためである。Ｎ＞２k-2であるとき、インジケータはオフセットビットアドレスを指し示すアドレスフィールドを伴って構築される。代替的に言えば、オペレーション１１６において記録されるスキャンビットアドレスは、インジケータに配置される前にＮ−２k-2だけ減らされる。
【００１９】
最大長の符号が構築されると、すなわち、Ｎ＝２k-2＋ｋ−１であれば、より短い符号、すなわち、任意のより小さなＮの値を有する符号を生成するために各ユーザデータブロックの右端からビットを削除できることを理解すべきである。このため、方法１００は、基本的には修正なしですべての比率Ｎ／（Ｎ＋１）について符号を生成する。
【００２０】
図２Ａ〜図２Ｄは、例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。この例では、符号ラン比率は２１／２２であり、ｋ（ＲＬＬ制約）は６に設定された。２０ビットのデータ１０が受取られ、各ビットは対応するビットアドレス１２を有する（図２Ａ）。次いで、値が１である追加のビット１４が、受取られたビットの先頭に付加されて、初期の符号語２９を形成する。符号語２９がｋ個の連続した０のいずれのシーケンス（違反列）も含まなければ、符号語２９は変更のないまま送られる。各ビットは対応するビットアドレスを有する。さらに、ビットアドレス♯５〜２０は対応するオフセットビットアドレス１６を有する。図２Ａ〜図２Ｄの符号化の例では、Ｎ＞２k-2であるため、オフセットビットアドレスが利用される。先頭に付加されたビット１４に直接に隣接するビットのビットアドレスを最初に指し示すアドレステーブルポインタ１７が作成される。図２Ｂの例では、アドレステーブルポインタ１７は最初にオフセットビットアドレス♯１５を指し示す。
【００２１】
符号語２９は次いで、オフセットビットアドレス♯１５から開始するｋビットのスライドウィンドウを使用して左から右にスキャンされる。違反列１８がオフセット検出されると、違反列の最初のビットアドレスのビットアドレスが記録される。図２Ｂの例では、違反列１８の最初のビットアドレスはビットアドレス♯８である。なぜなら、ｋ（６）個の０のシーケンスがそこで始まるためである。第１の違反列が検出されると、先頭に付加されたビット１４は０に変更される。次いで、ｋビットの違反列１８は、アドレステーブルポインタ１７が指し示しているオフセットビットアドレスから開始するｋビットの符号語２９と置換えられる。図２Ｂ〜図２Ｃを参照して、オフセットビットアドレス♯１５で始まるシーケンス「０ １ ０ ０ １ １」が違反列１８の位置に移動され、その移送されたデータはインジケータデータ２０と称される。
【００２２】
次に、ｋビットのインジケータシーケンス２２が構築され、アドレステーブルポインタが指し示すオフセットビットアドレスから開始する符号語２９に配置される（図２Ｂ）。一実現例では、インジケータは、値が１である保護フラグ、違反列の最初のオフセットビットアドレスを識別する、長さがｋ−２のアドレスフィールド、および初期値が１である終了フラグで始まる。さらなる違反列が検出されると、終了フラグは０に変更される。図２Ｃを参照して、第１のインジケータ２２は、オフセットビットアドレス♯１５における保護フラグと、オフセットビットアドレス♯１４〜１１におけるアドレスフィールドと、オフセットビットアドレス♯１０における終了フラグとを含む。第１のインジケータ２２のアドレスフィールドはシーケンス「１ ０ ０ ０」を含み、これはオフセットビットアドレス♯８を指す。
【００２３】
アドレステーブルポインタ１６は、図２Ｂから図２Ｃまでｋだけ進められ、図２Ｃにおいてオフセットビットアドレス♯９を今では指し示している。図２Ｃにおいても、符号語２９はさらにスキャンされ、記録されるオフセットビットアドレス♯６によって最初のビットがアドレス指定される第２の違反列２４が検出される。図２Ｄを参照して、第１のイ
ンジケータ２２の終了フラグはオフセットビットアドレス♯１０において１から０に変更され、第２の違反列２４のビットは、図２Ｃにおいてアドレステーブルポインタが指し示すオフセットビットアドレスから開始するｋビットと置換えられる。詳細には、オフセットビットアドレス♯９（図２Ｃ参照）から開始するｋビット（「１ ０１ ０ ０ １」）が、第２の違反列を占めていたビット、すなわちビットアドレス♯１〜６に配置され、ビットアドレス♯５〜６はオフセットビットアドレス♯０〜１に対応する。それらの置換えられたビットはインジケータデータ２６と称される。
【００２４】
図２Ｄを参照して、第２のインジケータ２８が次いで、値が１であるオフセットビットアドレス♯９における保護フラグ、オフセットビットアドレス♯５〜８におけるアドレスフィールド、および値が１である終了フラグを伴って構築される。アドレスフィールドは、オフセットビットアドレス♯５〜８において、列「０ ０ ０ １」を含み、これはオフセットビットアドレス♯１を指す。第２の違反列２４がオフセットビットアドレス１７によってアドレス指定されないビットに及ぶので、さらなる違反列についての符号語２９のスキャンは中止される。図２Ａ〜図２Ｄの符号化の例でオフセットビットアドレス１７が利用されなければ、符号語２９の最後に到達するまで違反列についての符号語２９のスキャンは継続するであろう。
【００２５】
記載される実施例は、２つのタイプの違反列、すなわち図３Ａ〜図３Ｂに示す外部の違反列および内部の違反列をそれぞれに考慮に入れる。外部の違反列とは、違反列を指すインジケータが配置されるべきである位置内で始まらない違反列である。外部の違反列の一例は外部の違反列３０である。外部の違反列のさらなる例は、図２Ｂ〜図２Ｃに示す違反列１８および２４である。以前に記載したものと同様に、アドレステーブルポインタ（「ＡＴＰ」）３５が指し示すビットアドレスから開始するビット３４は、外部の違反列３０によって占められていたビットアドレス３６に移動される。次に、インジケータ３２が構築され、アドレステーブルポインタ３５が指し示すビットアドレスから開始するビットアドレスに配置される。
【００２６】
図３Ｂを参照して、内部の違反列とは、違反列を指すインジケータが配置されるべき位置内で始まる違反列である。たとえば、内部の違反列３８は、アドレステーブルポインタ４０から数ビットアドレスだけ離れている。たとえば、ｋ＝６であれば、違反列３８についてのインジケータの長さは６ビットであり、内部の違反列３８のビットアドレスにおいて書込まれるであろう。この場合、内部の違反列３８によって占められるビットの一部を埋めるために、先頭の０でないデータ４２のみが移動される。
【００２７】
図４は、例示的な実施例に従う、媒体から読取られるデータの符号語を復号化するための方法４００を示すフローチャート図である。示す実現例では、方法４００は、符号語の先頭に付加されたビットを調べる媒体装置のコントローラを伴う。先頭に付加されたビットの値が１である場合、先頭に付加されたビットは廃棄され、残りのビットが変更のないまま送出される。そうでなければ、符号語の復号化は、アドレステーブルにおける最後のインジケータの初期値を有するアドレステーブルポインタを作成することによって行なわれ、これは１に等しい終了フラグを有するそのエントリ（entry）である。次に、コントローラは、アドレステーブルポインタが指し示すインジケータからアドレスフィールドを抽出し、必要であればそれをＮ−２k-2だけ増やし、その結果、違反列がアドレス指定される。次に、コントローラは、アドレス指定された違反列におけるｋビットとインジケータを置換える。次に、コントローラは、ｋビットのアドレス指定された違反列を０と置換え、アドレステーブルポインタをｋだけ減らし、第１のインジケータが置換えられるまで抽出オペレーション、２つの置換オペレーションおよび減少オペレーションを繰返す。
【００２８】
アドレステーブルポインタの値が違反列のアドレスに等しい場合には、移動されるビッ
トはなく、違反列のアドレスがアドレステーブルポインタ未満であるがアドレステーブルポインタ＋ｋよりも大きい場合には、最も右の違反列のビットからインジケータの最後までであるがインジケータの最後を含まないビットのみが移動されるという点で、第１の置換オペレーションについて時には例外が生じ得る。
【００２９】
方法４００をより詳細に説明するために、図４を参照する。最初に、コントローラは、次の符号語を受取り（４０２）、先頭に付加されたビットが１に等しいかどうかを判断する（４０４）。等しい場合には、コントローラは先頭に付加されたビットを廃棄し、符号語の残りのＮビットを送出する（４０６）。そうでなければ、コントローラは、アドレステーブルポインタをアドレステーブルにおける最後のインジケータの初期値に等しく設定し（４１０）、アドレステーブルポインタが指し示すインジケータからアドレスフィールドを抽出する（４１２）。次に、コントローラは、抽出されたアドレスがアドレステーブルポインタに等しいかどうかを判断する（４１４）。等しい場合には、コントローラは、抽出されたアドレスから開始するｋビットをｋ個の数の０と置換え（４１６）、アドレステーブルポインタをｋだけ減らす（４１８）。次に、コントローラは第１のインジケータが置換えられたかどうかを判断する。置換えられていた場合には、コントローラは次の符号語を受取る（４０２）。
【００３０】
抽出されたアドレスがアドレステーブルポインタに等しくない場合（４１４）、コントローラは次いで、抽出されたアドレスがアドレステーブルポインタ未満であるがアドレステーブルポインタ−ｋよりも大きいかどうかを判断する（４２２）。そうであれば、コントローラは、最も右の違反列からインジケータの最後までのインジケータビットを置換える（４２４）。そうでなければ、コントローラは、抽出されたアドレスから開始するｋビットとインジケータを置換える（４２６）。
【００３１】
チャネルにおけるビット誤りのために、受取られた符号語は不完全な形式である場合がある。言い換えると、受取られた符号語は、以前に記載したように適切に符号化された符号語の構造に適合できない。１つの検出可能な不完全な形式は、０に等しい任意の保護ビットである。他の不完全な形式は、インジケータ自体のアドレスよりも小さなアドレスまたは任意の前のインジケータのアドレスよりも小さなアドレスを有するインジケータの発生である。デコーダはこれらの不完全な形式を任意に検出し、復号できない符号語を報告し得る。
【００３２】
図５Ａ〜図５Ｄは、例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。この例では、符号率Ｎ／（Ｎ＋１）は２１／２２であり、ｋは任意に６に設定された。図５Ａの受取られた符号語２９は、図２Ａ〜図２Ｄの符号化の例において構築された符号語と同じであり、先頭に付加されたビット１４と、第１のインジケータ２２および第２のインジケータ２８と、インジケータデータ２６とを含む。先頭に付加されたビット１４の値は０であり、したがって符号語２９の復号化が必要である。アドレステーブルポインタ１６は、最後に符号化されたインジケータの最初のビットアドレスに設定される。詳細には、アドレステーブルポインタ１６は、第２のインジケータ２８のビットアドレス♯１４におけるポイントに設定される。最後に符号化された／第２のインジケータ２８の位置は、終了フラグの値に基づいて特定される。第２のインジケータ２８はビットアドレス♯９に終了フラグを有し、その値は１であり、これは第２のインジケータが構築された後にさらなる違反列が検出されなかったことを意味する。
【００３３】
アドレスが第２のインジケータ２８から抽出され、Ｎ＞２k-2であるので、抽出されたアドレスはＮ−２k-2だけ増やされる。抽出されたアドレスはビットアドレス♯１を指し示し、ビットアドレス♯１は次に、インジケータデータ２６の最初のビットのビットアドレスであるビットアドレス♯６に増やされる。図５Ｂを参照して、インジケータデータ２
６によって占められるビットが０に戻され、インジケータデータ２６は、アドレステーブルポインタ１６が指し示すビットアドレスから開始するビットに移動される。
【００３４】
図５Ｃを参照して、アドレステーブルポインタ１６は、ｋだけ減らされ、その結果、第１のインジケータ２２のビットアドレス♯２０を指し示す。アドレスが（インジケータデータ２２によって置換えられる前の図５Ｂに示す）第１のインジケータ２２のアドレスフィールドから抽出され、そのアドレスは、ビットアドレス♯１３に増やされるビットアドレス♯８を指し示す。したがって、ビットアドレス♯１３から開始するｋビットは０に戻され、図５Ｂに示すビットアドレス♯１３〜８からのインジケータデータ２０は、図５Ｃに示すビットアドレス♯２０〜１５に配置される。次に、図５Ｄにおいて、先頭に付加されたビット１４が削除され、これは結果的に最初に図２Ａに示した元の２１ビットのデータ１０になる。
【００３５】
図６Ａ〜図６Ｂは、例示的な実施例に従う、書込セクション６００および読取セクション６５０のための、ハードウェアにおいて実現される判定チャネルを示すブロック図である。図６Ａ〜図６Ｂは、ＲＬＬ符号化および復号化が誤り訂正機構の「外側」にあることを示す。言い換えると、書込の場合には、データはＲＬＬ符号化される前にＥＣＣ符号化される。そして、読取の場合には、誤り訂正が行なわれる前にＲＬＬ符号化が除去される。これは、典型的にはビタビアルゴリズムを利用する硬判定検出器が使用されるために可能であり、その出力は、ＲＬＬデコーダが処理し得る確定ビットのストリームである。
【００３６】
図７Ａ〜図７Ｂは、例示的な実施例に従う、書込セクション７００および読取セクション７５０のための、ソフトウェアにおいて実現される軟判定チャネルを示すブロック図である。この場合、（ＢＣＪＲ、ＳＯＶＡまたは他のタイプであり得る）軟判定検出器が使用され、その出力は確定ビットではなく確率である。典型的にはターボデコーダまたは低密度パリティチェック（ＬＤＰＣ）デコーダである誤り制御ブロックがこれらの確率で動作して、確定出力ビットを生成する。したがって、ＲＬＬデコーダは検出器の出力で動作するのではなく、その代わりに誤り制御ブロックの出力で動作する。その結果、ＲＬＬ符号化および復号化は、示されるように誤り訂正機構の「内側」にある。
【００３７】
以下の段落に記載する理由のために、記載される実施例は先行技術と比較して効率的である。長さＮのユーザデータブロックはいずれも２Nの可能な値を有し、これらが長さｋの符号語上にマッピングされるようにするために、符号語は少なくともその多くの異なる値を有するべきである。各符号語長Ｎ＋１ごとにおよびｋの各値ごとに、（１）ｋよりも大きな長さのすべて０のシーケンスを含まない符号語の数、および（２）長さの合計がｋを超えないすべて０のシーケンスで始まり、終了する符号語の数を計算することが可能である。このような符号語は、ｋ制約に違反することなく自由に連結され得る。符号語が少なくとも２Nの値を有するｋの最小値は、その符号語長にとっての最適なｋの値である。ｋの値が最適値に近い場合に、ＲＬＬ符号は効率的であると考えられる。
【００３８】
記載される実施例に従って構築されるＲＬＬ符号はその意味で効率的である。表Ｉは、符号化され得るユーザビットの最大数、すなわちＮについて、記載される実施例によって達成されるｋの値を最適なｋの値と比較する。達成される値は、符号長が増大するにつれて最適値からゆっくりと逸脱することがわかる。
【００３９】
【表１】
【００４０】
さらに、符号語の中に生じ得るｋ個の０のランが上述のように２つの符号語の結合部にしかないので、すべての他の位置におけるｋビットの違反列を排除することによって、符号語のストリームは「ほぼ」ｋ−１になる。したがって、これらの符号の平均性能は最適にいっそう近づく。
【００４１】
いくつかの例示的な局面および実施例を上述してきたが、当業者はそれらの特定の修正、入替え、追加および下位の組合せを認識するであろう。したがって、以下の添付の特許請求の範囲および今後導入される特許請求の範囲は真の精神および範囲内の修正、入替え、追加および下位の組合せをすべて含むように解釈されることが意図される。
【図面の簡単な説明】
【００４２】
【図１】例示的な実施例に従う、媒体に書込まれるべきデータの符号語を符号化するための方法を示すフローチャート図である。
【図２Ａ】例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。
【図２Ｂ】例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。
【図２Ｃ】例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。
【図２Ｄ】例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。
【図３Ａ】例示的な実施例に従う外部の違反列を示す。
【図３Ｂ】例示的な実施例に従う内部の違反列を示す。
【図４】例示的な実施例に従う、媒体から読取られるデータの符号語を復号化するための方法を示すフローチャート図である。
【図５Ａ】例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。
【図５Ｂ】例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。
【図５Ｃ】例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。
【図５Ｄ】例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。
【図６Ａ】例示的な実施例に従う、書込セクションのための、ハードウェアにおいて実現される判定チャネルを示すブロック図である。
【図６Ｂ】例示的な実施例に従う、読取セクションのための、ハードウェアにおいて実現される判定チャネルを示すブロック図である。
【図７Ａ】例示的な実施例に従う、書込セクションのための、ソフトウェアにおいて実現される軟判定チャネルを示すブロック図である。
【図７Ｂ】例示的な実施例に従う、読取セクションのための、ソフトウェアにおいて実現される軟判定チャネルを示すブロック図である。
【符号の説明】
【００４３】
１８ 第１の違反列
２２ 第１のインジケータ
２４ 第２の違反列
２９ 符号語
２８ 第２のインジケータ
【技術分野】
【０００１】
技術分野
この発明は概してデータの符号化および復号化に関する。
【背景技術】
【０００２】
背景
磁気記憶チャネルでは、タイミング回復システムの頻繁な更新を保証するためにデータストリームの中の連続する０の数を制限することが望ましい。これは、ランレングス制限と呼ばれ、たとえばデータを「Ｎ」ビットのブロックに分割し、次いで、Ｎ＋１ビットのブロックも連結されたブロックの対も所望の数「ｋ」以上の連続する０を持たないように、選択されたＮ＋１ビットのブロック上に各ブロックをマッピングすることによって達成され得る。典型的な符号には、８ビットの各ブロックを、９ビット（「８／９符号」）および「１６／１７」、「２４／２５」、「３２／３３」などのランレングス制限（run-length-limited）（「ＲＬＬ」）ブロックと置換える符号が含まれる。割合Ｎ／（Ｎ＋１）は、符号の「比率」と呼ばれる。もちろん、コード化率が異なるＲＬＬスキームも存在する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
多くの先行技術の方法の不利な点は、先行技術の方法がルックアップテーブルによって定義され、そのためコストおよび電力消費とともに符号化および復号化の複雑さが符号長に伴って指数関数的に増大することである。別の不利な点は、大半の先行技術の方法がその場その場での処理であり、各比率ごとに符号を開発するために異なるアプローチが必要であることである。先行技術の方法の中には、順次論理を使用して効率的に符号化および復号化でき、したがって複雑さの問題に部分的に対処しているものもある。しかしながら、これらの先行技術の方法は所与の比率に適合させるために相当な創意工夫が必要であることが多く、これらの先行技術の方法を使用して構築され得る符号がない比率が存在する。これは問題である。なぜなら、記録技術が（リード−ソロモン符号などの）バイト指向の誤り訂正から離れて（ターボおよび低密度パリティチェック（low density parity check）（「ＬＤＰＣ」）符号などの）軟復号化方法に移ると、さまざまな比率を有するＲＬＬ符号が必要になるためである。さらに、長い符号を構築するためのいくつかの先行技術の方法が考案されており、これは、符号化されていないブロックを、より短い、ＲＬＬ符号化された語からのブロックで挟むことを伴う。これらの技術は、ある意味では一般的であるが、最適状態に大幅に及ばないｋの値を生じさせることが多い。
【０００４】
上述を鑑みて、効率的なエンコーダおよびデコーダを利用し、ｋの値が最適に近い符号を生成し、任意の所望の符号率に容易に適合する、ＲＬＬ符号を構築するための一般的な方法が当該技術分野において必要である。
【課題を解決するための手段】
【０００５】
概要
範囲を限定するのではなく例示的および例証的であるように意図されるシステム、機器および方法に関連して、以下の実施例およびその局面を記載し、示す。さまざまな実施例において、上述の問題を１つ以上低減または解消した。
【０００６】
記載される実施例は、データのランレングス制限（ＲＬＬ）コード化に向けられる方法
、機器およびシステムを提供する。一実現例では、ｋを超えない０のランレングスを有する連結可能なＲＬＬ符号が任意の比率Ｎ／（Ｎ＋１）について構築され、ここでＮ≦２k-2＋ｋ-1である。符号率が増加すると、ｋの値は多くの他の符号の値よりもゆっくりと最小値から離れる。さらに、ｋビットのランレングスの発生は、２つの符号語の接合部でしか発生しない。このため、符号は大部分はｋ−１である。この特性によって、符号はＬＤＰＣチャネルなどのパリティビット挿入アプリケーションに理想的なものになる。一実現例では、この方法は、表の中の違反シーケンスのビットアドレスを符号語の初めに配置し、表項目が配置される位置を占めているユーザデータが違反シーケンスの位置に移動される。これは、繰返し行なわれ、違反シーケンスがアドレステーブル自体の内部にある場合に備える方法で行なわれる。
【発明を実施するための最良の形態】
【０００７】
上述の局面および実施例に加えて、図面を参照することによっておよび以下の説明を検討することによって、さらなる局面および実施例が明らかになる。
【０００８】
例示的な実施例を図面の参照図に示す。本明細書に開示される実施例および図は限定的ではなく例証的であると考えられることが意図される。
【０００９】
詳細な説明
範囲を限定するのではなく例証的であるように意図されるシステム、機器および方法に関連して、以下の実施例およびその局面を記載し、示す。
【００１０】
図１は、例示的な実施例に従う、媒体に書込まれるべきデータの符号語を符号化するための方法１００を示すフローチャート図である。方法１００は媒体装置のコントローラによって実現されることができ、このコントローラはコード化制約（ｋ）に違反する０の列について符号語をスキャンし、コード化制約を満たすインジケータと違反シーケンスを置換える。この方法は、各符号語の初めに１ビットを先頭に付加することを含む。符号語の中に長さｋの違反する０の列がなければ、符号語に対してさらなる修正が行なわれることはない。コントローラが符号語の中に長さｋの違反する０の列を発見すると、コントローラは先頭に付加されたビットを０に変更し、１（保護ビット）、違反のアドレスを示すｋ−２ビットに続いて、１（終了フラグ）を挿入する。また、コントローラは、違反する０の列を、以前は語の最初のｋビットの中にあったデータと置換える。次いで、コントローラは繰返し、第１の工程における先頭に付加されたビットと同様の態様で第１の置換の際に最後の１を処理する。
【００１１】
違反列（violator）のアドレスがアドレステーブルポインタの値に等しい場合には、移動されるビットはなく、違反列のアドレスがアドレステーブルポインタ未満であるがアドレステーブルポインタ＋ｋよりも大きい場合には、アドレステーブルポインタから最も左の違反列のビットまでであるが最も左の違反列のビットを含まないビットのみが移動されるという点で、上述の置換オペレーション中に例外が生じ得る。この例外は、後の段落に記載する「内部の」違反列に対処する。
【００１２】
最初に、コントローラは、Ｎビットを受取り（１０２）、１ビットを先頭に付加することによって初期の符号語を構築し（１０４）、アドレステーブルポインタ（address table pointer）（「Ａ．Ｔ．ポインタ」）を最初のデータビットアドレスに等しく設定する（１０６）。言い換えると、スキャンビットアドレスが最初のデータビットアドレスに等しく設定される。次に、コントローラは、符号語をスキャンし（１０８）、ｋ制約に違反していたかどうかを判断する（１１０）。違反していなければ、コントローラは、符号語のブロックの最後に到達したかどうかを判断する（１１２）。到達していれば、コントローラは、ブロックを送り（１１３）、次のＮビットを受取る（１０２）。そうでなければ
、コントローラはスキャンビットアドレスを次のデータビットアドレスに等しく設定する（１１４）。
【００１３】
ｋ制約に違反している場合には（１１０）、コントローラは、スキャンビットアドレスを記録し（１１６）、スキャンビットアドレスがアドレステーブルポインタに等しいかどうかを判断する（１２０）。コントローラは、生じた違反列のタイプ、すなわち外部の違反列または内部の違反列に起因して、代替的な処理が必要であるかどうか確かめるためにオペレーション１２０において判断を行なう。より詳細には、オペレーション１２０は、内部の違反列が特に発生したことに対して代替的な処理が必要であるかどうかを判断する。２つのタイプの違反列については後の段落で詳細に説明する。
【００１４】
スキャンビットアドレスがアドレステーブルポインタに等しい場合（１２０）、コントローラは、インジケータを構築し（１２２）、アドレステーブルポインタにおいてインジケータを挿入し（１２４）、前の終了フラグをクリアし（１２６）、アドレステーブルポインタをｋだけインクリメントする（１２８）。次に、コントローラはオペレーション１１２を実行する。
【００１５】
スキャンビットアドレスがアドレステーブルポインタに等しくない場合には（１２０）、コントローラは、スキャンビットアドレスがアドレステーブルポインタ未満でありかつアドレステーブルポインタ−ｋよりも大きいかどうかを判断する（１３０）。そうでなければ、コントローラは、違反列シーケンスの最初のｋビットを、アドレステーブルポインタから開始する最初のｋビットと置換える（１３２）。次に、コントローラは、以前に記載したようにオペレーション１２２〜１２８を実行する。
【００１６】
オペレーション１３０がイエスである場合、コントローラは、アドレステーブルポインタからスキャンビットアドレスまでであるがスキャンビットアドレスを含まないデータビットをインジケータの位置（アドレステーブルポインタ−ｋ）の後ろに移動させる（１３４）。次に、コントローラはオペレーション１２２〜１２８を実行する。また、オペレーション１３０は、内部の違反列の発生に起因して代替的な処理が必要かどうかを判断する。
【００１７】
図１のこの符号化方法１００はｋを超えないランレングスを提供する。なぜなら、生じ得るｋビットのシーケンスが、違反列を排除するために後続のブロックを変形したときに１つのブロックの最後のｋ−１ビットおよび後続のブロックの先頭に付加されたビットのシーケンスになるためである。保護ビットは、さらなる違反を引起し得るインジケータが確実にないようにし、オペレーション１２０（スキャンビットアドレス＝アドレステーブルポインタであるため、移動されるビットがない）の例外は確実に、アドレステーブルから移動する必要があるデータビットが違反列の数または長さを増やし得ないようにする。また、違反列のアドレスはさらなる違反を引起し得ない。なぜなら、たとえアドレスがすべて０であったとしても、常に１である保護ビットの対または保護ビットおよび値が１である終了フラグのいずれかの中に含められるためである。さらに、データパターンおよびｋビットの違反列を含むビットの組合せはいずれも、その違反列が外部の違反列であろうと内部の違反列であろうと、同一の数のビットと置換えられる。このため、初期のデータ語の中の違反列の数から独立して、十分なスペースが符号語の中でインジケータのために維持される。
【００１８】
一実現例では、Ｎ＞２k-2であれば、オフセットビットアドレスが利用される。オフセットビットアドレスは、違反列が残りのＮ−２k-2ビットの中に存在し得ないので、符号語の最初の２k-2ビットのみをアドレス指定する。たとえば、Ｎ＝２１およびｋ＝６であれば、最後の５ビットは、オフセットビットアドレスによってアドレス指定されることは
ない。なぜなら、ｋ（６）個の０の違反列がそれらの最後の５ビットでは生じ得ないためである。Ｎ＞２k-2であるとき、インジケータはオフセットビットアドレスを指し示すアドレスフィールドを伴って構築される。代替的に言えば、オペレーション１１６において記録されるスキャンビットアドレスは、インジケータに配置される前にＮ−２k-2だけ減らされる。
【００１９】
最大長の符号が構築されると、すなわち、Ｎ＝２k-2＋ｋ−１であれば、より短い符号、すなわち、任意のより小さなＮの値を有する符号を生成するために各ユーザデータブロックの右端からビットを削除できることを理解すべきである。このため、方法１００は、基本的には修正なしですべての比率Ｎ／（Ｎ＋１）について符号を生成する。
【００２０】
図２Ａ〜図２Ｄは、例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。この例では、符号ラン比率は２１／２２であり、ｋ（ＲＬＬ制約）は６に設定された。２０ビットのデータ１０が受取られ、各ビットは対応するビットアドレス１２を有する（図２Ａ）。次いで、値が１である追加のビット１４が、受取られたビットの先頭に付加されて、初期の符号語２９を形成する。符号語２９がｋ個の連続した０のいずれのシーケンス（違反列）も含まなければ、符号語２９は変更のないまま送られる。各ビットは対応するビットアドレスを有する。さらに、ビットアドレス♯５〜２０は対応するオフセットビットアドレス１６を有する。図２Ａ〜図２Ｄの符号化の例では、Ｎ＞２k-2であるため、オフセットビットアドレスが利用される。先頭に付加されたビット１４に直接に隣接するビットのビットアドレスを最初に指し示すアドレステーブルポインタ１７が作成される。図２Ｂの例では、アドレステーブルポインタ１７は最初にオフセットビットアドレス♯１５を指し示す。
【００２１】
符号語２９は次いで、オフセットビットアドレス♯１５から開始するｋビットのスライドウィンドウを使用して左から右にスキャンされる。違反列１８がオフセット検出されると、違反列の最初のビットアドレスのビットアドレスが記録される。図２Ｂの例では、違反列１８の最初のビットアドレスはビットアドレス♯８である。なぜなら、ｋ（６）個の０のシーケンスがそこで始まるためである。第１の違反列が検出されると、先頭に付加されたビット１４は０に変更される。次いで、ｋビットの違反列１８は、アドレステーブルポインタ１７が指し示しているオフセットビットアドレスから開始するｋビットの符号語２９と置換えられる。図２Ｂ〜図２Ｃを参照して、オフセットビットアドレス♯１５で始まるシーケンス「０ １ ０ ０ １ １」が違反列１８の位置に移動され、その移送されたデータはインジケータデータ２０と称される。
【００２２】
次に、ｋビットのインジケータシーケンス２２が構築され、アドレステーブルポインタが指し示すオフセットビットアドレスから開始する符号語２９に配置される（図２Ｂ）。一実現例では、インジケータは、値が１である保護フラグ、違反列の最初のオフセットビットアドレスを識別する、長さがｋ−２のアドレスフィールド、および初期値が１である終了フラグで始まる。さらなる違反列が検出されると、終了フラグは０に変更される。図２Ｃを参照して、第１のインジケータ２２は、オフセットビットアドレス♯１５における保護フラグと、オフセットビットアドレス♯１４〜１１におけるアドレスフィールドと、オフセットビットアドレス♯１０における終了フラグとを含む。第１のインジケータ２２のアドレスフィールドはシーケンス「１ ０ ０ ０」を含み、これはオフセットビットアドレス♯８を指す。
【００２３】
アドレステーブルポインタ１６は、図２Ｂから図２Ｃまでｋだけ進められ、図２Ｃにおいてオフセットビットアドレス♯９を今では指し示している。図２Ｃにおいても、符号語２９はさらにスキャンされ、記録されるオフセットビットアドレス♯６によって最初のビットがアドレス指定される第２の違反列２４が検出される。図２Ｄを参照して、第１のイ
ンジケータ２２の終了フラグはオフセットビットアドレス♯１０において１から０に変更され、第２の違反列２４のビットは、図２Ｃにおいてアドレステーブルポインタが指し示すオフセットビットアドレスから開始するｋビットと置換えられる。詳細には、オフセットビットアドレス♯９（図２Ｃ参照）から開始するｋビット（「１ ０１ ０ ０ １」）が、第２の違反列を占めていたビット、すなわちビットアドレス♯１〜６に配置され、ビットアドレス♯５〜６はオフセットビットアドレス♯０〜１に対応する。それらの置換えられたビットはインジケータデータ２６と称される。
【００２４】
図２Ｄを参照して、第２のインジケータ２８が次いで、値が１であるオフセットビットアドレス♯９における保護フラグ、オフセットビットアドレス♯５〜８におけるアドレスフィールド、および値が１である終了フラグを伴って構築される。アドレスフィールドは、オフセットビットアドレス♯５〜８において、列「０ ０ ０ １」を含み、これはオフセットビットアドレス♯１を指す。第２の違反列２４がオフセットビットアドレス１７によってアドレス指定されないビットに及ぶので、さらなる違反列についての符号語２９のスキャンは中止される。図２Ａ〜図２Ｄの符号化の例でオフセットビットアドレス１７が利用されなければ、符号語２９の最後に到達するまで違反列についての符号語２９のスキャンは継続するであろう。
【００２５】
記載される実施例は、２つのタイプの違反列、すなわち図３Ａ〜図３Ｂに示す外部の違反列および内部の違反列をそれぞれに考慮に入れる。外部の違反列とは、違反列を指すインジケータが配置されるべきである位置内で始まらない違反列である。外部の違反列の一例は外部の違反列３０である。外部の違反列のさらなる例は、図２Ｂ〜図２Ｃに示す違反列１８および２４である。以前に記載したものと同様に、アドレステーブルポインタ（「ＡＴＰ」）３５が指し示すビットアドレスから開始するビット３４は、外部の違反列３０によって占められていたビットアドレス３６に移動される。次に、インジケータ３２が構築され、アドレステーブルポインタ３５が指し示すビットアドレスから開始するビットアドレスに配置される。
【００２６】
図３Ｂを参照して、内部の違反列とは、違反列を指すインジケータが配置されるべき位置内で始まる違反列である。たとえば、内部の違反列３８は、アドレステーブルポインタ４０から数ビットアドレスだけ離れている。たとえば、ｋ＝６であれば、違反列３８についてのインジケータの長さは６ビットであり、内部の違反列３８のビットアドレスにおいて書込まれるであろう。この場合、内部の違反列３８によって占められるビットの一部を埋めるために、先頭の０でないデータ４２のみが移動される。
【００２７】
図４は、例示的な実施例に従う、媒体から読取られるデータの符号語を復号化するための方法４００を示すフローチャート図である。示す実現例では、方法４００は、符号語の先頭に付加されたビットを調べる媒体装置のコントローラを伴う。先頭に付加されたビットの値が１である場合、先頭に付加されたビットは廃棄され、残りのビットが変更のないまま送出される。そうでなければ、符号語の復号化は、アドレステーブルにおける最後のインジケータの初期値を有するアドレステーブルポインタを作成することによって行なわれ、これは１に等しい終了フラグを有するそのエントリ（entry）である。次に、コントローラは、アドレステーブルポインタが指し示すインジケータからアドレスフィールドを抽出し、必要であればそれをＮ−２k-2だけ増やし、その結果、違反列がアドレス指定される。次に、コントローラは、アドレス指定された違反列におけるｋビットとインジケータを置換える。次に、コントローラは、ｋビットのアドレス指定された違反列を０と置換え、アドレステーブルポインタをｋだけ減らし、第１のインジケータが置換えられるまで抽出オペレーション、２つの置換オペレーションおよび減少オペレーションを繰返す。
【００２８】
アドレステーブルポインタの値が違反列のアドレスに等しい場合には、移動されるビッ
トはなく、違反列のアドレスがアドレステーブルポインタ未満であるがアドレステーブルポインタ＋ｋよりも大きい場合には、最も右の違反列のビットからインジケータの最後までであるがインジケータの最後を含まないビットのみが移動されるという点で、第１の置換オペレーションについて時には例外が生じ得る。
【００２９】
方法４００をより詳細に説明するために、図４を参照する。最初に、コントローラは、次の符号語を受取り（４０２）、先頭に付加されたビットが１に等しいかどうかを判断する（４０４）。等しい場合には、コントローラは先頭に付加されたビットを廃棄し、符号語の残りのＮビットを送出する（４０６）。そうでなければ、コントローラは、アドレステーブルポインタをアドレステーブルにおける最後のインジケータの初期値に等しく設定し（４１０）、アドレステーブルポインタが指し示すインジケータからアドレスフィールドを抽出する（４１２）。次に、コントローラは、抽出されたアドレスがアドレステーブルポインタに等しいかどうかを判断する（４１４）。等しい場合には、コントローラは、抽出されたアドレスから開始するｋビットをｋ個の数の０と置換え（４１６）、アドレステーブルポインタをｋだけ減らす（４１８）。次に、コントローラは第１のインジケータが置換えられたかどうかを判断する。置換えられていた場合には、コントローラは次の符号語を受取る（４０２）。
【００３０】
抽出されたアドレスがアドレステーブルポインタに等しくない場合（４１４）、コントローラは次いで、抽出されたアドレスがアドレステーブルポインタ未満であるがアドレステーブルポインタ−ｋよりも大きいかどうかを判断する（４２２）。そうであれば、コントローラは、最も右の違反列からインジケータの最後までのインジケータビットを置換える（４２４）。そうでなければ、コントローラは、抽出されたアドレスから開始するｋビットとインジケータを置換える（４２６）。
【００３１】
チャネルにおけるビット誤りのために、受取られた符号語は不完全な形式である場合がある。言い換えると、受取られた符号語は、以前に記載したように適切に符号化された符号語の構造に適合できない。１つの検出可能な不完全な形式は、０に等しい任意の保護ビットである。他の不完全な形式は、インジケータ自体のアドレスよりも小さなアドレスまたは任意の前のインジケータのアドレスよりも小さなアドレスを有するインジケータの発生である。デコーダはこれらの不完全な形式を任意に検出し、復号できない符号語を報告し得る。
【００３２】
図５Ａ〜図５Ｄは、例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。この例では、符号率Ｎ／（Ｎ＋１）は２１／２２であり、ｋは任意に６に設定された。図５Ａの受取られた符号語２９は、図２Ａ〜図２Ｄの符号化の例において構築された符号語と同じであり、先頭に付加されたビット１４と、第１のインジケータ２２および第２のインジケータ２８と、インジケータデータ２６とを含む。先頭に付加されたビット１４の値は０であり、したがって符号語２９の復号化が必要である。アドレステーブルポインタ１６は、最後に符号化されたインジケータの最初のビットアドレスに設定される。詳細には、アドレステーブルポインタ１６は、第２のインジケータ２８のビットアドレス♯１４におけるポイントに設定される。最後に符号化された／第２のインジケータ２８の位置は、終了フラグの値に基づいて特定される。第２のインジケータ２８はビットアドレス♯９に終了フラグを有し、その値は１であり、これは第２のインジケータが構築された後にさらなる違反列が検出されなかったことを意味する。
【００３３】
アドレスが第２のインジケータ２８から抽出され、Ｎ＞２k-2であるので、抽出されたアドレスはＮ−２k-2だけ増やされる。抽出されたアドレスはビットアドレス♯１を指し示し、ビットアドレス♯１は次に、インジケータデータ２６の最初のビットのビットアドレスであるビットアドレス♯６に増やされる。図５Ｂを参照して、インジケータデータ２
６によって占められるビットが０に戻され、インジケータデータ２６は、アドレステーブルポインタ１６が指し示すビットアドレスから開始するビットに移動される。
【００３４】
図５Ｃを参照して、アドレステーブルポインタ１６は、ｋだけ減らされ、その結果、第１のインジケータ２２のビットアドレス♯２０を指し示す。アドレスが（インジケータデータ２２によって置換えられる前の図５Ｂに示す）第１のインジケータ２２のアドレスフィールドから抽出され、そのアドレスは、ビットアドレス♯１３に増やされるビットアドレス♯８を指し示す。したがって、ビットアドレス♯１３から開始するｋビットは０に戻され、図５Ｂに示すビットアドレス♯１３〜８からのインジケータデータ２０は、図５Ｃに示すビットアドレス♯２０〜１５に配置される。次に、図５Ｄにおいて、先頭に付加されたビット１４が削除され、これは結果的に最初に図２Ａに示した元の２１ビットのデータ１０になる。
【００３５】
図６Ａ〜図６Ｂは、例示的な実施例に従う、書込セクション６００および読取セクション６５０のための、ハードウェアにおいて実現される判定チャネルを示すブロック図である。図６Ａ〜図６Ｂは、ＲＬＬ符号化および復号化が誤り訂正機構の「外側」にあることを示す。言い換えると、書込の場合には、データはＲＬＬ符号化される前にＥＣＣ符号化される。そして、読取の場合には、誤り訂正が行なわれる前にＲＬＬ符号化が除去される。これは、典型的にはビタビアルゴリズムを利用する硬判定検出器が使用されるために可能であり、その出力は、ＲＬＬデコーダが処理し得る確定ビットのストリームである。
【００３６】
図７Ａ〜図７Ｂは、例示的な実施例に従う、書込セクション７００および読取セクション７５０のための、ソフトウェアにおいて実現される軟判定チャネルを示すブロック図である。この場合、（ＢＣＪＲ、ＳＯＶＡまたは他のタイプであり得る）軟判定検出器が使用され、その出力は確定ビットではなく確率である。典型的にはターボデコーダまたは低密度パリティチェック（ＬＤＰＣ）デコーダである誤り制御ブロックがこれらの確率で動作して、確定出力ビットを生成する。したがって、ＲＬＬデコーダは検出器の出力で動作するのではなく、その代わりに誤り制御ブロックの出力で動作する。その結果、ＲＬＬ符号化および復号化は、示されるように誤り訂正機構の「内側」にある。
【００３７】
以下の段落に記載する理由のために、記載される実施例は先行技術と比較して効率的である。長さＮのユーザデータブロックはいずれも２Nの可能な値を有し、これらが長さｋの符号語上にマッピングされるようにするために、符号語は少なくともその多くの異なる値を有するべきである。各符号語長Ｎ＋１ごとにおよびｋの各値ごとに、（１）ｋよりも大きな長さのすべて０のシーケンスを含まない符号語の数、および（２）長さの合計がｋを超えないすべて０のシーケンスで始まり、終了する符号語の数を計算することが可能である。このような符号語は、ｋ制約に違反することなく自由に連結され得る。符号語が少なくとも２Nの値を有するｋの最小値は、その符号語長にとっての最適なｋの値である。ｋの値が最適値に近い場合に、ＲＬＬ符号は効率的であると考えられる。
【００３８】
記載される実施例に従って構築されるＲＬＬ符号はその意味で効率的である。表Ｉは、符号化され得るユーザビットの最大数、すなわちＮについて、記載される実施例によって達成されるｋの値を最適なｋの値と比較する。達成される値は、符号長が増大するにつれて最適値からゆっくりと逸脱することがわかる。
【００３９】
【表１】
【００４０】
さらに、符号語の中に生じ得るｋ個の０のランが上述のように２つの符号語の結合部にしかないので、すべての他の位置におけるｋビットの違反列を排除することによって、符号語のストリームは「ほぼ」ｋ−１になる。したがって、これらの符号の平均性能は最適にいっそう近づく。
【００４１】
いくつかの例示的な局面および実施例を上述してきたが、当業者はそれらの特定の修正、入替え、追加および下位の組合せを認識するであろう。したがって、以下の添付の特許請求の範囲および今後導入される特許請求の範囲は真の精神および範囲内の修正、入替え、追加および下位の組合せをすべて含むように解釈されることが意図される。
【図面の簡単な説明】
【００４２】
【図１】例示的な実施例に従う、媒体に書込まれるべきデータの符号語を符号化するための方法を示すフローチャート図である。
【図２Ａ】例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。
【図２Ｂ】例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。
【図２Ｃ】例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。
【図２Ｄ】例示的な実施例に従う、符号化されているデータの一例をシーケンシャルに示す。
【図３Ａ】例示的な実施例に従う外部の違反列を示す。
【図３Ｂ】例示的な実施例に従う内部の違反列を示す。
【図４】例示的な実施例に従う、媒体から読取られるデータの符号語を復号化するための方法を示すフローチャート図である。
【図５Ａ】例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。
【図５Ｂ】例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。
【図５Ｃ】例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。
【図５Ｄ】例示的な実施例に従う、符号語の例示的な復号化をシーケンシャルに示す。
【図６Ａ】例示的な実施例に従う、書込セクションのための、ハードウェアにおいて実現される判定チャネルを示すブロック図である。
【図６Ｂ】例示的な実施例に従う、読取セクションのための、ハードウェアにおいて実現される判定チャネルを示すブロック図である。
【図７Ａ】例示的な実施例に従う、書込セクションのための、ソフトウェアにおいて実現される軟判定チャネルを示すブロック図である。
【図７Ｂ】例示的な実施例に従う、読取セクションのための、ソフトウェアにおいて実現される軟判定チャネルを示すブロック図である。
【符号の説明】
【００４３】
１８ 第１の違反列
２２ 第１のインジケータ
２４ 第２の違反列
２９ 符号語
２８ 第２のインジケータ
【特許請求の範囲】
【請求項１】
データの符号語を符号化および復号化するように動作可能な媒体装置において、媒体に書込まれるべきデータの符号語を符号化するための方法であって、
Ｎビットのデータを含む語を受取ることと、
前記語において違反シーケンスの位置を特定することと、
違反列を除去することと、
違反シーケンスのアドレスを特徴付けるインジケータを前記語に挿入することとを備える、方法。
【請求項２】
前記違反列は、予め定められた値を有するビットの連続したシーケンスである、請求項１に記載の方法。
【請求項３】
前記違反列は、連続した０のシーケンスである、請求項２に記載の方法。
【請求項４】
追加のビットを前記語の先頭に付加することをさらに備える、請求項１に記載の方法。
【請求項５】
先頭に付加されたビットの値は、前記違反列の位置を特定すると変更される、請求項４に記載の方法。
【請求項６】
前記違反シーケンスのビットは、以前は挿入されたインジケータのビットアドレスにあったビットと置換えられる、請求項１に記載の方法。
【請求項７】
前記違反シーケンスの位置を特定することは、
追加のビットを前記語の先頭に付加することを含み、各ビットは対応するビットアドレスを有し、前記違反シーケンスの位置を特定することはさらに、
先頭に付加された追加のビットに隣接するビットアドレスにアドレステーブルポインタを向けることと、
前記違反シーケンスについて前記語をインクリメンタルにスキャンすることとを含み、前記違反シーケンスは、ランレングス制限コード化制約に違反するビットの連続したシーケンスを含み、前記違反シーケンスの位置を特定することはさらに、
前記違反シーケンスの位置を特定することを含む、請求項６に記載の方法。
【請求項８】
前記インジケータを挿入することは、
ｋビットの前記違反列を、前記ビットアドレスから開始するｋビットの前記符号語と置換えることと、
前記インジケータを構築することと、
前記アドレステーブルポインタから開始する前記インジケータを挿入することと、
新しいビットアドレスを指し示すために前記アドレステーブルポインタをｋだけ進めることとを含む、請求項７に記載の方法。
【請求項９】
前記インジケータは、保護ビットと、アドレスフィールドと、終了フラグとを含む、請求項８に記載の方法。
【請求項１０】
アドレスフィールドの長さはｋ−２ビットである、請求項８に記載の方法。
【請求項１１】
アドレスフィールドは、前記違反シーケンスの最初のビットアドレスを識別する、請求項８に記載の方法。
【請求項１２】
前記保護ビットの値は１であり、前記終了フラグの値は最初は０であり、前記終了フラ
グは、追加の違反列が検出されると１に変更される、請求項９に記載の方法。
【請求項１３】
前記違反シーケンスの最初のビットのビットアドレスが対応するアドレステーブルポインタに等しい場合には、前記違反列のビットは前記インジケータと置換えられる、請求項８に記載の方法。
【請求項１４】
ａ） 前記違反シーケンスの最初のビットのビットアドレスが対応するアドレステーブルポインタに等しくない場合、および
ｂ） 前記ビットアドレスが前記対応するアドレステーブルポインタ未満である場合、および
ｃ） 前記ビットアドレスが前記対応するアドレステーブルポインタ−ｋよりも大きい場合、
前記アドレステーブルポインタから開始し、前記違反シーケンスの最初のビットのビットアドレスまでであるが前記違反シーケンスの最初のビットのビットアドレスを含まないビットと前記違反シーケンスのビットを置換え、前記違反シーケンスの置換えられたビットは、アドレステーブルポインタ＋ｋに隣接する１つのビットアドレスから開始して置換えられる、請求項８に記載の方法。
【請求項１５】
前記アドレスはビットアドレスであり、Ｎ＞２k-2の場合、前記違反列のビットアドレスはＮ−２k-2だけ減らされる、請求項８に記載の方法。
【請求項１６】
データの符号語を符号化および復号化するように動作可能な媒体装置において、媒体に書込まれるべきデータの符号語を復号化するための方法であって、
Ｎビットのデータを含む語を受取ることと、
前記語においてインジケータシーケンスを識別することとを備え、前記インジケータシーケンスは違反シーケンスのアドレスを含み、前記方法はさらに、
インジケータから前記違反シーケンスのアドレスを抽出することと、
前記アドレスにおいて前記違反シーケンスを挿入することとを備える、方法。
【請求項１７】
前記違反シーケンスが挿入される前に、前記インジケータを前記アドレスにおけるビットと置換えることをさらに備える、請求項１６に記載の方法。
【請求項１８】
前記方法は、
前記アドレスが抽出される前に、前記インジケータシーケンスの最初のビットアドレスを指し示すようにアドレステーブルポインタを設定することをさらに備え、
前記アドレスによって指定されるビットアドレスから開始するｋビットの前記語は、前記インジケータシーケンスを置換えるために使用され、
ｋビットの前記違反シーケンスは前記アドレスにおいて前記語に挿入される、請求項１７に記載の方法。
【請求項１９】
前記違反シーケンスはｋ個の０である、請求項１８に記載の方法。
【請求項２０】
前記語は先頭に付加されたビットをさらに含み、前記先頭に付加されたビットの値は、前記語が復号化を必要とするかどうかを判断するために利用される、請求項１８に記載の方法。
【請求項２１】
前記語が復号化を必要とするかどうかを判断することは、
前記先頭に付加されたビットを調べることと、
前記先頭に付加されたビットが０に等しい場合に前記符号語を復号化することとを含む、請求項２０に記載の方法。
【請求項２２】
前記アドレスが前記アドレステーブルポインタと同じビットアドレスを指し示す場合に、前記インジケータシーケンスのビットは前記違反シーケンスと置換えられる、請求項１８に記載の方法。
【請求項２３】
ａ） 前記アドレスが対応するアドレステーブルポインタに等しくない場合、および
ｂ） 前記ビットアドレスが前記対応するアドレステーブルポインタ未満である場合、および
ｃ） 前記ビットアドレスが前記対応するアドレステーブルポインタ−ｋよりも大きい場合、
最も右の違反シーケンスから前記インジケータシーケンスの最後までの違反列シーケンスのビットと前記インジケータシーケンスのビットを置換える、請求項１８に記載の方法。
【請求項２４】
前記インジケータシーケンスは、保護ビットと、終了フラグとをさらに含む、請求項１６に記載の方法。
【請求項２５】
前記インジケータシーケンスは、最後に符号化されたインジケータシーケンスであり、前記最後に符号化されたインジケータシーケンスの位置は、前記最後に符号化されたインジケータシーケンスにおける終了フラグの値によって前記語において特定される、請求項２４に記載の方法。
【請求項２６】
前記最後に符号化されたインジケータシーケンスにおける前記終了フラグの値は１である、請求項２５に記載の方法。
【請求項２７】
Ｎ＞２k-2の場合、前記アドレスはＮ−２k-2だけ増やされる、請求項１８に記載の方法。
【請求項１】
データの符号語を符号化および復号化するように動作可能な媒体装置において、媒体に書込まれるべきデータの符号語を符号化するための方法であって、
Ｎビットのデータを含む語を受取ることと、
前記語において違反シーケンスの位置を特定することと、
違反列を除去することと、
違反シーケンスのアドレスを特徴付けるインジケータを前記語に挿入することとを備える、方法。
【請求項２】
前記違反列は、予め定められた値を有するビットの連続したシーケンスである、請求項１に記載の方法。
【請求項３】
前記違反列は、連続した０のシーケンスである、請求項２に記載の方法。
【請求項４】
追加のビットを前記語の先頭に付加することをさらに備える、請求項１に記載の方法。
【請求項５】
先頭に付加されたビットの値は、前記違反列の位置を特定すると変更される、請求項４に記載の方法。
【請求項６】
前記違反シーケンスのビットは、以前は挿入されたインジケータのビットアドレスにあったビットと置換えられる、請求項１に記載の方法。
【請求項７】
前記違反シーケンスの位置を特定することは、
追加のビットを前記語の先頭に付加することを含み、各ビットは対応するビットアドレスを有し、前記違反シーケンスの位置を特定することはさらに、
先頭に付加された追加のビットに隣接するビットアドレスにアドレステーブルポインタを向けることと、
前記違反シーケンスについて前記語をインクリメンタルにスキャンすることとを含み、前記違反シーケンスは、ランレングス制限コード化制約に違反するビットの連続したシーケンスを含み、前記違反シーケンスの位置を特定することはさらに、
前記違反シーケンスの位置を特定することを含む、請求項６に記載の方法。
【請求項８】
前記インジケータを挿入することは、
ｋビットの前記違反列を、前記ビットアドレスから開始するｋビットの前記符号語と置換えることと、
前記インジケータを構築することと、
前記アドレステーブルポインタから開始する前記インジケータを挿入することと、
新しいビットアドレスを指し示すために前記アドレステーブルポインタをｋだけ進めることとを含む、請求項７に記載の方法。
【請求項９】
前記インジケータは、保護ビットと、アドレスフィールドと、終了フラグとを含む、請求項８に記載の方法。
【請求項１０】
アドレスフィールドの長さはｋ−２ビットである、請求項８に記載の方法。
【請求項１１】
アドレスフィールドは、前記違反シーケンスの最初のビットアドレスを識別する、請求項８に記載の方法。
【請求項１２】
前記保護ビットの値は１であり、前記終了フラグの値は最初は０であり、前記終了フラ
グは、追加の違反列が検出されると１に変更される、請求項９に記載の方法。
【請求項１３】
前記違反シーケンスの最初のビットのビットアドレスが対応するアドレステーブルポインタに等しい場合には、前記違反列のビットは前記インジケータと置換えられる、請求項８に記載の方法。
【請求項１４】
ａ） 前記違反シーケンスの最初のビットのビットアドレスが対応するアドレステーブルポインタに等しくない場合、および
ｂ） 前記ビットアドレスが前記対応するアドレステーブルポインタ未満である場合、および
ｃ） 前記ビットアドレスが前記対応するアドレステーブルポインタ−ｋよりも大きい場合、
前記アドレステーブルポインタから開始し、前記違反シーケンスの最初のビットのビットアドレスまでであるが前記違反シーケンスの最初のビットのビットアドレスを含まないビットと前記違反シーケンスのビットを置換え、前記違反シーケンスの置換えられたビットは、アドレステーブルポインタ＋ｋに隣接する１つのビットアドレスから開始して置換えられる、請求項８に記載の方法。
【請求項１５】
前記アドレスはビットアドレスであり、Ｎ＞２k-2の場合、前記違反列のビットアドレスはＮ−２k-2だけ減らされる、請求項８に記載の方法。
【請求項１６】
データの符号語を符号化および復号化するように動作可能な媒体装置において、媒体に書込まれるべきデータの符号語を復号化するための方法であって、
Ｎビットのデータを含む語を受取ることと、
前記語においてインジケータシーケンスを識別することとを備え、前記インジケータシーケンスは違反シーケンスのアドレスを含み、前記方法はさらに、
インジケータから前記違反シーケンスのアドレスを抽出することと、
前記アドレスにおいて前記違反シーケンスを挿入することとを備える、方法。
【請求項１７】
前記違反シーケンスが挿入される前に、前記インジケータを前記アドレスにおけるビットと置換えることをさらに備える、請求項１６に記載の方法。
【請求項１８】
前記方法は、
前記アドレスが抽出される前に、前記インジケータシーケンスの最初のビットアドレスを指し示すようにアドレステーブルポインタを設定することをさらに備え、
前記アドレスによって指定されるビットアドレスから開始するｋビットの前記語は、前記インジケータシーケンスを置換えるために使用され、
ｋビットの前記違反シーケンスは前記アドレスにおいて前記語に挿入される、請求項１７に記載の方法。
【請求項１９】
前記違反シーケンスはｋ個の０である、請求項１８に記載の方法。
【請求項２０】
前記語は先頭に付加されたビットをさらに含み、前記先頭に付加されたビットの値は、前記語が復号化を必要とするかどうかを判断するために利用される、請求項１８に記載の方法。
【請求項２１】
前記語が復号化を必要とするかどうかを判断することは、
前記先頭に付加されたビットを調べることと、
前記先頭に付加されたビットが０に等しい場合に前記符号語を復号化することとを含む、請求項２０に記載の方法。
【請求項２２】
前記アドレスが前記アドレステーブルポインタと同じビットアドレスを指し示す場合に、前記インジケータシーケンスのビットは前記違反シーケンスと置換えられる、請求項１８に記載の方法。
【請求項２３】
ａ） 前記アドレスが対応するアドレステーブルポインタに等しくない場合、および
ｂ） 前記ビットアドレスが前記対応するアドレステーブルポインタ未満である場合、および
ｃ） 前記ビットアドレスが前記対応するアドレステーブルポインタ−ｋよりも大きい場合、
最も右の違反シーケンスから前記インジケータシーケンスの最後までの違反列シーケンスのビットと前記インジケータシーケンスのビットを置換える、請求項１８に記載の方法。
【請求項２４】
前記インジケータシーケンスは、保護ビットと、終了フラグとをさらに含む、請求項１６に記載の方法。
【請求項２５】
前記インジケータシーケンスは、最後に符号化されたインジケータシーケンスであり、前記最後に符号化されたインジケータシーケンスの位置は、前記最後に符号化されたインジケータシーケンスにおける終了フラグの値によって前記語において特定される、請求項２４に記載の方法。
【請求項２６】
前記最後に符号化されたインジケータシーケンスにおける前記終了フラグの値は１である、請求項２５に記載の方法。
【請求項２７】
Ｎ＞２k-2の場合、前記アドレスはＮ−２k-2だけ増やされる、請求項１８に記載の方法。
【図１】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図２Ｄ】
【図３Ａ】
【図３Ｂ】
【図４】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図５Ｄ】
【図６Ａ】
【図６Ｂ】
【図７Ａ】
【図７Ｂ】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図２Ｄ】
【図３Ａ】
【図３Ｂ】
【図４】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図５Ｄ】
【図６Ａ】
【図６Ｂ】
【図７Ａ】
【図７Ｂ】
【公開番号】特開２００８−２０４５９３（Ｐ２００８−２０４５９３Ａ）
【公開日】平成２０年９月４日（２００８．９．４）
【国際特許分類】
【外国語出願】
【出願番号】特願２００７−３３９４８９（Ｐ２００７−３３９４８９）
【出願日】平成１９年１２月２８日（２００７．１２．２８）
【出願人】（５９１１７９３５２）クウォンタム・コーポレイション (49)
【氏名又は名称原語表記】ＱＵＡＮＴＵＭ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２０年９月４日（２００８．９．４）
【国際特許分類】
【出願番号】特願２００７−３３９４８９（Ｐ２００７−３３９４８９）
【出願日】平成１９年１２月２８日（２００７．１２．２８）
【出願人】（５９１１７９３５２）クウォンタム・コーポレイション (49)
【氏名又は名称原語表記】ＱＵＡＮＴＵＭ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]