JPH04501044A - 延長形バーストトラッピング - Google Patents

Abstract

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

Description

【発明の詳細な説明】 延長形バーストトラフピング 発明の背景 誤りトラッピングは誤り検出及び訂正の技術における周知の技法である。それは 、例えば、ＭＩＴプレス、１９８４年発行、ビータソン及びウヱルドン著［誤り 訂正用符号」（Ｐｅｔｅｒｓｏｎ　ａｎｄ　Ｗｅｌｄｏｎ＋Ｅｒｒｏｒ−Ｃｏｒ ｒｅｃｔｉｎｇ　Ｃｏｄｅ、Ｔｈｅ　ＭＩＴ　ＰｒｅｓｓB １９８４）の２３７〜２４０及び３６４〜３６７ページに記載されている。適用 可能なときには常に、誤りトラッピングは高度に？ｊ！雑な誤り訂正アルゴリズ ム、例えば、マグロ−ヒル、１９６８年発行、バーレカンブ著［代数符号化理論 Ｊ　（Ｂｅｒ−１ｅｋａｍｐ、　Ａｌｇｅｂｒａｉｃ　Ｃｏｄｉｎｇ　Ｔｈｅｏ ｒｙ＋ＭｃＧｒａｗ−Ｈｉｌｌ＋　１９６８）の１８４ページに記載されたよう なバーレカンプ・キ一方程式解法アルゴリズム、又はバーレカンプ（Ｂｅ−ｒｌ ｅｋａｍｐ）及びウェルシユ（Ｗｅｌｃｈ）による米国特許第４６６３４７０号 の主題であるウェルシェーバーレカンブ・アルゴリズム、又はユークリッドのア ルゴリズム、を復号器が実行する必要をなくする。そのようなアルゴリズムの実 行を回避することは時間及びオーバヘッドにおけるかなりの節約を意味する。

誤りトラッピングの背後の意味はこれである。受信符号語が、これのメツセージ 記号のすべてが正しく且つ誤りが二三の検査記号において現れるにすぎないよう なものであるときには、符号器を通る受信符号語全体を移動させると、誤りを持 った受信符号語検査記号に対応するものを除いてはすべて０である一組の新しい 検査記号（又は、より正確には、剰余記号）が生じる。（ここで使用されたよう な用語「新しい検査記号」は、このように生成された記号が実際には受信符号語 全体を符号生成多項式で除算した後に残された剰余を定義する「剰余」記号であ るので、実際上誤作である。用語「検査記号」は通常、符号語のメツセージ部分 だけを符号生成多項式で除算した後に残された剰余を意味する。）新しい検査記 号は厳密には誤りパターンに等しい、それゆえに、誤り訂正は平凡に、受信符場 語における対応する位置に非ゼロ新検査記号を単に加えることによって達成され る。

受信符号語のメツセージ部分において発生する誤りを捕えるためには、符号器（ 典型的には各符号語における検査記号の数に正確に等しい多数の帰還段を持つた シフトレジスタ）はこれの内容が検査記号の総数（「）の半分ｂ／２）以下の非 ゼロ記号パターンを除いてはすべて０になるまで単に移動される。この非ゼロ記 号パターンは、定義によって、対応する移動（シフト）シた符号語位置に発生す る誤りパターンである。誤った記号が受信符号語の検査部分に発生したならば、 符号器レジスタの移動（けた送り）は必要でない、誤りが検査記号に隣接した最 後のメツセージ記号において発生したならば、符号器は１度だけ移動されること が必要である。誤りが符号語における正に最初のメツセージ位置において発生し たならば、符号器は誤りを捕えるために符号語におけるメツセージ記号の数に等 しい回数だけ移動されなければならない。

によ　て　°　れるべ　ｌ 誤り捕獲の明白な限界は誤りの連続したストリング（「バースト」ンの長さが、 誤り訂正が保証されるべきであるならば、ｒ　／　２記号を越えることができな いことである。更に、受信符号語におけるすべての複数の誤りが再符号器におい て同時に「捕獲」されなければならないので、連続又は不連続の複数の誤りパタ ーンは符号器シフトレジスタの長さを越えることができない（この長さは符号語 における検査記号の数ｒである）、そうでなければ、誤り訂正は保証され得ない 。

不幸にも、複数の誤りのすべてのパターンがこの長さを越えないことは保証され 得ない。問題は誤り捕獲法を利用してｒ／２記号より大きい長さの連続した誤り バーストを訂正する方法である。

発明の要約 肱」詑堕 まず第一に、この発明は最初に、誤り捕獲技法を用いた誤り訂正が従来技術にお いては誤リバーストが長さにおいてｒ　／　２記号を越えない場合に限られる理 由に立ち返ってこれを考察することを必要とする。その理由は、符号器シフトレ ジスタにおいてはｒ／２未満のゼロ値記号のストリングがその適当な数のシフト の後に結局生成されるかもしれないが、そのような場合におけるゼロ値記号のあ るものが実際には受信符号語における対応する位置にある誤りのない記号の誤表 示であり得るかもしれないことである。そのような発生時には、符号器シフトレ ジスタにおける非ゼロ値記号は受信符号語における誤りパターンを正確に表さず 、従って上述の誤り捕獲技法に従って使用されたならば完全な誤り訂正を与えな い。

これが、誤りトラッピングが従来技術においては誤りバーストが長さにおいて１ ７２未満の記号である場合だけに限られている基本的な理由である。

この発明における次の段階は、ｎが符号語における記号の数であり且つＢが上述 の誤り捕獲技法に従って最適数のシフトの後に符号器シフトレジスタに収容され ているゼロ値記号の数であり、且つＢがｒ　／　２未満であるという条件で（但 し、ｒは符号語における検査記号の数である）、そのような発生の確率がｎ　＋ ｌ　−＋１−　＋１に比例していることを認識することである。もちろん、Ｂが ｒ　／　２以上であるならば、そのような発生の確率は零である。

この発明における更なる段階は、たとえ前述の確率が精密に０でなくても、例え ば２−１４のような、許容可能に小さい数であるかぎり、誤り捕獲技法が有効で あり得ることを認識することである。

前述の洞察を用意したうえで、この発明は次のように進行する。まず、この発明 は比較的大きい数の記号を持った符号だけを使用する。−例は２５５記号を持っ たり一ドーソロモン（Ｒｅｅｄ−３ｏｌｏｓｏｎ）符号であり、これにおいては 各符号語における最後の１６記号が検査記号を構成しており、且つ各記号が８ビ ツトバイト又は「キャラクタ」である、（用語「キャラクタ」は今度はこの明細 書の残りの部分全体において使用される。）次に、誤り捕獲を行う前に、この発 明は符号器シフトレジスタにおいて誤りゼロ値キャラクタを発生する確率におけ る許容可能な上限を指定することを使用者に要求する。この確率に対して２−ｚ ４の上限を選ぶならば、例示的リード−ソロモン２５５符号を用いて、Ｂ＝４で ある。それゆえ、少なくとも四つのゼロ値キャラクタの連続したストリングが符 号器シフトレジスタにおいて発生されるまで符号器シフトレジスタが上述の誤り 捕獲技法に従ってシフトされることが単に要求される。

四つのゼロ値キャラクタが（これの最適数のシフトの後に）符号器シフトレジス タにおいて発生され得るかぎり、誤り表示の確率は、Ｐ　＝（ｎ＋１）　−１ｍ −１ｌ＝２５６”−”＝２−”によって与えられ、これは使用者により選ばれた 上限を満足する。

多くの応用に対して、２−２４の誤り訂正復号器出力における見逃しビット誤り 率は完全に許容可能である。一般的な場合には、誤り表示の確率は、（最適数の シフトの後に）符号器シフトレジスタにおいて発生されるべき連続したゼロ値キ ャラクタの最小所要値がたとえ従来技術において必要とされる最小数（すなわち 、長さにおいてｒ　／　２キヤラクタ）よりはるかに下であるとしても、選ばれ た符号長が十分に長いかぎり無視可能である。

前述の例において、この発明に従って行われる誤りトラッピングはやはり従来技 術における最大訂正可能バースト誤り長であるかぎリバースト誤りを半分訂正す ることができ、これは以前では可能とは考えられなかった重要な改善である。

イン　１−プエ、　におしる　パ　−ンの−この発明の最も劇的な利点はインタ リーブ式符号において実現される。インタリーブ式符号においては、周知のよう に、使用者メツセージがブロックに分割されて各ブロックが符号語へと符号化さ れた後、符号語の各群は送信前に互いにインタリーブされて、各符号語における キャラクタが連続して送信されないようになっている。符号語の各群はブロック として処理されて、インタリーブの深さＤはブロック当りの符号語の数である。

−例として、１ブロツクの符号語が受信されてこのブロックにおける符号語のた だ一つがこの発明の誤り捕獲技法を用いて復号化され得るような場合を考える。

そのような場合には、そのブロックにおける他の符号語のいずれも符号器シフト レジスタの最大数（ｎ）のシフト後にさえ符号器シフトレジスタにおいてゼロ値 キャラクタのストリングを発生しないであろうが、そのブロックにおけるその一 つの符号語は、上述の誤り捕獲技法に従って、符号器シフトレジスタのある数の シフトの後符号器シフトレジスタにおいて少なくとも最小数（例えば、四つ）の 連続したゼロ値キャラクタを発生するであろう。

これまでに説明されたこの発明の特徴に従って、少なくともその一つの符号語が この発明の誤り捕獲技法を用いて直接訂正可能であることは直ちに明らかである 。すなわち、符号器シフトレジスタにおける非ゼロ値キャラクタのすべてをそれ における対応する位置に配置された受信符号語における記号に加えるだけでよい 、質問は、ブロックにおける残りの「復号不可能な」符号語をどう処理すればよ いかである。

答えは、ブロックにおける「復号不可能な」残りの符号語に対して、（一つの訂 正可能な符号語から）シフトレジスタにおいて生成された非ゼロ値キャラクタの 位置をブロックにおける残りの「復号不可能な」符号語のすべてに対する消去位 置として指定することである。これらの消去位置は通常の誤り復号器に送られる （この後号器は、例えばこの明細書の第１ページに記載されたウェルシューバー レカンプ・アルゴリズム、又は技術上周知の他の任意の適当なアルゴリズムを使 用することができる）、このような復号器は次に、全記述されたばかりの方法で 導出された消去位置を考慮に入れて、一度に一つずつ残りの「復号不可能な」符 号語のそれぞれを復元（訂正）し始める。消去位置がｒ記号より大きい長さの誤 りバーストに対応しないかぎり、この明細書の第１ページにおいて引用されたバ ーレカンプの教科書の２３１ページに記載されたもののような復号化アルゴリズ ムがブロックにおける残りの「復号不可能な」な符号語のそれぞれにおけるすべ ての誤りを訂正する。それゆえ、この発明は、以前には従来の技法を用いては復 号不可能であったような、受信インタリーブ式符号語ブロックにおける誤りのパ ターン全体を解決する。

ここで適用可能な原理は、符号器シフトレジスタを通して一つの「復号不可能な 」符号語をシフトすることによって得られた非ゼロ値キャラクタのストリングが 、同し符号語位置を通ってインタリーブ式ブロックにおけるすべての符号語と交 錯する誤リバーストの位置に対応しているという認識である。それゆえ、プロ７ りに少なくとも一つの「復号可能な符号語、すなわち（上述のリード−ソロモン ２５５符号の例においては）１２以下の長さの誤リバーストを持った一つの符号 語が存在するかぎり、この発明の誤り捕獲技法を使用して、ブロックにおける一 つの「復号可能なＪ符号語を訂正するだけでなく、ブロック全体に対するバース ト誤り位置を同定する。ことができる。このように導出され且つ消去位置として 復号器に送られた誤りバースト位置は復号器がｒもの誤り、すなわち（上に引用 された）バーレカンブの教科書の２３１ページに記載されたような、誤り位置が 事前に未知である場合における２倍もの誤りを訂正することを可能にする。

典型的には、検査キャラクタの数ｒがブロック当りの符号語の数りによって除電 された最長予想バースト誤り長を越えている符号が選ばれる。この場合には、た とえ残りの「復号不可能な」符号語がこのように導出された位置におけるバース ト誤りだけでなく他の「任意の」位置における一つ又は二つの誤りを含んでいた としてもこの発明に従ってブロックにおける残りの「復号不可能な」符号語を訂 正することができる。これは、ｓ＋２ｔがｒ以下であるかぎり復号器がＳ消去及 びｔｆｉりを訂正することができるからである０例えば、「が１６の検査キャラ クタに等しく且つ一つの「復号可能な」符号語から導出された誤すバースト長（ 消去の数）Ｓが１２記号の長さである（従って符号器シフトレジスタにおける少 なくとも四つの連続したゼロ偵キャラクタという我々の基準が満足される）なら ば、復号器は（Ｓ消去位置を用いて）ブロックにおける「復号不可能な」残りの 符号語のそれぞれを、これが長さ１２の予測バースト誤りだけでなく、これに加 えて符号語の他の任意の位置における一つ又は二つもの誤った記号を有すること があるにもかかわらず、訂正する。

この誤った記号の存在は、一つの「復号可能な」符号語が上述の方法で前に導出 されたパースＨ％り位置以外の位置に誤りを有することの２−＊ａ以下の確率に よって特徴づけられていたので、起こりそうなことである。このような事情であ るから、誤り率がブロックにおけるすべての符号語に対して同じ位置において非 常に低く又はゼロであったことは事実上はとんど確かである。それゆえ、ブロッ クにおけるすべての符号語に対してバースト誤り位置の予測ストリングのせいぜ い外側の位置に一つ又は二つのキャラクタの確率的誤りが予想されるだけであろ う。

結果として、その発明は従来技術においてはそれほど容易に訂正をすることがで きなかったインタリーブ式ブロックの符号語における誤りのパターンを「解決」 して訂正することができる。

図面の説明 この発明は添付の図面の参照によって理解されるであろうが、その図面中、図１ は従来技術の誤り捕獲用復号器の構成図であり、図２は誤り捕獲の原理を図解し た線図であり、図３はこの発明の採択実施例を図解した構成図であり、図４はこ の発明によって容易に訂正される図３のシステムにおいて受信された例示的誤り パターンを図解しており、又図５８及びｂは図３のシステムにおける制御処理装 置の動作を図解した流れ図である。

詳細な説明 １岨」肥 図１に言及すると、受信符号語１２０はｎキャラクタを有しており、そのうちの 四つが符号生成多項式に従って（使用者データである）残りのにキャラクタが計 算された冗長検査キャラクタを構成している。受信符号語１２０は典型的なり一 ドーソロモン再符号器１２２の四つの段を通してシフトされるが、この再符号器 には符号生成多項式の係数８゜＋　ｇ＋＋　ｇ！＋＋＋、＋＋１ｇＦ−＋に従っ て周知の方法で帰還が施されている。受信符号語１２０のすべてのｎキャラクタ が再符号器１２２の１段をシフトさせられた後、再符号器１２２の各段の内容は 受信符号語１２０のｒ剰余の対応する一つを含んでいる。受信符号語に「／２以 下の誤ったキャラクタがあり、且つ誤ったキャラクタのすべてが互いの「位置内 にあるならば、誤りのすべては通常の誤り捕獲法によって訂正され得る。この過 程において、スイ・ンチ１２６が開かれて（再符号器１２２を分離し）、そして 再符号器の内容は右から左へ１位置だけシフトされる。これは図２において示唆 された方法で符号器を通して符号語を循環的にシフトすることとみなされること ができる。それぞれのそのようなシフトにより、１段１２４（図１）の内容は変 化する。誤りがすべて捕獲されると、段１２４は符号語における受信した誤りに 対応する位置を除いてすべてのゼロを収容して、ｒの「仮想検査キャラクタ」を 含むことになる。

再符号器１２２の各シフトは、符号語１２０に重なるものとみなされ得るキャラ クタ長ｒの窓１２Ｂの１位置だけのシフトと対応する。窓１２Ｂ内の符号語位置 は仮想検査位置と呼ば娠且つ残りの符号語位置は仮想メンセージ位置と呼ばれる 。窓１２８が符号語１２０における誤ったキャラクタのすべてに同時に重なるや 否や、１段１２４の内容（すなわち、仮想検査キャラクタ）は符号語１２０にお ける誤り位置に対応するものを除いてすべてゼロになる。

組合せ論理回路１３０はｒのゼロ検出器１３２によりそのような各シフトのある 段１２４のそれぞれの内容を検査する。すべての誤りが捕獲された（すなわち、 段１２４の限定数以下のものを除いたすべてのものがすべてゼロを収容している ）ことをゼロ検出器＋３２が示すや否や、組合せ論理回路は段１２４の非ゼロ現 在内容のすべてを符号語１２０についての窓１２Ｂの現在の（シフトした）位置 内の対応する符号語位置に加える０例えば、再符号器１２２の数シフトの後にゼ ロ検出器１３２が、最初の段１２４Ａを除いて１段１２４のすべての内容がゼロ であることを見つけたならば、組合せ論理回路１３０は段１２４Ａの内容を、窓 １２８における「最初の」位置である位置１２０Ａに現在ある受信符号語キャラ クタに加える。その結果は訂正された符号語である。

′　の　の 問題はもちろん、すべての連続した誤リバーストがｒ　／　２キヤラクタ以下の 長さであること、又は所与の受信符号語における二つの誤ったキャラクタが「の 符号語位置より多く離れていないことを保証することができないことである（但 し、「は符号語シフトレジスタの長さである）、それゆえ、任意の受信符号語に おける複数の誤りが再符号器シフトレジスタにおいて同時に捕獲され得ることは 保証され得ない、誤り捕獲法はそのような場合におけるすべての誤ったキャラク タの誤り訂正を保証することができない。

問題は、誤りバースト長がｒ　／　２キヤラクタを越える場合に（誤り捕獲法が 誤り訂正を保証することができないときに）多重誤り捕獲法を使用する方法であ る。

ζ−Ω−光一朋 図１の誤り捕獲用復号器の能力は、比較的大きい数（ｎ）の記号によって特徴づ けられているリード−ソロモン２５５のような符号語を選択し、且つゼロ値検査 キャラクタの最小所要数を（従来技術において必要とされる）ｒ／２からｒ／２ よりかなり小さいある数に低減することによってかなり高められる。１６の検査 キャラクタを持ったり一ドーソロモン２５５符号の場合には、符号器シフトレジ スタにおいて最適数のシフトの後に発生された少なくとも四つの（すなわちｒ／ ４の）ゼロ値仮想検査キャラクタが存在するかぎり、これらのゼロ値キャラクタ の一つが誤り表示である確率は２−ｔ４であり、これは多くの応用に対して復号 器出力における許容可能な剰余ビット誤り率に対応する。

イン　１−ブ工、　への・ この発明の採択実施例は図３に図解されている０図３の例示において、データは 五つのインタリーブ式符号語の各ブロックにおいて通信路（チャネル）を通して 伝送され、それぞれの全長Ｒ３２５５は１６の検査キャラクタを含む２５５のキ ャラクタを持っており、各キャラクタは８ビツトからなっている０図３において 、通信路から受信された到来データは並列に配列された２５５の直列シフトレジ スタ１００からなる（周知の形式の）インタリープ解除用直列−並列シフトレジ スタ配列を用いてインタリーブ解除される。各シフトレジスタ１００は図３に示 された「ｘ」方向において直列方式で五つの８ビツトキヤラクタ１００を記憶し 、転送する。２５５の直列レジスタ１００は更に五つの並列レジスタの方法で動 作し、これのそれぞれは２５５の８ビツトキヤラクタを配列における他のレジス タのすべてを並列に「Ｙ」方向において直列方法で記憶し、転送する。

図３に示されたように、到来インタリーブ式データは左から右へ最上部シフトレ ジスタ１００ａを通って直列方法で転送され、次に次のシフトレジスタ１００ｂ の左側に送られ、そこから再び左から右へ転送され、そしてレジスタ１００の配 列全体を通って直列にくねり進んで、ついには最下部レジスタ１００ｚに達する 。

図４に言及すると、レジスタ１００の配列は五つのインタリープ式符号語のちょ うど一つのブロックを記憶するのにちょうど十分な長であり、各符号語は２３９ のメツセージキャラクタ及び１６の検査キャラクタからなっており、各キャラク タは８ビツトからなっており、２３９メツセージキヤラクタ及び１６検査キヤラ クタの各集合が一つの符号語を構成していて、各符号語はＹ方向において垂直な 列に配列されている。各符号語の１６検査キヤラクタは図４に示されたように配 列における五つの符号語の各垂直列の最下部の１６のキャラクタ位置に配置され ている。

技術上周知であるそのようなインタリープの利点は、誤りの連続的バーストを引 き起こす通信路における干渉が図４のブロックにおける符号語のそれぞれの一部 分だけを「消し去る」のであって、この符号語の一つを完全に消し去ってこれを 訂正する望みをなくするのではないということである。ブロックにおける五つす べての符号語の間で誤りを分けることによって、十分の正しいキャラクタが各符 号語に残っていて訂正を可能にすることが期待される。

スイッチ２００が準備されていて、レジスタ１００の配列に記憶された五つの符 号語の任意の一つを制御処理装置２１０に送ることができる。制御処理装置２１ Ｏは図１に図示され且つ前に記述された形式の符号器シフトレジスタ２２０と関 連している。符号器シフトレジスタ２２０は、図１に関連して前に論述されたよ うに、符号器シフトレジスタ２２０を通って左から右ヘシフトされる一連のキャ ラクタの、選ばれた符号生成多項式による除算を行うために図３には図示されて いない（が図１に図示されている）装置を備えている。制御処理装置２１０はス イッチ２００を制御して、レジスタ１００の配列に記憶された五つの符号語の任 意の一つを符号器シフトレジスタ２２０へ移すようにする。

制御処理装置２１０は更に誤り訂正復号器２３０及び記憶装置２４０に接続され ている。

制御処理装置２１０はこの発明に従って次のように誤り訂正を開始する。まず、 それは到来するインタリープ式ブロックの符号語が前に説明された方法でレジス タ１００の配列を通ってくねくねと転送されて最後には一つの完全なブロックが 配列に記憶されるようになることを可能にする。これが行われると、配列は制御 処理装置２１０に応答するスイッチ２４０によって到来データから分離される。

次に、制御処理装置２１０はスイッチ２００を用いる配列から一度に一つの符号 語を選択して、対応する垂直列のレジスタ位置をＹ方向に垂直にシフトさせるの で、選択された符号語はスイッチ２００を通過して符号器シフトレジスタ２２０ に送られ、図１に関連して前に与えられた説明に従ってこれを通過してシフトさ れるようになる。それゆえ、制御処理装置２１０はレジスタ１００のインタリー ブ解除用配列に記憶された五つの符号語のそれぞれを、一度に１符号語ずつレジ スタ２２０の符号器を通じてＹ方向に垂直下方ヘシフトさせる。

′　几　のアルゴｌズム 制御処理装置２１０は次の動作に従ってブロックにおける五つすべての符号語の 誤り訂正を行う。

１、ブロックにおける符号語のそれぞれに対して、制御処理装置２１０は、ａ、 符号器シフトレジスタ２２０を通して符号語を１回シフトして、符号器シフトレ ジスタ２２０においてｒ（この場合にはｒ＝１６）の剰余キャラクタを生成する ようにし、 ｂ、符号器２２０を（スイッチ２００により分離して、符号器シフトレジスタ２ ２０を図１に関連して前に説明された方法でシフトすることを開始して連続した ゼロ埴仮想検査キャラクタの可能な最長のストリングが符号器シフトレジスタに 存在するようにし、そして対応する非ゼロ仮想検査キャラクタを対応する符号語 位置におけるキャラクタに加えて符号語を訂正するようにし、しがしＣ８符号器 シフトレジスタ２２０をｎ（この場合にはｎ＝２５５）回シフトした後に最小長 （この例では４キヤラクタの最小長）の連続したゼロ値仮想検査キャラクタのス トリングを生成すること力呵能でないならば、制御処理装置２２０は一時的にこ の符号語の処理を延期してブロックにおける次の符号語に移り、処理を繰り返す 。

２、最小長のゼロ値仮想検査キャラクタの連続的ストリングがブロックにおける ５符号語の少なくともｊ番目のものに対して生成されるかぎり、制御処理装置２ １０は最小長のゼロ値仮想検査キャラクタの連続的ストリングを生成することが できなかったブロックにおける他の符号語に対する消去位置としてｉ番目の符号 語における対応する非ゼロ偵仮想検査位置を指定する。

３、制御処理装置２１０は次にブロックにおける残りの符号語を一度に一つずつ 次のように訂正する。

ａ、制御処理装置２１０は符号器シフトレジスタ２２０において前に計算された 対応する剰余を誤り訂正復号器２３０に送り、且つす、制御処理装置２１０は、 ブロックにおけるｉ番目の符号語に対して消去位置として前に生成された非ゼロ 埴仮想検査キャラクタの位置を復号器２３０に送り、且つ ｃ、！準誤り訂正アルゴリズムに従って訂正キャラクタＹｅ及び対応する誤り位 置Ｌｅの集合を生成するように誤り訂正復号器２３０に信号を送る。処理装置！ ２１０は位置Ｌｅを使用して各符号語における誤ったキャラクタの位置を正確に 示し、対応する符号語キャラクタにこれがレジスタ１００の配列がら送り出され るときに排他的０Ｒｖｏｄ２加夏器３００において対応する誤りパターンＹｅを 加える。

イン　リープ　にお番るバースト　の 図４は従来の技法を用いて誤り訂正を容易にすることができない典型的なバース ト誤り状況を図解している。

図４において、ブロックにおける５符号語は、符号語＃２を除いて、個別に誤り 訂正することができない、しかしながら、符号語＃２は誤り訂正が可能であり、 符号器シフトレジスタ２２０のｊ番目のシフトのときに、それにおいて４ゼロ値 仮想検査キヤラクタのストリングを生成する。

図４において、簡単のために、符号語の五つすべてがｊ符号語キャラクタ位置だ け（図２の方法で）Ｎ環的にシフトされており、従って五つの垂直並列レジスタ （Ｙ方向）のそれぞれにおける最後の（最下部の）キャラクタ位置が、原初符号 語位置からｊ位置だけシフトされた】６の仮想検査キャラクタ位置に対応してい ると仮定する。符号語＃２における最初の１２の仮想検査キャラクタ位置は符号 語＃２における長さ１２の誤りバーストに対応して非ゼロである。

この発明に従って、誤りバーストがブロックの五つすべての符号における同じ符 号語位置のすべてではないとしても最多数のものに発生していることは大いにあ りそうである。従って、制御処理装置２１０は五つすべての符号語における（図 １及び２の「窓Ｊ１２８のｊシフトに対応する）最初の１２の仮想検査キャラク タ位置を誤り訂正復号器２３０への消去位置として指定する。符号がリード−ソ ロモン符号であると仮定すれば、このように導出された１２消去位置を備えた復 号器２３０は、１２の消去だけでなく、（ここで以前に論述されたように）四つ の残りの符号語のそれぞれにおける他の位置に配置された二つもの付加的な誤っ たキャラクタを訂正することができる。そのような確率的に配置された誤りは図 ４において平行斜線で図示されている。

唯一の要件は、符号語＃２がこの発明に従って誤り捕獲の可能である誤りパター ンを持っていることである。明確には、確実性のために、少なくとも四つの連続 したゼロ値仮想検査キャラクタが符号器シフトレジスタのある最適数のシフト時 に生成されたならば、符号語＃２はバーストにおいて１２以下の誤ったキャラク タを持っていなければならず、更にバースト位置の外側の任意の位置に他の誤っ たキャラクタを持つことができない。

呵纒処理装置曵動作 図５ａ及び５ｂは記憶装置２４０を備えた処理装置２１０の動作を大変詳細に図 解している０図５に言及すると、処理装置２１０は到来データの５符号語のブロ ックを前に説明された方法でレジスタ１００の配列へ直列蛇行方式でロードする 。（ブロック４００）　次に、処理装置は二つの指標ｉ及びｊを両方共ｌに等し くセットする。（ブロック４０５）　図５ａの凡例に記載されたように、指標ｉ はブロック内の５符号語の個個のものを指定し、ｌないしＤの範囲を持っており 、ここでＤはブロック当りのインタリープ式符号語の数、この例では５、である 。

次に、処理装置２１０はｉ番目の符号語を符号器シフトレジスタを通して１回シ フトさせ、そしてこの符号語をシフトレジスタ１００の配列における原初位置に 戻す、（ブロック４１０）　処理装置２１０は次に符号器シフトレジスタ２２０ を分離する。（ブロック４１５）　次に、処理装置２１０は符号器シフトレジス タ２２０において生成された連続したキャラクタの数（Ｎ　ｊ　）を計数する９ Ｍｊは、図５ａの凡例に記載されたように、符号器のｊ番目のシフト時に符号器 において生成された連続したゼロキャラクタの数を表している０次に処理装置２ １０は符号器シフトレジスタのシフトの数（ｊ）が符号語当りの記号の数ｎに等 しいか否かを決定する。（ブロック４２５）　等しくなければ、処理装置２１０ は符号器シフトレジスタを１キヤラクタ位置だけシフトさせ（ブロック４３０） 、指標ｊを１だけ増分しくブロック４３５）、そしてブロック４２０に戻って符 号器シフトレジスタ２２０に存在するゼロ値キャラクタの数を計算する。このシ フト及び計数動作ループ（箱形４２０．４２５，４３０，４３５）は符号器シフ トレジスタ２２０のｎ回ものソフトまで続き、その間にＮｊのすべてが記憶され る。ｊがｎ（この例では偶然符号におけるキャラクタの数に等しい符号語当りの キャラクタの数）の値に達すると、処理装置はブロック４２５からブロック４４ ０へのＹＥＳ（イエス）分岐をとり、この点で処理装置２１０はＮｊのいずれか が使用者により要求された最小数のゼロ値仮想キャラクタより大きかったかどう かを決定する。前にＲ３２５５符号の例に関連して論述されたように、連続した ゼロ値仮想検査キャラクタの最小数は、誤り表示の最小限の許容可能な確率、こ の例では２）４、を与えるように４（又はｒ　／　２より小さい他の任意の数） のように選ばれることができる。

Ｎｊのいずれも４より大きくないならば（換言すれば、符号器シフトレジスタの ｎシフトのいずれもゼロ値仮想検査キャラクタの十分に長いストリングを生成し ない−従ってｉ番目の符号語が「復号不可能」であることが示されている−なら ば）、符号器はブロック４４０のＮｏ（ノー）分岐をとり、現在の符号語の指標 ｉを記憶装置２４０の表２における復号不可能な符号語の指標ｌ′として記憶す る。（ブロック４４５） 他方、Ｎｊの少なくとも一つが所要数４（この例では４）に少なくとも等しかっ たならば、処理装置２１０はブロック４４０のＹＥＳ分岐をとり、ｉ番目の符号 語に対するＮｊのどれが最大であったかを決定しくブロック４５０）、そしてｊ のその値を記憶装置２４０の表１における指標ｊ′として記憶する。更に、処理 装置２１０は記憶装置２４０の表１に、符号器シフトレジスタ２２０のｊ′シフ ト時に符号器シフトレジスタにおいて生成された非ゼロ仮想検査キャラクタの値 及び符号語位置Ｌｉを記憶する０図２に言及すると、非ゼロ仮想検査キャラクタ の符号語位置Ｌｉは窓１２Ｂ内の各位置数にｊを加えることによって窓１２８内 のそれらの位置から計算されることができる。別の方法として、符号器シフトレ ジスタ２２０を通ってシフトされるときの各記号の絶対的符号語位置を単に追跡 してもよいであろう、（図５ａのブロック４５５）処理装置２１０は次に、符号 語指標ｉがインタリーブの深さくブロック当りの符号語の数）Ｄ（この例ではｎ ＝５）に達したか否かを決定する。（ブロック４６０）否であれば、処理袋Ｗ２ １０はブロック４６０のＮＯ分岐をとり、符号語指標ｉを１だけ増分しくブロッ ク４６５Ｌそしてブロック４１０に戻って次の符号語について過程全体をそっ（ り再び開始する。過程はすべての符号語がそのように処理されてしまうまで何度 も何度も繰り返され、そしてこの処理されてしまった点においては符号語指標ｉ はブロック４６０におけるＤに等しい、この点において、処理装置２１０はブロ ック４６０のＹＥＳ分岐をとって図５ｂにおけるブロック５００に進む。

ブロック４４０に戻って、前に言及したように、連続したゼロ値仮想検査キャラ クタのストリングが符号器シフトレジスタ２２０を通っての符号語のシフトの任 意のものにおいて生成されないならば（換言すれば、Ｎｊのいずれも最小所要数 を満たさないならば）、処理装置２１０はブロック４４０のＮｏ分岐をとり、そ の符号語の指標ｉを記憶装置２４０の表２における指標ｉ′として記憶する。

（ブロック４４５）　次に、ｉ′のその値に対して、処理装置２１０は（シフト 指標ｊ−１に対応して）符号器シフトレジスタに存在するキャラクタの最初の集 合を、表２におけるそれらの位置Ｌｓと共に、剰余キャラクタとして記憶する。

（これらの剰余キャラクタは過程の後の方の部分においてｉ番目の符号語におけ る誤りを訂正するために使用される。）（ブロック４７０）　処理装置は次にブ ロック４６０に進み、そしてブロック４６０に関連して前に説明された方法で継 続する。それゆえ、表２はブロックにおける「復号不可能な」符号語、及び符号 器シフトレジスタ２２０を通っての各対応符号語の最初の完全なシフト時に計算 されたそれらの剰余のリストを構成している。

今後はブロック５００に続いて、処理装置２１０は表２に記載されたいわゆる「 復号不可能な」符号語を含む、ブロックにおけるすべての符号語を訂正するため に記憶装置２４０に十分な情報を現在記憶している。復号器２１０は次のように 進行する。まず、復号器２１０は表１に記憶された連続した非ゼロ仮想検査キャ ラクタ位置のストリングを見つけて、これを消去位置として復号器２３０に送る 。この発明の誤り捕獲技法により訂正可能であるとして表１に記載されたように 一つを越える符号語がある場合には、あいまいさは単に表１から連続した非ゼロ 仮想検査キャラクタ位置Ｌｉの最長のストリングを選択することによって解決さ れることができる。（ブロック５００）次に、表２に記載された指標ｉ′によっ て標識付けされた符号語のそれぞれに対して、処理装置２１０は対応するシンド ローム及びこれの位置Ｌｓを表２から取り出して、これらを（一度に一つずつ） 復号器２３０に送る。（ブロック５０５）処理装置２１０はシンドロームからｉ ′番目の符号語における対応する誤りパターンＹｅ及びこれら位１ｌＬｅを計算 するように復号器２３０に命令する。（ブロック５０５）　復号器は次に復号器 ２３０によって今計算されたばかりの　Ｙｅ’及びＬｅ’を表３における対応す る符号語指標ビで記憶されるようにする。

（ブロック５１０）　次に処理装置２１０は復号器２３０が表２に記載された「 復号不可能な」符号語（指標ｉ′によって指定されたもの）のすべて処理したか どうかを決定する。（ブロック５１５）　処理していないならば、処理装置２１ ０はブロック５１５のＮｏ分岐をとり、前述の動作を継続し、ブロック５０５の 開始に戻って表２に記載された次の符号語の剰余を取り出し、ついには表２に記 載された符号語のすべてがブロック５０５．５１０，５１５及び５２０のループ により同様に処理されてしまうようにする。そこで、処理装置２１０はブロック ５１５のＹＥＳ分岐をとる。

この点において、処理装置２１０はレジスタ１００の配列に記憶されたブロック におけるすべての符号語に対する誤りパターン及びこれの位置のすべてを計算し ている。処理装置によって行われるべき唯一の残りのタスクはこのように計算さ れた誤りパターンのそれぞれをブロックの符号語における対応する位置へ加える ことである。（表１に記載された）誤り捕獲法により訂正が可能であった。

（少なくとも）一つの符号語に対しては復号器は単に対応する符号語位置に非ゼ ロ仮想検査位置を加えるだけでよいが、残りの符号語に対しては処理装置は対応 する符号語位置に計算された誤りパターンを加えなければならない、これを行う ために、処理装置２１０は、（図３に示されたようにＹ方向に垂直「下方へ」シ フトすることによって）レジスタ１００の配列から一度に一つの符号語を送り出 してこれがレジスタの配列を出るときに対応する符号語位置に訂正を加えるか、 又は別の方法として、直列方式でレジスタの配列から符号語のブロックをシフト して互いにインダリーブされた五つの符号語を残し、これがレジスタｌＯＯの配 列を去るときに一度に１キヤラクタずつ対応する符号語位置に訂正を加えるとい う選択肢を持っている０図５ｂに関連して現在説明されているのはこの後者の選 択肢である。

ブロック５１５のＹＥＳ分岐をとると、処理装置２１０はレジスタ１００の配列 に、データを（前に説明された蛇行方式で）８ビツト排他的ＯＲゲート又はモジ ュラス２加算器３００を通して送り出させる。（ブロック５２５）　加算器３０ ０の一方の入力に現れる各キャラクタに対して、処理装置２１０は符号語指標数 ｉ及びｉ番目の符号語内のそのキャラクタの位置りを決定する。（ブロック５３ ０）処理装置２１０は次に加算器３００のその入力に現在あるキャラクタの符号 語指標ｉが表１に記載されているか否かを決定する。（ブロック５３５）　記載 されているならば、処理装置はブロック５３５のＹＥＳ分岐をとり、そのキャラ クタの位置りが表１に記載されたいずれかのＬｉに対応しているかどうかを決定 する。

（ブロック５４０）　対応しているならば、処理装置２１０は記憶装置２４０の 表１から位置しに対応する仮想検査キャラクタを取り出してこれを加算器３００ の他方の人力に送る。（ブロック５４５）　加算器３００における現在のキャラ クタの位置りが表１に記載されたいずれかのＬｉに対応していないならば、それ はこのキャラクタが正しくて訂正を行わなくてよいことことの表示であり、処理 装置はブロック５４０のＮｏ分岐をとる。処理装置２１０は次に符号語の全ブロ ックにおけるすべての符号語のすべてのキャラクタがレジスタ１００の配列から 送り出されたかどうかを決定する。（ブロック５５０）　送り出されていないな らば、処理装置２１０は過程を続行して（ブロック５５５Ｌブロツク５２５の初 めに戻り、次のキャラクタをレジスタ１００の配列から送り出す、ブロック５３ ５に戻って、処理装置２１０は、加算器３００の入力における現在のキャラクタ の符号語指標数 に記載されていないことを見いだすかもしれない。その場合には、処理装置２１ ０はブロック５３５のＮｏ分岐をとり、加算器３００の入力における現在のキャ ラクタの符号語指標ｉが表３に記載されているかどうかを決定する。（ブロック ５６０）そのように記載されているならば、処理装置２１０はブロック５６０の ＹＥＳ分岐をとり、加算器３００の入力における現在のキャラクタの位置が表３ に記載されたいずれかの誤りパターン位置Ｌｅに対応しているかどうかを決定す る。（ブロック５６５）　処理装置は、加算器３００の入力における現在のキャ ラクタの符号語位置りが表３に記憶されたＬｅに対応していることを決定したな らば、ブロック５６５のＹＥＳ分岐をとり、表３から対応する誤りパターンＹｅ を取り出して、これを加算器３００の他方の入力に送る。

ブロック５６０に戻って、処理装置は、加算器３００の入力における現在のキャ ラクタの符号語指標ｉが表３に記載された符号語のものでないことを決定したな らば、ブロック５６０のＮｏ分岐をとり、ブロック５５０の初めに行く、同様に 、ブロック５６５において、処理装置２１０は、加算器３００の入力における現 在のキャラクタの符号語位置が表３に記憶されたいずれかのＬｅに対応していな いことを決定したならば、ブロック５６５のＮｏ分岐をとり、ブロック５５０の 初めに行く。

前に言及したように、過程全体は５符号語のブロックにおけるすべての符号語の すべてのキャラクタがレジスタ１００の配列から加算器３００を通って送り出さ れてしまうまで続行される。この時点において、処理装置２１０はブロック５５ ０のＹＥＳ分岐をとり、図５ａのブロック４００に復帰しくブロック５７０）、 インタリーブ式５符号語の次のブロックがレジスタ１００の配列ヘロードされる ことを可能にする。

前述の説明において、訂正されたデータはインタリーブ形式で加算器３００を出 る。他方、訂正された形式でのインタリープ解除式データを持つことが望まれる 場合には、図５ｂに図解された前述の過程は制御処理装置２１０内で内部的に行 われて、各符号語が、制御処理装置２１０により図３においてＹ方向に下方ヘシ フトされるときに個別に訂正され、訂正が符号語でこの方式で行われることが可 能であると思われ、そして加算器３００は単に除去されるであろう、そのような 場合にはインタリーブ解除式訂正済みデータが制御処理装置出力２１０ａにおい て出力されるであろう。

この発明はその採択実施例に言及して詳細に説明されたが、この発明の精神及び 範囲から外れることなく種々の変形及び変更が行われ得ることは理解される。

几ＪＦ’Ｉ Ｄ＝プロ７７労りのインクリ−１戎杆号給０叡ｒ＝片号語カクＯ検青Ａヤラクク ｎ数 ドブｐツク内の州別Ｏ蔚力語を相定する（れρ）ｊ−１＝后ＪＩｆ組（合端１俊 トう７１推升Ｆ１女２＃６定Ｊる ＦＩＧ、５ 手続補正書（方式） １．事件の表示 ’　ＰＣＴ／ＵＳ８９１０２５３３ 平成　１年特許願第５０６９２４号 ２、発明の名称 延長形バーストトラッピング ３、補正をする者 事件との関係　特許出願人 住所 名　称　サイクロトミックス・インコーホレーテッド４゜代理人 住　所　東京都千代田区大手町二丁目２番１号新大手町ビル　２０６区 ５、補正命令の日付　平成　３年　８月２７日　（発送日）６、補正の対象 （１）出願人の住所、名称、代表貴名、国籍を正確に記載した国内書面

Claims (10)

【特許請求の範囲】
1. １．各符号語が大きさＮキャラクタの符号におけるｒ検査キャラクタを含む長さ ｎキャラクタのものであるＤインタリーブ式符号語のブロックを受信し且つ記憶 するための記憶装置、 所与の符号語から符号生成多項式を定義するキャラクタの選ばれた集合に関して ｒ剰余キャラクタの集合を計算するための符号器装置、前記の剰余キャラクタの 集合から誤りパターンの集合及び前記の所与の符号語における対応する誤り位置 を生成するために誤り訂正アルゴリズムを実行するように構成された復号器処理 装置、並びにａ．前記の受信ブロックにおける前記のＤ符号語の各一つを個別に 前記の記憶装置から前記の符号器装置を通してシフトして前記の符号器装置が前 記の一つの符号語に対応するｒ剰余キャラクタの集合を生成するようにし、ｂ． 前記の符号器装置を分離して前記の符号器装置にその内容を１キャラクタ位置だ けｎ回もシフトさせてｒ仮想検査キャラクタのｎもの集合を生成させるようにし 、 ｃ．前記の符号器装置の前記のシフトの一つがしきい値数のゼロ値検査キャラク タを超過するゼロ値仮想検査キャラクタの連続的系列を生成したときには、対応 する非ゼロ値仮想検査キャラクタの位置を前記の受信ブロックの他のすべての符 号語における消去位置として前記の復号器処理装置に送るための制御処理装置、 を備えており、これにより前記の復号器が前記の消去位置を用いて対応する剰余 キャラクタから前記のブロックにおける前記の他の符号語を訂正し、且つ前記の 制御処理装置が前記の一つのシフトに対応する前記の仮想検査キャラクタの集合 を前記の一つの符号語における対応する位置に加えることによって前記の一つの 符号語を訂正することができる、 インタリーブ式符号のための誤り訂正処理装置。
2. ２．前記の連続的ゼロ値検査キャラクタのしきい値数及び前記の符号の大きさＮ が、前記のゼロ値仮想検査キャラクタの一つ以上のものが誤り表示である最大確 率に対応するように選ばれ、前記のしきい値数が、前記の確率が許容可能な程度 に低いように選択されている、請求項１の誤り訂正処理装置。
3. ３．前記の符号語及び前記の符号生成多項式がリードーソロモン符号に対応して おり、これによって前記の復号器が、指定された位置を持ったＳ消去及び前記の 他の符号語のそれぞれにおける事前未知位置のｔ誤りをＳ＋２ｔがｒ以下である という条件で訂正することができる、請求項１の誤り訂正処理装置。
4. ４．前記の消去位置が、前記のブロックのすべての符号梧における同じキャラク タ位置に影響を及ぼす連続的誤りバーストに対応している、請求項１の誤り訂正 処理装置。
5. ５．ｒ検査キャラクタを含む長さｎのキャラクタの所与の符号語から符号生成多 項式を定義するキャラクタの選ばれた集合に関してｒ剰余キャラクタの集合を計 算するための符号器装置、及び ａ．前記の符号器装置の内容をｎ回もシフトして仮想検査キャラクタのｒもの集 合を生成するようにし、 ｂ．前記の符号器の前記シフトの一つが、連続的ゼロ値検査キャラクタのしきい 値数Ｂを超過するゼロ値仮想検査キャラクタの系列を生成したときには、前記の 符号器の前記の一つのシフト時に生成された非ゼロ値仮想検査キャラクタを前記 の所与の符号語における対応する位置に加えて前記の符号語を訂正するようにす るための制御処理装置であって、前記の非ゼロ値検査キャラクタのしきい値Ｂが 、前記のゼロ値検査キャラクタの一つ以上のものが誤り表示である確率（Ｎ＋１ ）−（Ｂ−１）に対応しており、且つ前記の確率が許容可能なほど低い残差ビッ ト誤り率に対応している 前記の制御処理装置 を備えている誤り訂正処理装置。
6. ６．Ｎ＝２５５，ｒ＝１６，Ｂ＝４であり且つ前記の確率が２−２４である、請 求項１の誤り訂正処理装置。
7. ７．各符号梧がｒ検査キャラクタを含む長さｎのキャラクタのものであるＤイン タリーブ式符号語のブロックを受信し且つ記憶するための記憶装置、所与の符号 語から符号生成多項式を定義するキャラクタの選ばれた集合に関してｒ剰余キャ ラクタの集合を計算するための符号器装置、前記の剰余キャラクタの集合から誤 りパターンの集合及び前記の所与の符号語における対応する誤り位置を生成する ために誤り訂正アルゴリズムを実行するように構成された復号器処理装置、並び にａ．前記の受信ブロックにおける前記のＤ符号語の各一つを個別に前記の記憶 装置から前記の符号器装置を通してシフトして前記の符号器装置が前記の一つの 符号語に対応するｒ剰余キャラクタの集合を生成するようにし、ｂ．前記の符号 器装置を分離して前記の符号器装置にその内容を１キャラクタだけｎ回もシフト させてｒ仮想検査キャラクタのｎもの集合を生成させるようにし、 ｃ．前記の符号器装置の前記のシフトのどれがゼロ値検査キャラクタのしきい値 を超過するゼロ値仮想検査キャラクタの最長の連続的系列を生成するかを決定し 、且つ対応する非ゼロ値仮想検査キャラクタの位置を前記の受信ブロックにおけ る他のすべての符号語における消去位置として前記の復号器処理装置に送るため の制御処理装置、 を備えており、これにより前記の復号器が前記の消去位置を用いて対応する剰余 キャラクタから前記のブロックにおける前記の他の符号語を訂正し、且つ前記の 制御処理装置が、前記の一つのシフトに対応する前記の仮想検査キャラクタの集 合を前記の一つの符号語における対応する位置に加えることによって前記の一つ の符号語を訂正することができる、 インタリーブ式符号のための誤り訂正処理装置。
8. ８．連続的ゼロ値検査キャラクタの前記のしきい値及び前記の符号の大きさＮｎ が、前記のゼロ値仮想検査キャラクタの一つ以上のものが誤り表示である最大確 率に対応するように選ばれており、前記のしきい値数が、前記の確率が許容可能 な程度に低いように選択されている、請求項７の誤り訂正処理装置。
9. ９．前記の符号誤及び前記の符号生成多項式がリードーソロモン符号に対応して おり、これによって前記の復号器が、指定された位置を持ったＳ消去及び前記の 他の符号語のそれぞれにおける事前未知位置のｔ誤りを、Ｓ＋２ｔがｒ以下であ るという条件で訂正することができる、請求項７の誤り訂正処理装置。
10. １０．前記の消去位置が、前記のブロックのすべての符号語における同じキャラ クタ位置に影響を及ぼす連続的誤りバーストに対応している、請求項７の誤り訂 正処理装置。