JPH05244020A - インターリーブ式の誤り訂正符号を復号化するための復号器能力強化方法 - Google Patents
インターリーブ式の誤り訂正符号を復号化するための復号器能力強化方法Info
- Publication number
- JPH05244020A JPH05244020A JP4270145A JP27014592A JPH05244020A JP H05244020 A JPH05244020 A JP H05244020A JP 4270145 A JP4270145 A JP 4270145A JP 27014592 A JP27014592 A JP 27014592A JP H05244020 A JPH05244020 A JP H05244020A
- Authority
- JP
- Japan
- Prior art keywords
- codeword
- error
- block
- code
- codewords
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/27—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques
- H03M13/2703—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques the interleaver involving at least two directions
- H03M13/2728—Helical type interleaver
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
- G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
- G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/27—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques
- H03M13/2703—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques the interleaver involving at least two directions
- H03M13/2721—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques the interleaver involving at least two directions the interleaver involves a diagonal direction, e.g. by using an interleaving matrix with read-out in a diagonal direction
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Probability & Statistics with Applications (AREA)
- Mathematical Physics (AREA)
- General Physics & Mathematics (AREA)
- Algebra (AREA)
- Pure & Applied Mathematics (AREA)
- Quality & Reliability (AREA)
- General Engineering & Computer Science (AREA)
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
(57)【要約】 （修正有）
【目的】 インターリーブ式の誤り訂正符号を復号化す
る復号器の、復号化能力を強化する。 【構成】 ｎバイト長の複数のコード化済み符号語を行
方向に配列して深さλの複数の矩形ブロックを形成し
（ｎとλは互いに素）、ブロック毎順番にインターリー
ブして伝送する。インターリーブはブロックの斜め方向
に実行される。受信側では、受信データをデインターリ
ーブし復号するが、誤りバイト数が４以上でＥＣＣ能力
を超えている行１、４の符号語にフラグ付けをし、訂正
可能である行０の誤りバイト２、３に斜め方向に隣接す
る行１のバイト３、４を消滅痕として行１を訂正可能に
し訂正する。また、行３の誤りバイト０、１０に斜め方
向に隣接する行４のバイト１、１１を消滅痕として、同
様に誤り訂正を実行する。
る復号器の、復号化能力を強化する。 【構成】 ｎバイト長の複数のコード化済み符号語を行
方向に配列して深さλの複数の矩形ブロックを形成し
（ｎとλは互いに素）、ブロック毎順番にインターリー
ブして伝送する。インターリーブはブロックの斜め方向
に実行される。受信側では、受信データをデインターリ
ーブし復号するが、誤りバイト数が４以上でＥＣＣ能力
を超えている行１、４の符号語にフラグ付けをし、訂正
可能である行０の誤りバイト２、３に斜め方向に隣接す
る行１のバイト３、４を消滅痕として行１を訂正可能に
し訂正する。また、行３の誤りバイト０、１０に斜め方
向に隣接する行４のバイト１、１１を消滅痕として、同
様に誤り訂正を実行する。
Description
【０００１】
【産業上の利用分野】本発明は符号の誤り訂正に関し、
より詳しくは、ランダム誤りと共にかなり多くのバース
ト誤りを発生する伝送チャネルに対応できるようにし
た、インターリーブ式の誤り訂正符号の符号語を復号化
する復号器の、復号化能力を強化するための方法に関す
る。
より詳しくは、ランダム誤りと共にかなり多くのバース
ト誤りを発生する伝送チャネルに対応できるようにし
た、インターリーブ式の誤り訂正符号の符号語を復号化
する復号器の、復号化能力を強化するための方法に関す
る。
【０００２】
【従来の技術】データ中に、バースト誤りとランダム誤
りの２種類の誤りが混在する場合に、それら２種類の誤
りを訂正できるようにするための最も一般的な方法は、
誤り訂正符号（ＥＣＣ）の符号語を、インターリーブし
た符号語にしておくという方法である。従来のこのイン
ターリーブ式の方法では、先ず、（ブロック１つ分の）
一連の符号語の、各々の第０バイトだけを縦方向に並べ
て符号化して行き、それら符号語の全ての第０バイトの
符号化が完了したならば、続いてそれら符号語の第１バ
イトだけを同じく縦方向に並べて符号化して行き、以下
同様にして、一連の複数の矩形ブロックの各ブロックご
とに、その１つのブロックの中に、ブロック１つ分の一
連の符号語の全てのバイトを書き込むようにしていた。
一方、復号化の際には、ある特定の１つのブロックの中
の全ての符号語を、そのブロックの１本の横列ごとに復
号化し、そして次々と連続して横列１本ずつ復号化して
行くようにしている。このインターリーブを行なうこと
によって、１つのバースト誤りに含まれるｍ個の誤り
が、連続するｍ個の符号語の間に空間的に分散されるよ
うになり、即ち、それらｍ個の誤りの全て、或いは殆ど
全てが、１つの符号語の中に入ってしまうのを避けられ
るようになる。このインターリーブ式の方法は、それが
良好に機能する状況であれば、個々の符号語の誤り訂正
能力を超えてしまうという事態を招くことはない。
りの２種類の誤りが混在する場合に、それら２種類の誤
りを訂正できるようにするための最も一般的な方法は、
誤り訂正符号（ＥＣＣ）の符号語を、インターリーブし
た符号語にしておくという方法である。従来のこのイン
ターリーブ式の方法では、先ず、（ブロック１つ分の）
一連の符号語の、各々の第０バイトだけを縦方向に並べ
て符号化して行き、それら符号語の全ての第０バイトの
符号化が完了したならば、続いてそれら符号語の第１バ
イトだけを同じく縦方向に並べて符号化して行き、以下
同様にして、一連の複数の矩形ブロックの各ブロックご
とに、その１つのブロックの中に、ブロック１つ分の一
連の符号語の全てのバイトを書き込むようにしていた。
一方、復号化の際には、ある特定の１つのブロックの中
の全ての符号語を、そのブロックの１本の横列ごとに復
号化し、そして次々と連続して横列１本ずつ復号化して
行くようにしている。このインターリーブを行なうこと
によって、１つのバースト誤りに含まれるｍ個の誤り
が、連続するｍ個の符号語の間に空間的に分散されるよ
うになり、即ち、それらｍ個の誤りの全て、或いは殆ど
全てが、１つの符号語の中に入ってしまうのを避けられ
るようになる。このインターリーブ式の方法は、それが
良好に機能する状況であれば、個々の符号語の誤り訂正
能力を超えてしまうという事態を招くことはない。
【０００３】インターリーブ式の様々な方法を記載した
文献としては、クラークら（Clarket al.）による「デ
ィジタル通信のための誤り訂正符号 (Error-correction
Coding for Digital Communications）」 1981,Plenu
m Press発行 等がある。広く一般的に採用されている
ＥＣＣの１つに、リード−ソロモン符号（ＲＳ符号）と
呼ばれているものがある。ＲＳ符号は、有限体（ガロア
体）上のバイト訂正符号であり、その有限体はＧＦ
（ｑ）で表わされ、ここでｑは素数のベキを表わしてい
る。このｑの値として一般的に用いられているのは「２
8 」という値である。また、あるリード−ソロモン符号
が、［ｎ，ｋ］ＲＳ符号というように書き表わされてい
るならば、それは、符号語の長さをｎバイト（ただしｎ
≦ｑ−１）とし、そのうちの情報バイトの個数をｋバイ
トとしたＲＳ符号である。この場合、冗長バイトの個数
（バイト数）ｒは、ｒ＝ｎ−ｋとなり、また、符号の最
小距離ｄは、ｄ＝（ｎ−ｋ）＋１となる。［ｎ，ｋ］Ｒ
Ｓ符号を用いて「誤り」と「消滅痕 (erasure)」とを訂
正する場合に、２ｓ＋ｔ≦（ｎ−ｋ）を満足するＳ個の
誤り及びｔ個の消滅痕を訂正することができる。「消滅
痕」とは、誤りの一種であって、その発生位置が既知の
（ただし、その正しい信号値は未知の）ものである。
尚、ここでは、単に「誤り」という場合には、それは、
「消滅痕」ではない、通常の誤りのことを意味するもの
とする。１個の誤りは略々２個の消滅痕に相当するた
め、誤りのうちのあるものを消滅痕として取扱うことに
よって、冗長度を増大させることなく復号器の能力を強
化することが可能となる。
文献としては、クラークら（Clarket al.）による「デ
ィジタル通信のための誤り訂正符号 (Error-correction
Coding for Digital Communications）」 1981,Plenu
m Press発行 等がある。広く一般的に採用されている
ＥＣＣの１つに、リード−ソロモン符号（ＲＳ符号）と
呼ばれているものがある。ＲＳ符号は、有限体（ガロア
体）上のバイト訂正符号であり、その有限体はＧＦ
（ｑ）で表わされ、ここでｑは素数のベキを表わしてい
る。このｑの値として一般的に用いられているのは「２
8 」という値である。また、あるリード−ソロモン符号
が、［ｎ，ｋ］ＲＳ符号というように書き表わされてい
るならば、それは、符号語の長さをｎバイト（ただしｎ
≦ｑ−１）とし、そのうちの情報バイトの個数をｋバイ
トとしたＲＳ符号である。この場合、冗長バイトの個数
（バイト数）ｒは、ｒ＝ｎ−ｋとなり、また、符号の最
小距離ｄは、ｄ＝（ｎ−ｋ）＋１となる。［ｎ，ｋ］Ｒ
Ｓ符号を用いて「誤り」と「消滅痕 (erasure)」とを訂
正する場合に、２ｓ＋ｔ≦（ｎ−ｋ）を満足するＳ個の
誤り及びｔ個の消滅痕を訂正することができる。「消滅
痕」とは、誤りの一種であって、その発生位置が既知の
（ただし、その正しい信号値は未知の）ものである。
尚、ここでは、単に「誤り」という場合には、それは、
「消滅痕」ではない、通常の誤りのことを意味するもの
とする。１個の誤りは略々２個の消滅痕に相当するた
め、誤りのうちのあるものを消滅痕として取扱うことに
よって、冗長度を増大させることなく復号器の能力を強
化することが可能となる。
【０００４】米国特許第４５５９６２５号は、誤りを消
滅痕として取扱うことによって符号器の能力を強化しよ
うとする予測式の方法を記載した従来例の文献として
は、出願人の知る限りで唯一の文献である。この米国特
許の方法は、以下の特性を有している。 （１）符号語の長さ（ｎ）を、通常採用されている１２
８バイトの長さにした場合、この方法では、１２７×
（ｎ−１）個の符号語（余りにも大きな個数である）を
インターリーブしなければ、完全な螺旋対称性が得られ
ない。そして完全な螺旋対称性が得られない場合には、
このバースト予測式の方法では、更に複雑度が上昇して
しまう。 （２）ある符号語が訂正可能な誤りを含んでいたなら
ば、その符号語に隣接した符号語の中の、その訂正可能
な誤りに隣接したロケーション（隣接ロケーション）に
フラグで標識付けをし、そして、隣接した符号語の中の
誤りを、隣接ロケーションに位置する消滅痕であるもの
と、自動的に予測するようにしている。 （３）一連の符号語を符号化する際には、それら符号語
が、１列ごとに斜めにずれたブロックの中に並ぶように
している。即ち、１つの符号語を１本の横列とし、連続
する符号語が縦方向に並ぶようにするが、その際に、連
続する２つの符号語の間では、それら符号語の中の対応
するバイトどうしが横方向にずれるようにしている。
滅痕として取扱うことによって符号器の能力を強化しよ
うとする予測式の方法を記載した従来例の文献として
は、出願人の知る限りで唯一の文献である。この米国特
許の方法は、以下の特性を有している。 （１）符号語の長さ（ｎ）を、通常採用されている１２
８バイトの長さにした場合、この方法では、１２７×
（ｎ−１）個の符号語（余りにも大きな個数である）を
インターリーブしなければ、完全な螺旋対称性が得られ
ない。そして完全な螺旋対称性が得られない場合には、
このバースト予測式の方法では、更に複雑度が上昇して
しまう。 （２）ある符号語が訂正可能な誤りを含んでいたなら
ば、その符号語に隣接した符号語の中の、その訂正可能
な誤りに隣接したロケーション（隣接ロケーション）に
フラグで標識付けをし、そして、隣接した符号語の中の
誤りを、隣接ロケーションに位置する消滅痕であるもの
と、自動的に予測するようにしている。 （３）一連の符号語を符号化する際には、それら符号語
が、１列ごとに斜めにずれたブロックの中に並ぶように
している。即ち、１つの符号語を１本の横列とし、連続
する符号語が縦方向に並ぶようにするが、その際に、連
続する２つの符号語の間では、それら符号語の中の対応
するバイトどうしが横方向にずれるようにしている。
【０００５】図１には、米国特許第４５５９６２５号に
記載されている螺旋インターリーブ式のデータ書込みシ
ーケンスが、単純化して示されている。この図１に示し
た書込みシーケンスでは、符号化の際に、バイトを垂直
方向に次々と書き込んで行くようにしており、その書き
込んで行く順序をバイト番号で表わすと、図示の如く、
０’、７、１０、１’、４’、１１、２’、５’、
８’、３’、６’、９’、０”、７’、１０’、１”、
４”、１１’という順序である。従ってこれらバイト
は、符号化された状態では、図１のブロックｍ−１、ブ
ロックｍ、及びブロックｍ＋１のように、斜めにずれた
形のブロックの中に並んでいる。ブロックｍを構成して
いる複数の符号語はその各々の長さがｎバイトであり、
またインターリーブ深さがｉである。ただし、符号語
「０’〜３’」と、符号語「４’〜７’」と、符号語
「８’〜１１’」とは、上下に並んだものどうしが互い
に横方向にずれており、全体として斜めにずれた形とな
っている。このブロックｍの、バイト０’〜バイト１
１’が復号化されるときには、復号化横列Ａ、復号化横
列Ｂ、復号化横列Ｃの順で、各々の横列ごとに次々と復
号化されて行く。それら全てが復号化されならば、続い
て、ブロックｍ＋１のバイト０”〜バイト１１”（これ
らのバイトは、図にはそのうちの一部しか示していな
い）が同じように次々と復号化されて行き、以下、同様
にしてその他のブロックも復号化されて行く。この復号
化の処理は、もし誤りが全く検出されなければ、いかな
る遅延も生じることなく進められて行く。
記載されている螺旋インターリーブ式のデータ書込みシ
ーケンスが、単純化して示されている。この図１に示し
た書込みシーケンスでは、符号化の際に、バイトを垂直
方向に次々と書き込んで行くようにしており、その書き
込んで行く順序をバイト番号で表わすと、図示の如く、
０’、７、１０、１’、４’、１１、２’、５’、
８’、３’、６’、９’、０”、７’、１０’、１”、
４”、１１’という順序である。従ってこれらバイト
は、符号化された状態では、図１のブロックｍ−１、ブ
ロックｍ、及びブロックｍ＋１のように、斜めにずれた
形のブロックの中に並んでいる。ブロックｍを構成して
いる複数の符号語はその各々の長さがｎバイトであり、
またインターリーブ深さがｉである。ただし、符号語
「０’〜３’」と、符号語「４’〜７’」と、符号語
「８’〜１１’」とは、上下に並んだものどうしが互い
に横方向にずれており、全体として斜めにずれた形とな
っている。このブロックｍの、バイト０’〜バイト１
１’が復号化されるときには、復号化横列Ａ、復号化横
列Ｂ、復号化横列Ｃの順で、各々の横列ごとに次々と復
号化されて行く。それら全てが復号化されならば、続い
て、ブロックｍ＋１のバイト０”〜バイト１１”（これ
らのバイトは、図にはそのうちの一部しか示していな
い）が同じように次々と復号化されて行き、以下、同様
にしてその他のブロックも復号化されて行く。この復号
化の処理は、もし誤りが全く検出されなければ、いかな
る遅延も生じることなく進められて行く。
【０００６】ここで、バイト２’（即ち、符号語Ａ（符
号語「０’〜３’」）の第３番目のバイト）に誤りが検
出されたものとする。このバイト２’に対して垂直方向
に隣接する位置にある、符号語Ｂのバイト５’には、符
号語ＡにＥＣＣが適用されてその誤りの訂正が行なわれ
た後に、フラグによって自動的に、消滅痕であることを
示す標識付けがなされる。続いてこの符号語Ｂに対して
ＥＣＣが適用される。この符号語Ｂの誤り訂正が成功し
たならば、そのバイト５’が、実際に誤りを発生してい
たか否かを調べる。もしバイト５’が実際には誤りを発
生していなかったのであれば、そのフラグを、このバイ
ト位置から除去する。一方、バイト５’が実際に誤りを
発生していたのであれば、符号語Ｃにフラグで標識付け
することによって、そのバイト８’（符号語Ｃの先頭の
バイト）が消滅痕であることを自動的に予測し、且つそ
れを宣言する。以上と同じプロセスを、後続のブロック
ｍ＋１を復号化する際にも反復して実行する。要するに
この米国特許においては、ある１つの符号語の中に誤り
が発生したならば、その符号語の中の誤りの位置に対し
て垂直方向に隣接した、次の符号語の中の対応する位置
が、消滅痕であるものと自動的に予測するようにしてい
るのである。
号語「０’〜３’」）の第３番目のバイト）に誤りが検
出されたものとする。このバイト２’に対して垂直方向
に隣接する位置にある、符号語Ｂのバイト５’には、符
号語ＡにＥＣＣが適用されてその誤りの訂正が行なわれ
た後に、フラグによって自動的に、消滅痕であることを
示す標識付けがなされる。続いてこの符号語Ｂに対して
ＥＣＣが適用される。この符号語Ｂの誤り訂正が成功し
たならば、そのバイト５’が、実際に誤りを発生してい
たか否かを調べる。もしバイト５’が実際には誤りを発
生していなかったのであれば、そのフラグを、このバイ
ト位置から除去する。一方、バイト５’が実際に誤りを
発生していたのであれば、符号語Ｃにフラグで標識付け
することによって、そのバイト８’（符号語Ｃの先頭の
バイト）が消滅痕であることを自動的に予測し、且つそ
れを宣言する。以上と同じプロセスを、後続のブロック
ｍ＋１を復号化する際にも反復して実行する。要するに
この米国特許においては、ある１つの符号語の中に誤り
が発生したならば、その符号語の中の誤りの位置に対し
て垂直方向に隣接した、次の符号語の中の対応する位置
が、消滅痕であるものと自動的に予測するようにしてい
るのである。
【０００７】
【発明が解決しようとする課題】しかしながらこの従来
例の方法では、実際には符号語が訂正可能であったにも
かかわらず、自動的にフラグ標識付けがなされて消滅痕
であると推定されてしまい、この方法を採用したばかり
に、ＥＣＣの能力を超えてしまうという不都合が発生す
るおそれがあった。
例の方法では、実際には符号語が訂正可能であったにも
かかわらず、自動的にフラグ標識付けがなされて消滅痕
であると推定されてしまい、この方法を採用したばかり
に、ＥＣＣの能力を超えてしまうという不都合が発生す
るおそれがあった。
【０００８】更にこの米国特許の方法では、螺旋対称性
を得るためにはｉ＝ｎ−１としておく必要があり、即
ち、インターリーブ深さｉが、１つの符号語の中に含ま
れるバイト数ｎよりも丁度１つだけ少ない値としておく
必要がある。これが必要とされるのは、この米国特許の
式の方法を用いたときに、最後の横列（図１の例では横
列Ｃ）だけを特別の処理方式で処理せずとも良いように
したいからである。例えば、もしｉ＜（ｎ−１）であっ
たならば、螺旋の規則性が壊れてしまうことになる。即
ち、図１において、もし仮に、インターリーブする横列
を、ＡとＢとの２列だけとしたならば、Ａ、Ｂ、Ｃの３
列としていたときには螺旋対称性を壊すことなく１０か
ら１’へ回れたのに対して、７から１’へ回る際に、ど
うしても螺旋対称性が壊れてしまう。従って、以上に説
明した従来例と比較して、更に復号化の能力を強化した
ＥＣＣの符号語を復号化するための復合器能力強化方法
が求められており、本発明の目的は、このような強化方
法を提供することである。
を得るためにはｉ＝ｎ−１としておく必要があり、即
ち、インターリーブ深さｉが、１つの符号語の中に含ま
れるバイト数ｎよりも丁度１つだけ少ない値としておく
必要がある。これが必要とされるのは、この米国特許の
式の方法を用いたときに、最後の横列（図１の例では横
列Ｃ）だけを特別の処理方式で処理せずとも良いように
したいからである。例えば、もしｉ＜（ｎ−１）であっ
たならば、螺旋の規則性が壊れてしまうことになる。即
ち、図１において、もし仮に、インターリーブする横列
を、ＡとＢとの２列だけとしたならば、Ａ、Ｂ、Ｃの３
列としていたときには螺旋対称性を壊すことなく１０か
ら１’へ回れたのに対して、７から１’へ回る際に、ど
うしても螺旋対称性が壊れてしまう。従って、以上に説
明した従来例と比較して、更に復号化の能力を強化した
ＥＣＣの符号語を復号化するための復合器能力強化方法
が求められており、本発明の目的は、このような強化方
法を提供することである。
【０００９】
【課題を解決するための手段】この目的を達成するため
に、本発明では、復号化能力を次のようにして強化して
いる。先ず、ＥＣＣの能力を超えた符号語に対しての
みフラグで標識付けをするようにしている。また、ｎ
とλとが互いに素であるということのみを条件として、
符号語を任意のバイト長さ（ｎ）及び任意の符号語深さ
（λ）のものとすることができるようにしている。そし
て、連続する複数の符号語のコード化済バイトを、斜
め方向の単一の連続したシーケンスを成すようにインタ
ーリーブして、位相幾何学的に円環体を成すアレイを形
成するようにし、それによって全てのバースト誤りが、
そのアレイの中におけるそれらバースト誤りの発生位置
の如何にかかわらず、１つの符号語から次の符号語へと
連続するようにしている。以上の諸特性によって、λ本
以下の横列にしか影響を及ぼさないバースト誤りに付随
する問題が確実に回避されており、これが可能であるの
は、以上のようにすることによって「最後の横列」も、
また「先頭の横列」も存在しなくなるからである。
に、本発明では、復号化能力を次のようにして強化して
いる。先ず、ＥＣＣの能力を超えた符号語に対しての
みフラグで標識付けをするようにしている。また、ｎ
とλとが互いに素であるということのみを条件として、
符号語を任意のバイト長さ（ｎ）及び任意の符号語深さ
（λ）のものとすることができるようにしている。そし
て、連続する複数の符号語のコード化済バイトを、斜
め方向の単一の連続したシーケンスを成すようにインタ
ーリーブして、位相幾何学的に円環体を成すアレイを形
成するようにし、それによって全てのバースト誤りが、
そのアレイの中におけるそれらバースト誤りの発生位置
の如何にかかわらず、１つの符号語から次の符号語へと
連続するようにしている。以上の諸特性によって、λ本
以下の横列にしか影響を及ぼさないバースト誤りに付随
する問題が確実に回避されており、これが可能であるの
は、以上のようにすることによって「最後の横列」も、
また「先頭の横列」も存在しなくなるからである。
【００１０】
【実施例】これより、図２以下の図面を参照しつつ、本
発明の好適実施例について説明して行く。図２は、本発
明の実施例に係る装置１０を示したものであり、この装
置１０はランダム誤りと共にかなり多くのバースト誤り
を発生する通信チャネル上を伝送されるディジタル・デ
ータを、符号化及び復号化するための装置である。図示
の如く、装置１０は符号器１２を含んでおり、この符号
器１２は、ディジタル・データ入力を、符号語の構成要
素であるシンボルのストリームへと変換するものであ
る。符号語の１つ１つは、その長さをｎバイトに定めて
ある。コード化済の符号語のシンボルに対しては、イン
ターリーバー１４によって、順序の並べ換えが行なわ
れ、この並べ換えの方式については後に重点的に詳述す
る。変調器１６は、信号をチャネル１８上で伝送できる
形にするものであり、これを、インターリーブされた符
号語をラン・レングス・リミテッド符号（例えば（１，
７）符号）へ変換することによって行なっている。
発明の好適実施例について説明して行く。図２は、本発
明の実施例に係る装置１０を示したものであり、この装
置１０はランダム誤りと共にかなり多くのバースト誤り
を発生する通信チャネル上を伝送されるディジタル・デ
ータを、符号化及び復号化するための装置である。図示
の如く、装置１０は符号器１２を含んでおり、この符号
器１２は、ディジタル・データ入力を、符号語の構成要
素であるシンボルのストリームへと変換するものであ
る。符号語の１つ１つは、その長さをｎバイトに定めて
ある。コード化済の符号語のシンボルに対しては、イン
ターリーバー１４によって、順序の並べ換えが行なわ
れ、この並べ換えの方式については後に重点的に詳述す
る。変調器１６は、信号をチャネル１８上で伝送できる
形にするものであり、これを、インターリーブされた符
号語をラン・レングス・リミテッド符号（例えば（１，
７）符号）へ変換することによって行なっている。
【００１１】復調器２０は、チャネル上を伝送されてき
た信号を処理してディジタル・データの形にし、そこか
らシンボルのストリームを復元し（こうして復元された
シンボルのストリームは、チャネル上のノイズ等のため
に劣化している）、そして、その復元した、即ち復調し
たシンボルのストリームを、デインターリーバー２２へ
向けて出力する。デインターリーバー２２は、インター
リーブされている、そのシンボルのストリームに対し
て、インターリーバー１４が行なった操作とは逆の操作
を施すことによって、そのストリームの中のシンボルの
並び順を、元の順序に戻す。こうして得られた符号語
は、強化されたＲＳ復号器２４へ転送され、この復号器
２４は、従来のＲＳ復号器では不可能な程に困難な、オ
リジナル・データの評価値の出力作業を、冗長度を増大
させることなしに、ＥＣＣ符号の誤り訂正能力を拡張す
ることによって可能にしたものである。
た信号を処理してディジタル・データの形にし、そこか
らシンボルのストリームを復元し（こうして復元された
シンボルのストリームは、チャネル上のノイズ等のため
に劣化している）、そして、その復元した、即ち復調し
たシンボルのストリームを、デインターリーバー２２へ
向けて出力する。デインターリーバー２２は、インター
リーブされている、そのシンボルのストリームに対し
て、インターリーバー１４が行なった操作とは逆の操作
を施すことによって、そのストリームの中のシンボルの
並び順を、元の順序に戻す。こうして得られた符号語
は、強化されたＲＳ復号器２４へ転送され、この復号器
２４は、従来のＲＳ復号器では不可能な程に困難な、オ
リジナル・データの評価値の出力作業を、冗長度を増大
させることなしに、ＥＣＣ符号の誤り訂正能力を拡張す
ることによって可能にしたものである。
【００１２】尚、本明細書の発明の詳細な説明並びに請
求の範囲において使用している「シンボル」という用語
は、バイト、ハーフワード、ワード、或いはその他の任
意の種類の、所定個数のビットの集まりを、広く包括す
る用語である。ただし、理解を容易にするために、これ
までの説明では、シンボルがバイトである場合について
述べており、また、これ以降の説明でも、シンボルがバ
イトである場合について述べることにする。更に、以下
の説明の中で使用する「《ｍ》n」という表記は、ｎを
法としてｍと合同な整数ｉであって（ｍ≡ｉ（モジュー
ロｎ））、０≦ｉ≦ｎ−１である整数ｉを表わすもので
ある。
求の範囲において使用している「シンボル」という用語
は、バイト、ハーフワード、ワード、或いはその他の任
意の種類の、所定個数のビットの集まりを、広く包括す
る用語である。ただし、理解を容易にするために、これ
までの説明では、シンボルがバイトである場合について
述べており、また、これ以降の説明でも、シンボルがバ
イトである場合について述べることにする。更に、以下
の説明の中で使用する「《ｍ》n」という表記は、ｎを
法としてｍと合同な整数ｉであって（ｍ≡ｉ（モジュー
ロｎ））、０≦ｉ≦ｎ−１である整数ｉを表わすもので
ある。
【００１３】本発明を実施する上での最初のステップ
は、ｎとλとが互いに素でなければならないということ
のみを条件として、長さがｎバイトのコード化済の符号
語を、インターリーブ深さλでインターリーブすること
ができるようなＥＣＣ符号を選択することである。例え
ば、ｎ＝１２８、λ＝９とすれば、「１２８」と「９」
とはいずれもそれ自体は素数でないが、ｎとλとは、互
いに素である。従って、容易に理解されるように、λ＝
３、５、７、１１、等々のように、λの値それ自体を素
数にした上、ｎをそのλでは割り切れない数とすれば、
上記の条件は簡単に満足することができる。
は、ｎとλとが互いに素でなければならないということ
のみを条件として、長さがｎバイトのコード化済の符号
語を、インターリーブ深さλでインターリーブすること
ができるようなＥＣＣ符号を選択することである。例え
ば、ｎ＝１２８、λ＝９とすれば、「１２８」と「９」
とはいずれもそれ自体は素数でないが、ｎとλとは、互
いに素である。従って、容易に理解されるように、λ＝
３、５、７、１１、等々のように、λの値それ自体を素
数にした上、ｎをそのλでは割り切れない数とすれば、
上記の条件は簡単に満足することができる。
【００１４】このＥＣＣは、複数の矩形ブロック（例え
ば、ブロックｍ−１、ブロックｍ、ブロックｍ＋１）の
形に構成されるものである。それらブロックの単純化し
た具体例を示すならば、例えば図３に示したようなブロ
ックであり、同図において各ブロックは複数の符号語か
ら成り、それら符号語は、その各々の長さｎを４バイト
としてあり、またブロックの深さλを符号語３列分の深
さとしてある。各々のブロックは、ａ（ｉ、０）、ａ
（ｉ、１）、... 、ａ（ｉ、ｎ−１）で表わされる横列
から成り、ここで、０≦ｉ≦λ−１である。本発明によ
れば、インターリーバー１４は、１つ１つのブロックご
とに、そのブロックの中のλ本の横列を、（λ＋ｎ−
１）本の斜線へと並べ換え、即ち変換するものであり、
これを次の規則に従って行なうようにしている。ａ
（０、０）の書込みを行なう。ａ（ｉ、ｊ）の書込みを
行なったならば、続いてａ（《ｉ＋１》λ、《ｊ＋１》
n）の書込みを行ない、ただし、０≦ｉ≦λ−１、０≦
ｊ≦ｎ−１ ａ（λ−１、ｎ−１）の書込みを行なったならば、終了
する。ｎとλとは互いに素であるため、本発明の方法に
よれば、ブロックの中の全てのバイトの書込みを必ず完
了することができる。
ば、ブロックｍ−１、ブロックｍ、ブロックｍ＋１）の
形に構成されるものである。それらブロックの単純化し
た具体例を示すならば、例えば図３に示したようなブロ
ックであり、同図において各ブロックは複数の符号語か
ら成り、それら符号語は、その各々の長さｎを４バイト
としてあり、またブロックの深さλを符号語３列分の深
さとしてある。各々のブロックは、ａ（ｉ、０）、ａ
（ｉ、１）、... 、ａ（ｉ、ｎ−１）で表わされる横列
から成り、ここで、０≦ｉ≦λ−１である。本発明によ
れば、インターリーバー１４は、１つ１つのブロックご
とに、そのブロックの中のλ本の横列を、（λ＋ｎ−
１）本の斜線へと並べ換え、即ち変換するものであり、
これを次の規則に従って行なうようにしている。ａ
（０、０）の書込みを行なう。ａ（ｉ、ｊ）の書込みを
行なったならば、続いてａ（《ｉ＋１》λ、《ｊ＋１》
n）の書込みを行ない、ただし、０≦ｉ≦λ−１、０≦
ｊ≦ｎ−１ ａ（λ−１、ｎ−１）の書込みを行なったならば、終了
する。ｎとλとは互いに素であるため、本発明の方法に
よれば、ブロックの中の全てのバイトの書込みを必ず完
了することができる。
【００１５】上記規則によって規定されたこの斜め方向
インターリーブ法を実行することにより形成されるアレ
イ・パターンは、位相幾何学的に円環体（ドーナツ形）
を成すものであり、即ち、ドーナツに紐を斜めに巻付け
て行き、その紐がドーナツを何周かした後に、その末端
を先端に結び付けた形に対し、相似の形になる。位相幾
何学的にこのような形となっているため、λ本以下の横
列にしか影響を及ぼさないバースト誤りは連続になる。
ここで連続という意味は、従来のインターリーブ法では
最後の横列において不連続性が存在していたのに対し、
このインターリーブ法では、最初の横列も最後の横列も
存在しないということである。例えば、図３に示したブ
ロックｍ、ブロックｍ＋１、... の中のシンボルは、１
度にブロック１つずつ（即ち、１つのブロックの処理が
完了してから次のブロックに移るようにして）インター
リーブされることによって、それらの順序は、０’、
５’、１０’、３’、４’、９’、２’、７’、８’、
１’、６’、１１’、０”、５”、１０”、... という
ようになる。
インターリーブ法を実行することにより形成されるアレ
イ・パターンは、位相幾何学的に円環体（ドーナツ形）
を成すものであり、即ち、ドーナツに紐を斜めに巻付け
て行き、その紐がドーナツを何周かした後に、その末端
を先端に結び付けた形に対し、相似の形になる。位相幾
何学的にこのような形となっているため、λ本以下の横
列にしか影響を及ぼさないバースト誤りは連続になる。
ここで連続という意味は、従来のインターリーブ法では
最後の横列において不連続性が存在していたのに対し、
このインターリーブ法では、最初の横列も最後の横列も
存在しないということである。例えば、図３に示したブ
ロックｍ、ブロックｍ＋１、... の中のシンボルは、１
度にブロック１つずつ（即ち、１つのブロックの処理が
完了してから次のブロックに移るようにして）インター
リーブされることによって、それらの順序は、０’、
５’、１０’、３’、４’、９’、２’、７’、８’、
１’、６’、１１’、０”、５”、１０”、... という
ようになる。
【００１６】こうしてインターリーブされた複数の符号
語は、チャネル１８上を伝送された後に、デインターリ
ーブされて、インターリーブされる前の順序に戻され
る。これは、それら符号語がコード化された直後の状態
に戻されるということである。この後、それら符号語の
復号化を行なう。この復号化はブロックごとに行ない、
即ち、１つのブロックの復号化が完了したら次のブロッ
クへ移るというようにして、しかも各ブロックの中で
は、各々の横列ごとに次々と連続して行なうようにして
いる。具体的には、例えば先ず、ブロックｍについて、
その中のバイト０’〜バイト１１’を各横列ごとに次々
と連続して復号化して行き、それら全ての復号化が完了
したならば、続いて、ブロックｍ＋１について、その中
のバイト０”〜バイト１１”を同様に復号化して行き、
以下同様に処理して行く。この復号化の処理は、訂正不
可能な誤りが検出されない限り、いかなる遅延も生じる
ことなく進められて行く。
語は、チャネル１８上を伝送された後に、デインターリ
ーブされて、インターリーブされる前の順序に戻され
る。これは、それら符号語がコード化された直後の状態
に戻されるということである。この後、それら符号語の
復号化を行なう。この復号化はブロックごとに行ない、
即ち、１つのブロックの復号化が完了したら次のブロッ
クへ移るというようにして、しかも各ブロックの中で
は、各々の横列ごとに次々と連続して行なうようにして
いる。具体的には、例えば先ず、ブロックｍについて、
その中のバイト０’〜バイト１１’を各横列ごとに次々
と連続して復号化して行き、それら全ての復号化が完了
したならば、続いて、ブロックｍ＋１について、その中
のバイト０”〜バイト１１”を同様に復号化して行き、
以下同様に処理して行く。この復号化の処理は、訂正不
可能な誤りが検出されない限り、いかなる遅延も生じる
ことなく進められて行く。
【００１７】本発明によれば、後に更に詳細に説明する
ように、冗長性を更に増大させることなくＲＳ復号器２
４の復号化能力を強化することができ、この復号化能力
の強化は、以下にようにすることによって達成されてい
る。 （１）各ブロックの中の、以上に説明したインターリー
ブ処理を施したＥＣＣ符号の全ての符号語（横列）を、
次々と連続して復号化して行くようにする。 （２）ある１つのブロックにおいて、その中の全ての符
号語の復号化が完了し、かつそれら符号語に関する、Ｅ
ＣＣ符号の誤り訂正能力の及ぶ限りの誤り訂正とが完了
したならば、そのブロックの中の、ＥＣＣ符号の誤り訂
正能力を超えてしまったために訂正できずに残っている
符号語（即ち、誤りを含んだままの符号語）の全てに、
フラグで標識付けをする。 （３）フラグで標識付けした符号語の各々について、そ
の符号語に隣接している符号語（即ち、その符号語に先
行する符号語ないし後続の符号語）のうちの、少なくと
も一方の符号語（以下、「隣接符号語」という）を調べ
て、その「隣接符号語」の中に誤りが存在していたか否
か（即ち、その「隣接符号語」が、復号化の際に誤りが
発見されたためにその誤りの訂正が行なわれた複合語で
あるか否か）を判別する。もしそこに誤りが存在し、従
ってその「隣接符号語」が、誤り訂正が行なわれたもの
であったならば、その誤り訂正が行なわれた「隣接符号
語」の中の、誤りが生じていた全てのロケーションを特
定する。 （４）そのフラグで標識付けした符号語の中のロケーシ
ョンのうち、「隣接符号語」の中の誤りが生じていたロ
ケーションに対して、斜め方向に隣接している（この
「斜め方向に隣接している」というのは、上掲の規則の
順番において連続しているという意味である）ロケーシ
ョンに対して、そのロケーションが消滅痕であるとする
宣言を暫定的に行なう。これによって、そのフラグで標
識付けした符号語の中の誤りの全てが（或いは、全てで
なければそのうちの一部が）消滅痕であると暫定的に宣
言される。 （５）そのフラグで標識付けした符号語の復号化を試み
る。 （６）その復号化に成功したならば、同じくフラグで標
識付けしておいたその他の符号語に対して、上記ステッ
プ（３）、（４）、（５）を、反復して実行する。一
方、復号化に成功しなかったならば、その符号語が訂正
不可能な符号語であることを宣言し、復号化の再試行或
いは終了等の、所定のプロトコルを起動する。
ように、冗長性を更に増大させることなくＲＳ復号器２
４の復号化能力を強化することができ、この復号化能力
の強化は、以下にようにすることによって達成されてい
る。 （１）各ブロックの中の、以上に説明したインターリー
ブ処理を施したＥＣＣ符号の全ての符号語（横列）を、
次々と連続して復号化して行くようにする。 （２）ある１つのブロックにおいて、その中の全ての符
号語の復号化が完了し、かつそれら符号語に関する、Ｅ
ＣＣ符号の誤り訂正能力の及ぶ限りの誤り訂正とが完了
したならば、そのブロックの中の、ＥＣＣ符号の誤り訂
正能力を超えてしまったために訂正できずに残っている
符号語（即ち、誤りを含んだままの符号語）の全てに、
フラグで標識付けをする。 （３）フラグで標識付けした符号語の各々について、そ
の符号語に隣接している符号語（即ち、その符号語に先
行する符号語ないし後続の符号語）のうちの、少なくと
も一方の符号語（以下、「隣接符号語」という）を調べ
て、その「隣接符号語」の中に誤りが存在していたか否
か（即ち、その「隣接符号語」が、復号化の際に誤りが
発見されたためにその誤りの訂正が行なわれた複合語で
あるか否か）を判別する。もしそこに誤りが存在し、従
ってその「隣接符号語」が、誤り訂正が行なわれたもの
であったならば、その誤り訂正が行なわれた「隣接符号
語」の中の、誤りが生じていた全てのロケーションを特
定する。 （４）そのフラグで標識付けした符号語の中のロケーシ
ョンのうち、「隣接符号語」の中の誤りが生じていたロ
ケーションに対して、斜め方向に隣接している（この
「斜め方向に隣接している」というのは、上掲の規則の
順番において連続しているという意味である）ロケーシ
ョンに対して、そのロケーションが消滅痕であるとする
宣言を暫定的に行なう。これによって、そのフラグで標
識付けした符号語の中の誤りの全てが（或いは、全てで
なければそのうちの一部が）消滅痕であると暫定的に宣
言される。 （５）そのフラグで標識付けした符号語の復号化を試み
る。 （６）その復号化に成功したならば、同じくフラグで標
識付けしておいたその他の符号語に対して、上記ステッ
プ（３）、（４）、（５）を、反復して実行する。一
方、復号化に成功しなかったならば、その符号語が訂正
不可能な符号語であることを宣言し、復号化の再試行或
いは終了等の、所定のプロトコルを起動する。
【００１８】本発明を実施するための、様々な具体的な
方法については、以下に示す具体例と、そのフローチャ
ートとから明らかにする。具体例I この具体例Iでは、使用する［ｎ，ｋ］ＲＳ符号は、そ
の最小距離をｄ＝８とし、３つまでの誤りを訂正でき、
４つまでの誤りを検出できるようにしたＲＳ符号である
ものとする。また、符号語の長さはｎ＝１７であり、イ
ンターリーブ深さはλ＝６であるものとする。更にこの
具体例Iにおいては、図４に示したように、発生した誤
りのパターンは、３つのバースト誤りｂ1、ｂ2、ｂ
3と、３つのランダム誤りＲとを含んでいるパターンで
あったものとする。復号器２４は、図５のフローチャー
トの中の諸々のステップに従い、横列の復号化と、その
横列の中の誤り訂正とを行なって行くが、その際に、最
初から復号化及び誤り訂正を行なえるのは、横列０、横
列２、横列３、及び横列５だけであり、その理由は、こ
れら横列だけは、その各々に含まれている誤りの個数
が、上記のように選定したＲＳ符号の誤り訂正能力を超
えていないからである。一方、残りの横列１と横列４と
には、フラグで標識付けがなされ、なぜならば、これら
２本の横列は、この最初の復号化の段階では、その誤り
の訂正が不可能だからである。続いて復号器２４は、横
列０のバイト２とバイト３とに誤りが発生していたた
め、暫定的にそれら誤りがバースト誤りであったものと
推定し、そして横列１のバイト３とバイト４とが、消滅
痕ｂ1と消滅痕ｂ2とであるものと宣言する。この宣言を
した後の横列１の誤りの状態は、誤り訂正能力の範囲内
にあるため、この段階で、復号器２４は、この横列１の
２つの誤りｂ3及びＲと、２つの消滅痕ｂ1及びｂ2とを
訂正する。同様に、横列３の中の誤りが、バイト０、バ
イト１０、及びバイト１６であったことから、次の横列
４の中のバイト１、バイト１１、及びバイト０は、夫
々、消滅痕ｂ1、ｂ2、及びｂ3であるものと推定され
る。このように推定された後には、復号器２４は、横列
４に関しては１つの誤りＲと３つの消滅痕ｂ1、ｂ2、ｂ
3とを訂正すれば良いことになり、これは可能であるた
め、それらを訂正する。このようにして、冗長性を更に
増大させることなく復号化能力を強化することができる
という、望ましい結果が得られる。
方法については、以下に示す具体例と、そのフローチャ
ートとから明らかにする。具体例I この具体例Iでは、使用する［ｎ，ｋ］ＲＳ符号は、そ
の最小距離をｄ＝８とし、３つまでの誤りを訂正でき、
４つまでの誤りを検出できるようにしたＲＳ符号である
ものとする。また、符号語の長さはｎ＝１７であり、イ
ンターリーブ深さはλ＝６であるものとする。更にこの
具体例Iにおいては、図４に示したように、発生した誤
りのパターンは、３つのバースト誤りｂ1、ｂ2、ｂ
3と、３つのランダム誤りＲとを含んでいるパターンで
あったものとする。復号器２４は、図５のフローチャー
トの中の諸々のステップに従い、横列の復号化と、その
横列の中の誤り訂正とを行なって行くが、その際に、最
初から復号化及び誤り訂正を行なえるのは、横列０、横
列２、横列３、及び横列５だけであり、その理由は、こ
れら横列だけは、その各々に含まれている誤りの個数
が、上記のように選定したＲＳ符号の誤り訂正能力を超
えていないからである。一方、残りの横列１と横列４と
には、フラグで標識付けがなされ、なぜならば、これら
２本の横列は、この最初の復号化の段階では、その誤り
の訂正が不可能だからである。続いて復号器２４は、横
列０のバイト２とバイト３とに誤りが発生していたた
め、暫定的にそれら誤りがバースト誤りであったものと
推定し、そして横列１のバイト３とバイト４とが、消滅
痕ｂ1と消滅痕ｂ2とであるものと宣言する。この宣言を
した後の横列１の誤りの状態は、誤り訂正能力の範囲内
にあるため、この段階で、復号器２４は、この横列１の
２つの誤りｂ3及びＲと、２つの消滅痕ｂ1及びｂ2とを
訂正する。同様に、横列３の中の誤りが、バイト０、バ
イト１０、及びバイト１６であったことから、次の横列
４の中のバイト１、バイト１１、及びバイト０は、夫
々、消滅痕ｂ1、ｂ2、及びｂ3であるものと推定され
る。このように推定された後には、復号器２４は、横列
４に関しては１つの誤りＲと３つの消滅痕ｂ1、ｂ2、ｂ
3とを訂正すれば良いことになり、これは可能であるた
め、それらを訂正する。このようにして、冗長性を更に
増大させることなく復号化能力を強化することができる
という、望ましい結果が得られる。
【００１９】更に詳しく説明すると、この復号化の方法
は、配線して組立てたハードウェアのロジックによって
実現することもできるが、図５のフローチャートに示し
たように、ソフトウェアによっても実現することのでき
るものである。図５のフローチャートのステップ１１０
では、復号器２４が、その入力として、デインターリー
バー２２からλ個の受信語Ｒ（０）、Ｒ（１）、... 、
Ｒ（λ−１）を受け取る。この入力はステップ１１１へ
受け渡され、このステップ１１１では、フラグ集合Ｆを
空集合にセットすると共に、ｌ −カウンタを「０」に
セットする。フラグ集合Ｆは、訂正不可能な受信語のイ
ンデックスを格納するための（即ち、訂正不可能な受信
語にフラグで標識付けするための）集合であり、一方、
ｌ −カウンタは、処理中の受信語の番号を保持してお
くためのカウンタである。このステップ１１１の処理で
得られた出力は、ステップ１１２へ受け渡され、このス
テップ１１２では、現在受信語Ｒ（ｌ ）の復号化を試
みる。この現在受信語Ｒ（ｌ ）において誤り訂正が可
能であったならば、誤り集合Ｅ（ｌ ）をステップ１１
３へ受け渡し、このステップ１１３では誤り集合Ｅ（ｌ
）の格納を行なう。一方、現在受信語Ｒ（ｌ ）におい
て誤り訂正が不可能であったならば、ステップ１１６へ
進み、フラグ集合Ｆにインデックスｌ を追加する。ス
テップ１１３で得られた出力と、ステップ１１６で得ら
れた出力とは、ステップ１１４へ送られ、このステップ
１１４では、インデックスｌ を「１」だけインクリメ
ントする。このステップ１１４からは、ステップ１１５
へ進み、このステップ１１５では、ｌ の値がλの値に
達したか否かを調べる。これは、換言するならば、全て
の受信語の処理が完了したか否かを調べていることに他
ならない。もし、全ての受信語の処理が完了していなか
ったならば、ステップ１１２へ戻り、このステップ１１
２からステップ１１５までの処理を反復して実行する。
一方、最後の受信語の処理が完了していたならば、その
処理結果をステップ１１７へ受け渡し、このステップ１
１７では、フラグで標識付けされている受信語が存在し
ているか否かを調べる（即ち、フラグ集合Ｆを調べ
る）。もし、フラグで標識付けされている受信語が１つ
も存在していなかったならば、ステップ１１８におい
て、訂正済符号語Ｃ（ｌ ）を、この復号器２４の出力
として送出する。一方、フラグで標識付けされている受
信語が存在していたならば、フラグ集合Ｆの内容を、ス
テップ１１９へ受け渡し、このステップ１１９から、強
化復号化処理のプロセスを開始する。
は、配線して組立てたハードウェアのロジックによって
実現することもできるが、図５のフローチャートに示し
たように、ソフトウェアによっても実現することのでき
るものである。図５のフローチャートのステップ１１０
では、復号器２４が、その入力として、デインターリー
バー２２からλ個の受信語Ｒ（０）、Ｒ（１）、... 、
Ｒ（λ−１）を受け取る。この入力はステップ１１１へ
受け渡され、このステップ１１１では、フラグ集合Ｆを
空集合にセットすると共に、ｌ −カウンタを「０」に
セットする。フラグ集合Ｆは、訂正不可能な受信語のイ
ンデックスを格納するための（即ち、訂正不可能な受信
語にフラグで標識付けするための）集合であり、一方、
ｌ −カウンタは、処理中の受信語の番号を保持してお
くためのカウンタである。このステップ１１１の処理で
得られた出力は、ステップ１１２へ受け渡され、このス
テップ１１２では、現在受信語Ｒ（ｌ ）の復号化を試
みる。この現在受信語Ｒ（ｌ ）において誤り訂正が可
能であったならば、誤り集合Ｅ（ｌ ）をステップ１１
３へ受け渡し、このステップ１１３では誤り集合Ｅ（ｌ
）の格納を行なう。一方、現在受信語Ｒ（ｌ ）におい
て誤り訂正が不可能であったならば、ステップ１１６へ
進み、フラグ集合Ｆにインデックスｌ を追加する。ス
テップ１１３で得られた出力と、ステップ１１６で得ら
れた出力とは、ステップ１１４へ送られ、このステップ
１１４では、インデックスｌ を「１」だけインクリメ
ントする。このステップ１１４からは、ステップ１１５
へ進み、このステップ１１５では、ｌ の値がλの値に
達したか否かを調べる。これは、換言するならば、全て
の受信語の処理が完了したか否かを調べていることに他
ならない。もし、全ての受信語の処理が完了していなか
ったならば、ステップ１１２へ戻り、このステップ１１
２からステップ１１５までの処理を反復して実行する。
一方、最後の受信語の処理が完了していたならば、その
処理結果をステップ１１７へ受け渡し、このステップ１
１７では、フラグで標識付けされている受信語が存在し
ているか否かを調べる（即ち、フラグ集合Ｆを調べ
る）。もし、フラグで標識付けされている受信語が１つ
も存在していなかったならば、ステップ１１８におい
て、訂正済符号語Ｃ（ｌ ）を、この復号器２４の出力
として送出する。一方、フラグで標識付けされている受
信語が存在していたならば、フラグ集合Ｆの内容を、ス
テップ１１９へ受け渡し、このステップ１１９から、強
化復号化処理のプロセスを開始する。
【００２０】ステップ１１９では、受信語の全てにフラ
グで標識付けされているのか否かを調べる。もしそうで
あれば、強化復号器であっても処理は不可能であるた
め、ステップ１２０において、訂正不可能な誤りである
ことを宣言するための所定のプロトコルを起動する。一
方、フラグで標識付けされていない受信語が存在してい
たならば、ステップ１２１において、フラグ集合Ｆの中
の第１番目の要素ｊを判別する。続いてステップ１２２
において、その判別した要素ｊに対応した受信語Ｒ
（ｊ）にとっての、先行受信語Ｒ（《ｊ−１》λ）の誤
り集合（即ち、誤り集合Ｅ（《ｊ−１》λ））が、空集
合であるか否かを調べる。もしその誤り集合が空集合で
あったならば、誤り集合Ｅ（ｊ）の状態改善を行なうこ
とは不可能であるため、ステップ１２０へ進んで、訂正
不可能な誤りであることを宣言するための所定のプロト
コルを起動する。一方、誤り集合Ｅ（《ｊ−１》λ）が
空集合ではなかったならば、ステップ１２３において、
この誤り集合Ｅ（《ｊ−１》λ）に基づいて、受信語Ｒ
（ｊ）の中の《１＋Ｅ（《ｊ−１》λ）》nで表わされ
る夫々のロケーションに誤りがあるものと予測する。そ
れらロケーションは、この受信語Ｒ（ｊ）の中にあるロ
ケーションのうち、集合Ｅ（《ｊ−１》λ）に含まれて
いる位置に対して斜めに隣接した位置に相当するロケー
ションである。復号器２４は、それら予測ロケーション
が消滅痕であることを宣言した上で、ステップ１２４に
おいて、受信語Ｒ（ｊ）の復号化を試みる。もし受信語
Ｒ（ｊ）が、それらロケーションが消滅痕であると宣言
しても尚、復号化の不可能なものであったならば、ステ
ップ１２０へ進んで上述のプロトコルを起動する。一
方、受信語Ｒ（ｊ）の復号化が、その消滅痕の宣言によ
って可能になったならば、ステップ１２５において、こ
の受信語Ｒ（ｊ）の誤り集合Ｅ（ｊ）を格納し、続いて
ステップ１２６において、フラグ集合Ｆから要素ｊを抜
き取った後に、ステップ１１７へ戻り、そしてこのステ
ップ１１７から、以上の強化復号化処理のプロセスを反
復して実行する。
グで標識付けされているのか否かを調べる。もしそうで
あれば、強化復号器であっても処理は不可能であるた
め、ステップ１２０において、訂正不可能な誤りである
ことを宣言するための所定のプロトコルを起動する。一
方、フラグで標識付けされていない受信語が存在してい
たならば、ステップ１２１において、フラグ集合Ｆの中
の第１番目の要素ｊを判別する。続いてステップ１２２
において、その判別した要素ｊに対応した受信語Ｒ
（ｊ）にとっての、先行受信語Ｒ（《ｊ−１》λ）の誤
り集合（即ち、誤り集合Ｅ（《ｊ−１》λ））が、空集
合であるか否かを調べる。もしその誤り集合が空集合で
あったならば、誤り集合Ｅ（ｊ）の状態改善を行なうこ
とは不可能であるため、ステップ１２０へ進んで、訂正
不可能な誤りであることを宣言するための所定のプロト
コルを起動する。一方、誤り集合Ｅ（《ｊ−１》λ）が
空集合ではなかったならば、ステップ１２３において、
この誤り集合Ｅ（《ｊ−１》λ）に基づいて、受信語Ｒ
（ｊ）の中の《１＋Ｅ（《ｊ−１》λ）》nで表わされ
る夫々のロケーションに誤りがあるものと予測する。そ
れらロケーションは、この受信語Ｒ（ｊ）の中にあるロ
ケーションのうち、集合Ｅ（《ｊ−１》λ）に含まれて
いる位置に対して斜めに隣接した位置に相当するロケー
ションである。復号器２４は、それら予測ロケーション
が消滅痕であることを宣言した上で、ステップ１２４に
おいて、受信語Ｒ（ｊ）の復号化を試みる。もし受信語
Ｒ（ｊ）が、それらロケーションが消滅痕であると宣言
しても尚、復号化の不可能なものであったならば、ステ
ップ１２０へ進んで上述のプロトコルを起動する。一
方、受信語Ｒ（ｊ）の復号化が、その消滅痕の宣言によ
って可能になったならば、ステップ１２５において、こ
の受信語Ｒ（ｊ）の誤り集合Ｅ（ｊ）を格納し、続いて
ステップ１２６において、フラグ集合Ｆから要素ｊを抜
き取った後に、ステップ１１７へ戻り、そしてこのステ
ップ１１７から、以上の強化復号化処理のプロセスを反
復して実行する。
【００２１】具体例II 容易に理解されるように、以上の具体例Iのプロセスで
は、フラグで標識付けされているある横列の中に多数の
ランダム誤りＲが含まれていた場合には、その横列に基
づいて、後続の横列において消滅痕を宣言したならば、
宣言された消滅痕のうちに、多くの偽消滅痕が含まれて
しまうことになる。そして、このような事態が生じる
と、ＥＣＣ符号の誤り訂正能力を超えてしまったり、誤
った訂正が行なわれてしまうおそれがある。
は、フラグで標識付けされているある横列の中に多数の
ランダム誤りＲが含まれていた場合には、その横列に基
づいて、後続の横列において消滅痕を宣言したならば、
宣言された消滅痕のうちに、多くの偽消滅痕が含まれて
しまうことになる。そして、このような事態が生じる
と、ＥＣＣ符号の誤り訂正能力を超えてしまったり、誤
った訂正が行なわれてしまうおそれがある。
【００２２】この具体例IIでは、具体例Iで使用してい
るものと同じ［ｎ，ｋ］ＲＳ符号を使用するものとする
が、ただしここでは、発生した誤りのパターンは、図４
の誤りパターンとはやや異なった、図６に示したパター
ンであったものとする。具体例Iの場合と同様に、ここ
でも復号器２４は、４つまでの誤りを検出することがで
き、３つまでの誤りを訂正することができる。復号器２
４は、最初の復号化の際に、横列０、横列１、横列３、
横列４、及び横列５に関しては誤り訂正を行ない、横列
２には、フラグで標識付けをする。続いて符号器２４
は、横列１のバイト４とバイト８とに誤りが発生してい
たことから、横列２のバイト５とバイト９とが消滅痕で
あると宣言する。この結果、この横列２には、３つの誤
り（バイト２、１２の２つのＲ、それにバイト１５のｂ
1）と、バイト５の（偽の）消滅痕ｂ2と、バイト９の消
滅痕ｂ3とを含むことになる。誤りと消滅痕との組み合
わせがこのようになっている場合には、図５のフローチ
ャートに関して説明したステップでは、その誤りと消滅
痕との組み合わせを、検出することはできるが、訂正す
ることはできない。何故ならば、このような組み合わせ
は、このＥＣＣの誤り訂正能力を超えているからであ
る。
るものと同じ［ｎ，ｋ］ＲＳ符号を使用するものとする
が、ただしここでは、発生した誤りのパターンは、図４
の誤りパターンとはやや異なった、図６に示したパター
ンであったものとする。具体例Iの場合と同様に、ここ
でも復号器２４は、４つまでの誤りを検出することがで
き、３つまでの誤りを訂正することができる。復号器２
４は、最初の復号化の際に、横列０、横列１、横列３、
横列４、及び横列５に関しては誤り訂正を行ない、横列
２には、フラグで標識付けをする。続いて符号器２４
は、横列１のバイト４とバイト８とに誤りが発生してい
たことから、横列２のバイト５とバイト９とが消滅痕で
あると宣言する。この結果、この横列２には、３つの誤
り（バイト２、１２の２つのＲ、それにバイト１５のｂ
1）と、バイト５の（偽の）消滅痕ｂ2と、バイト９の消
滅痕ｂ3とを含むことになる。誤りと消滅痕との組み合
わせがこのようになっている場合には、図５のフローチ
ャートに関して説明したステップでは、その誤りと消滅
痕との組み合わせを、検出することはできるが、訂正す
ることはできない。何故ならば、このような組み合わせ
は、このＥＣＣの誤り訂正能力を超えているからであ
る。
【００２３】そこで、この問題を克服し、誤った訂正が
行なわれる確率を大幅に低減することのできる、具体例
Iに示したものよりも複雑な２通りの復号化方法の実施
例について、以下に説明する。尚、図７と図８とに示し
た夫々の復号化方法において、図５の復号化方法の中の
ステップと同一内容のステップには同一の引用符号を付
してあり、また、図５の復号化方法の中のステップとは
やや内容が異なるステップには、図５で使用した引用符
号にダッシュ（図７）ないしダブル・ダッシュ（図８）
を加えた引用符号を付してある。
行なわれる確率を大幅に低減することのできる、具体例
Iに示したものよりも複雑な２通りの復号化方法の実施
例について、以下に説明する。尚、図７と図８とに示し
た夫々の復号化方法において、図５の復号化方法の中の
ステップと同一内容のステップには同一の引用符号を付
してあり、また、図５の復号化方法の中のステップとは
やや内容が異なるステップには、図５で使用した引用符
号にダッシュ（図７）ないしダブル・ダッシュ（図８）
を加えた引用符号を付してある。
【００２４】図７に示した復号化方法は、そのステップ
１２３’の手前までの部分は、図５に関して説明した復
号化方法と同じであるが、このステップ１２３’では、
図５のステップ１２３よりも更に複雑な処理を実行する
ようにしている。即ち、このステップ１２３’では、誤
り集合Ｅ（《ｊ−１》λ）の部分集合Ａの各々につい
て、受信語Ｒ（ｊ）の中の《Ａ＋１》nで表わされるロ
ケーションを消滅痕であると宣言した上で、受信語Ｒ
（ｊ）の復号化を試みるようにしている。そして、ある
部分集合Ａについて、受信語Ｒ（ｊ）の復号化が可能で
あったならば、その部分集合Ａに対応した誤り集合Ｅ
（Ａ）を格納する。そして、こうして得られた（通常は
複数の）誤り集合Ｅ（Ａ）の内容をステップ１２４’へ
受け渡し、このステップ１２４’では、それら複数の集
合Ｅ（Ａ）のうちに多数派が存在しているか否か（即
ち、それら集合Ｅ（Ａ）のうちに、互いに同一の多数の
集合が存在しているか否か）を判断する。もし集合Ｅ
（Ａ）のうちに多数派が存在していなかったならば、ス
テップ１２０へ進んで、訂正不可能な誤りに対処するた
めのプロトコルを起動する。一方、集合Ｅ（Ａ）のうち
に多数派が存在していたならば、ステップ１２５’にお
いて、その多数派を誤り集合Ｅ（ｊ）として該誤り集合
Ｅ（ｊ）を格納し、これ以後、図５の復号化方法と同様
に処理を続行する。
１２３’の手前までの部分は、図５に関して説明した復
号化方法と同じであるが、このステップ１２３’では、
図５のステップ１２３よりも更に複雑な処理を実行する
ようにしている。即ち、このステップ１２３’では、誤
り集合Ｅ（《ｊ−１》λ）の部分集合Ａの各々につい
て、受信語Ｒ（ｊ）の中の《Ａ＋１》nで表わされるロ
ケーションを消滅痕であると宣言した上で、受信語Ｒ
（ｊ）の復号化を試みるようにしている。そして、ある
部分集合Ａについて、受信語Ｒ（ｊ）の復号化が可能で
あったならば、その部分集合Ａに対応した誤り集合Ｅ
（Ａ）を格納する。そして、こうして得られた（通常は
複数の）誤り集合Ｅ（Ａ）の内容をステップ１２４’へ
受け渡し、このステップ１２４’では、それら複数の集
合Ｅ（Ａ）のうちに多数派が存在しているか否か（即
ち、それら集合Ｅ（Ａ）のうちに、互いに同一の多数の
集合が存在しているか否か）を判断する。もし集合Ｅ
（Ａ）のうちに多数派が存在していなかったならば、ス
テップ１２０へ進んで、訂正不可能な誤りに対処するた
めのプロトコルを起動する。一方、集合Ｅ（Ａ）のうち
に多数派が存在していたならば、ステップ１２５’にお
いて、その多数派を誤り集合Ｅ（ｊ）として該誤り集合
Ｅ（ｊ）を格納し、これ以後、図５の復号化方法と同様
に処理を続行する。
【００２５】図８に示した復号化方法は、そのステップ
１２２”及びステップ１２３”以外の部分は、図５に関
して説明した復号化方法と同じである。ステップ１２
２”では、フラグで標識付けされている受信語のうちの
最初の受信語Ｒ（ｊ）に対して先行する受信語Ｒ（《ｊ
−１》λ）と後続の受信語Ｒ（《ｊ＋１》λ）の、夫々
の誤り集合Ｅ（《ｊ−１》λ）とＥ（《ｊ＋１》λ）と
を共に調べる。もしそれら誤り集合のうちのいずれか一
方が空集合であったならば、ステップ１２０へ進んで、
訂正不可能な誤りに対処するためのプロトコルを起動す
る。一方、それら誤り集合がいずれも空集合ではなかっ
たならば、ステップ１２３”へ進む。このステップ１２
３”では、受信語Ｒ（ｊ）の中のロケーションのうち、
先行する符号語Ｒ（《ｊ−１》λ）の誤り集合Ｅ（《ｊ
−１》λ）の中のいずれかの要素の位置に対しても斜め
に隣接し、また、後続の受信語Ｒ（《ｊ＋１》λ）の誤
り集合Ｅ（《ｊ＋１》λ）の中のいずれかの要素の位置
に対しても斜めに隣接した位置（この「斜めに隣接した
位置」とは、前述のインターリーブの規則に従って書込
みをおこなうときの連続した斜めの位置のことである）
に相当するロケーションを、消滅痕であると宣言する。
換言すれば、受信語Ｒ（ｊ）のロケーションのうちで消
滅痕であると宣言されるロケーションは、《Ｅ（《ｊ−
１》λ）＋１》nで表わされるロケーション集合と、
《Ｅ（《ｊ＋１》λ）−１》nで表わされるロケーショ
ン集合との、交わり集合（∩）に含まれるロケーション
である。これ以後、この図８の復号化方法は、図５の復
号化方法と同様に処理を続行する。
１２２”及びステップ１２３”以外の部分は、図５に関
して説明した復号化方法と同じである。ステップ１２
２”では、フラグで標識付けされている受信語のうちの
最初の受信語Ｒ（ｊ）に対して先行する受信語Ｒ（《ｊ
−１》λ）と後続の受信語Ｒ（《ｊ＋１》λ）の、夫々
の誤り集合Ｅ（《ｊ−１》λ）とＥ（《ｊ＋１》λ）と
を共に調べる。もしそれら誤り集合のうちのいずれか一
方が空集合であったならば、ステップ１２０へ進んで、
訂正不可能な誤りに対処するためのプロトコルを起動す
る。一方、それら誤り集合がいずれも空集合ではなかっ
たならば、ステップ１２３”へ進む。このステップ１２
３”では、受信語Ｒ（ｊ）の中のロケーションのうち、
先行する符号語Ｒ（《ｊ−１》λ）の誤り集合Ｅ（《ｊ
−１》λ）の中のいずれかの要素の位置に対しても斜め
に隣接し、また、後続の受信語Ｒ（《ｊ＋１》λ）の誤
り集合Ｅ（《ｊ＋１》λ）の中のいずれかの要素の位置
に対しても斜めに隣接した位置（この「斜めに隣接した
位置」とは、前述のインターリーブの規則に従って書込
みをおこなうときの連続した斜めの位置のことである）
に相当するロケーションを、消滅痕であると宣言する。
換言すれば、受信語Ｒ（ｊ）のロケーションのうちで消
滅痕であると宣言されるロケーションは、《Ｅ（《ｊ−
１》λ）＋１》nで表わされるロケーション集合と、
《Ｅ（《ｊ＋１》λ）−１》nで表わされるロケーショ
ン集合との、交わり集合（∩）に含まれるロケーション
である。これ以後、この図８の復号化方法は、図５の復
号化方法と同様に処理を続行する。
【００２６】
【発明の効果】本発明は、以上説明したような方法でデ
ータを符号化し、かつインターリーブして伝送し、そし
て受信側においてデーンターリーブし、復号化するよう
構成されているので、従来例のものと比較して、ＥＣＣ
の符号語を復号化する能力を強化することができ、しか
も螺旋対称性が壊れることがないので複雑な処理を必要
としない、という作用効果を奏することができる。
ータを符号化し、かつインターリーブして伝送し、そし
て受信側においてデーンターリーブし、復号化するよう
構成されているので、従来例のものと比較して、ＥＣＣ
の符号語を復号化する能力を強化することができ、しか
も螺旋対称性が壊れることがないので複雑な処理を必要
としない、という作用効果を奏することができる。
【図１】従来例である米国特許第４５５９６２５号に記
載されている螺旋インターリーブ法のデータ書込みシー
ケンスを、単純化して示した説明図である。
載されている螺旋インターリーブ法のデータ書込みシー
ケンスを、単純化して示した説明図である。
【図２】通信チャネルを介して伝送されるディジタル・
データを符号化及び復号化するための、本発明の実施例
に係る装置のブロック図である。
データを符号化及び復号化するための、本発明の実施例
に係る装置のブロック図である。
【図３】本発明の実施例に係る円環体インターリーブ法
のデータ書込みシーケンスを、単純化して示した説明図
である。
のデータ書込みシーケンスを、単純化して示した説明図
である。
【図４】一具体例の誤りパターンの模式図である。
【図５】図４の誤りパターンを復号化することのでき
る、本発明の方法を示したフローチャートである。
る、本発明の方法を示したフローチャートである。
【図６】図４の誤りパターンとは幾分異なった、別具体
例の誤りパターンの模式図である。
例の誤りパターンの模式図である。
【図７】図６の誤りパターンを復号化することのでき
る、本発明の方法を示したフローチャートである。
る、本発明の方法を示したフローチャートである。
【図８】図６の誤りパターンを図７の方法とは別の方法
で復号化することのできる、本発明の方法を示したフロ
ーチャートである。
で復号化することのできる、本発明の方法を示したフロ
ーチャートである。
フロントページの続き (72)発明者 ヘンリクス・セー・ヴァン・ティルボルグ オランダ王国5683 エル・イェー・ベス ト、クラボトス 19番地
Claims (12)
- 【請求項１】 誤り訂正符号（ＥＣＣ符号）に従いイン
ターリーブされた複数のコード化済シンボルから成る複
数の符号語を復号化する復号器の能力を、冗長度を増大
することなく強化する、復号器能力強化方法において、 全ての符号語を復号化し、全ての訂正可能な符号語の中
の全ての訂正可能な誤りを訂正し、前記ＥＣＣ符号の誤
り訂正能力を超える符号語のみをフラグで標識付けして
フラグ付符号語とする、復号化ステップと、 前記フラグ付符号語の各々について、当該フラグ付符号
語に対して時間的に隣接した少なくとも１つの符号語を
検査して、その隣接符号語中の誤り状態にあるロケーシ
ョンであって、訂正がなされてその復号化が成功したロ
ケーションを識別する、検査ステップと、 当該フラグ付符号語中のロケーションのうち、その隣接
符号語中の誤り状態にあったロケーションに対して斜め
方向に時間的に隣接した特定ロケーションに存在する誤
りを暫定的に消滅痕であると宣言する、宣言ステップ
と、 前記復号化ステップを再実行して、当該フラグ付符号語
を訂正して復号化することを試みる、再実行ステップ
と、 を含んでいることを特徴とする復号器能力強化方法。 - 【請求項２】 請求項１記載の方法において、該方法は
更に、 ｎの値とλの値とを、それら値が互いに素であるという
条件を満足する任意の所望の整数値に選定するステップ
と、 複数の符号語が矩形ブロックの中に並ぶように符号化を
行ない、その際に各ブロックにおいて、個々の符号語が
そのブロックの中の各々の横列を成すようにすると共
に、夫々の横列を成す符号語の間で互いに対応するシン
ボルどうしが縦方向に位置が揃うようにし、更に、各ブ
ロックが、シンボルｎ個分の長さの符号語がλ行並んだ
ものから成るようにする、符号化ステップと、 各ブロック中の連続する複数の符号語の複数のシンボル
を、１つの連続した斜めのシーケンスに沿ってインター
リーブすることにより、位相幾何学的に円環体を成すア
レイを形成し、それによって、全てのバースト誤りが、
前記アレイ中のそれらバースト誤りの発生位置にかかわ
らず符号語から符号語へと連続するようにする、インタ
ーリーブステップと、 を含んでいることを特徴とする方法。 - 【請求項３】 請求項１記載の方法において、該方法は
更に、 複数の符号語が矩形ブロックの中に並ぶように符号化を
行ない、その際に各ブロックが、シンボルｎ個分の長さ
の横列が縦にλ本並んだものから成るようにすると共
に、各ブロックにおいて、夫々の横列の間で互いに対応
するシンボルどうしが縦方向に位置が揃うようにする、
符号化ステップと、 ａ（ｉ、ｊ）を各ブロックのｉ＋１行、ｊ＋１列（ただ
し、０≦ｉ≦λ−１、０≦ｊ≦ｎ−１）のシンボルとし
て、各ブロックの中の複数のシンボルを、 ・ａ（０、０）の書込みを行ない、 ・ａ（ｉ、ｊ）の書込みを行なったならば、続いてａ
（《ｉ＋１》λ、《ｊ＋１》n）の書込みを行ない、 ・ａ（λ−１、ｎ−１）の書込みを行なったならば、終
了する という規則によって規定されるシーケンスに沿って、斜
め方向にインターリーブすることにより、位相幾何学的
に円環体を成すアレイを形成し、それによって、全ての
バースト誤りが、前記アレイ中のそれらバースト誤りの
発生位置にかかわらず符号語から符号語へと連続するよ
うにする、インターリーブステップと、 を含んでいることを特徴とする方法。 - 【請求項４】 請求項１記載の方法において、前記検査
ステップで、前記フラグ付符号語に対する先行符号語と
後続符号語との誤りの有無を検査し、且つ、前記宣言ス
テップで、前記先行符号語中の誤り状態ロケーションと
前記後続符号語中の誤り状態ロケーションとの両方に対
して時間的に斜めに隣接する、該フラグ付符号語中のロ
ケーションを消滅痕であると宣言するようにしたことを
特徴とする方法。 - 【請求項５】 請求項１記載の方法において、該方法は
更に、 前記フラグ付符号語が、前記再実行ステップにおいて訂
正不可能であったならば、訂正不可能誤りの宣言をす
る、訂正不可能誤り宣言ステップと、 所定のプロトコルを起動するステップと、 を含んでいることを特徴とする方法。 - 【請求項６】 請求項１記載の方法において、前記検査
ステップに続き、所定のプロトコルに従って、誤り状態
ロケーションであると識別したロケーションを分離して
誤り集合とする、誤り集合形成ステップを含んでおり、
且つ、前記宣言ステップでは、異なった夫々の誤り集合
中の誤り状態ロケーションに対して隣接した特定のロケ
ーションをシーケンシャルに消滅痕として宣言するよう
にしたことを特徴とする方法。 - 【請求項７】 ＥＣＣ符号に従いインターリーブされた
複数のコード化済シンボルから成る複数の符号語を復号
化する復号器の能力を、冗長度を増大することなく強化
する、復号器能力強化方法において、 複数の符号語が矩形ブロックの中に並ぶように符号化を
行ない、その際に各ブロックにおいて、個々の符号語が
そのブロックの中の各々の横列を成すようにすると共
に、夫々の横列を成す符号語の間で互いに対応するシン
ボルどうしが縦方向に位置が揃うようにする、符号化ス
テップと、 一度にブロック１つずつのインターリーブを行ない、そ
の際に、そのブロック中の連続する複数の符号語の複数
のシンボルを、１つの連続した斜めのシーケンスに沿っ
てインターリーブすることにより、位相幾何学的に円環
体を成すアレイを形成し、それによって、全てのバース
ト誤りが、前記アレイ中のそれらバースト誤りの発生位
置にかかわらず符号語から符号語へと連続するようにす
るインターリーブステップと、 を含んでいることを特徴とする復号器能力強化方法。 - 【請求項８】 請求項７記載の方法において、 前記矩形ブロックの各々が、シンボルｎ個分の長さの符
号語がλ行並んだものから成るようにし、且つ、 インターリーブステップにおいて、ａ（ｉ、ｊ）を各ブ
ロックのｉ＋１行、ｊ＋１列（ただし、０≦ｉ≦λ−
１、０≦ｊ≦ｎ−１）のシンボルとして、各ブロック中
の複数のシンボルを、 ・ａ（０、０）の書込みを行ない、 ・ａ（ｉ、ｊ）の書込みを行なったならば、続いてａ
（《ｉ＋１》λ、《ｊ＋１》n）の書込みを行ない、 ・ａ（λ−１、ｎ−１）の書込みを行なったならば、終
了する という規則によって規定されるシーケンスに沿って、斜
め方向にインターリーブすることにより、位相幾何学的
に円環体を成すアレイを形成するようにした、 ことを特徴とする方法。 - 【請求項９】 請求項８記載の方法において、該方法は
更に、ｎの値とλの値とを、それら値が互いに素である
という条件を満足する任意の所望の整数値に選定するス
テップ、を含んでいることを特徴とする方法。 - 【請求項１０】 ＥＣＣ符号に従いインターリーブされ
た複数のコード化済シンボルから成る複数の符号語を復
号化する復号器の能力を、冗長度を増大することなく強
化する、復号器能力強化方法において、 複数の符号語が矩形ブロックの中に並ぶように符号化を
行ない、その際に各ブロックにおいて、個々の符号語が
そのブロックの中の各々の横列を成すようにすると共
に、夫々の横列を成す符号語の間で互いに対応するシン
ボルどうしが縦方向に位置が揃うようにする、符号化ス
テップと、 一度にブロック１つずつのインターリーブを行ない、そ
の際に、そのブロック中の連続する複数の符号語の複数
のシンボルを、１つの連続した斜めのシーケンスに沿っ
てインターリーブすることにより、位相幾何学的に円環
体を成すアレイを形成し、それによって、全てのバース
ト誤りが、前記アレイ中のそれらバースト誤りの発生位
置にかかわらず符号語から符号語へと連続するようにす
るインターリーブステップと、 全ての符号語を復号化し、全ての訂正可能な誤りを訂正
し、前記ＥＣＣ符号の誤り訂正能力を超える符号語のみ
をフラグで標識付けしてフラグ付符号語とする、復号化
ステップと、 前記フラグ付符号語の各々について、当該フラグ付符号
語に対して時間的に隣接した少なくとも１つの符号語を
検査して、その隣接符号語中の誤り状態におるロケーシ
ョンであって、訂正がなされてその復号化が成功したロ
ケーションを識別する、検査ステップと、 当該フラグ付符号語中のロケーションのうち、その隣接
符号語の中の誤り状態にあったロケーションに対して、
斜め方向の連続シーケンスの中にあって時間的に隣接し
た、特定ロケーションに存在する誤りを暫定的に消滅痕
であると宣言する、宣言ステップと、 前記復号化ステップを再実行して、当該フラグ付符号語
を訂正して復号化することを試みる、再実行ステップ
と、 を含んでいることを特徴とする復号器能力強化方法。 - 【請求項１１】 請求項１０記載の方法において、前記
矩形ブロックの各々が、シンボルｎ個分の長さのコード
化済符号語がλ行並んだものから成るようにしてあり、
且つ、ｎの値とλの値とが互いに素であるという条件を
満足する任意の所望の整数値に選定されていることを特
徴とする方法。 - 【請求項１２】 請求項１０記載の方法において、前記
復号化ステップは、各々のブロックの復号化を、そのブ
ロックの次のブロックの復号化を開始する前に完了させ
るようにしたことを特徴とする方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US792113 | 1991-11-14 | ||
| US07/792,113 US5299208A (en) | 1991-11-14 | 1991-11-14 | Enhanced decoding of interleaved error correcting codes |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH05244020A true JPH05244020A (ja) | 1993-09-21 |
| JP2520551B2 JP2520551B2 (ja) | 1996-07-31 |
Family
ID=25155836
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4270145A Expired - Lifetime JP2520551B2 (ja) | 1991-11-14 | 1992-10-08 | インタ―リ―ブ式の誤り訂正符号を復号化するための復号器能力強化方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5299208A (ja) |
| JP (1) | JP2520551B2 (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2001076078A1 (en) * | 2000-03-31 | 2001-10-11 | Mitsubishi Denki Kabushiki Kaisha | Communication apparatus and communication method |
| WO2001091307A1 (en) * | 2000-05-22 | 2001-11-29 | Mitsubishi Denki Kabushiki Kaisha | Communication apparatus and communication method |
| JP2003518800A (ja) * | 1999-12-20 | 2003-06-10 | コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ | 改善されたデコーダーを備えた受信機 |
| JP2010152745A (ja) * | 2008-12-25 | 2010-07-08 | Nec Corp | ディスクアレイ装置 |
Families Citing this family (31)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05182368A (ja) * | 1992-01-07 | 1993-07-23 | Pioneer Electron Corp | 記録媒体演奏装置における情報データの有無検出装置 |
| US5589994A (en) * | 1992-08-21 | 1996-12-31 | Mitsubishi Denki Kabushiki Kaisha | Image recording method and apparatus with reduced error propagation |
| US5602857A (en) * | 1993-09-21 | 1997-02-11 | Cirrus Logic, Inc. | Error correction method and apparatus |
| US5559506A (en) * | 1994-05-04 | 1996-09-24 | Motorola, Inc. | Method and apparatus for encoding and decoding a digital radio signal |
| US6125469A (en) * | 1994-10-18 | 2000-09-26 | Cirrus Logic, Inc. | Error correction method and apparatus |
| US5774481A (en) * | 1995-03-31 | 1998-06-30 | International Business Machines Corporation | Reduced gate error detection and correction circuit |
| US5796755A (en) * | 1995-10-10 | 1998-08-18 | Eastman Kodak Company | Error minimization in interleaved error correcting codes |
| US5983383A (en) * | 1997-01-17 | 1999-11-09 | Qualcom Incorporated | Method and apparatus for transmitting and receiving concatenated code data |
| US6378100B1 (en) | 1997-12-29 | 2002-04-23 | U.S. Philips Corporation | Method and apparatus for encoding multiword information with error locative clues directed to low protectivity words |
| IL131627A (en) * | 1997-12-29 | 2005-08-31 | Koninkl Philips Electronics Nv | Method for encoding multiword information |
| TR199903284T1 (xx) * | 1998-04-29 | 2000-10-23 | Koninklijke Philips Electronics N.V. | �ok kelimeli bilgilerin �ifrelenmesi i�in bir y�ntem, alet ve ta��y�c�. |
| US6321357B1 (en) | 1998-05-31 | 2001-11-20 | Innomedia Pte Ltd | Method and apparatus for burst error correction |
| CN1288561C (zh) * | 1998-07-27 | 2006-12-06 | 皇家菲利浦电子有限公司 | 具有字方式交错和多字编码信息的记录载体 |
| US6240538B1 (en) | 1998-09-10 | 2001-05-29 | Ericsson Inc. | Method and apparatus for errors and erasures decoding |
| JP3214478B2 (ja) * | 1998-12-28 | 2001-10-02 | 日本電気株式会社 | 誤り訂正復号装置 |
| US20020138793A1 (en) * | 2001-03-26 | 2002-09-26 | Leif Wilhelmsson | Iterative decoding of differentially modulated symbols |
| US6901550B2 (en) | 2001-10-17 | 2005-05-31 | Actelis Networks Inc. | Two-dimensional interleaving in a modem pool environment |
| ATE408931T1 (de) * | 2002-04-05 | 2008-10-15 | Koninkl Philips Electronics Nv | Verfahren und vorrichtung zur einbettung einer zusätzlichen schicht der fehlerkorrektur in einen fehlerkorrekturcode |
| WO2003085840A1 (en) * | 2002-04-05 | 2003-10-16 | Koninklijke Philips Electronics N.V. | Method and apparatus for embedding an additional layer of error correction into an error correcting code |
| US7055082B2 (en) * | 2002-10-29 | 2006-05-30 | Victor Company Of Japan, Ltd. | Information recording and reproducing apparatus |
| US7434138B2 (en) * | 2005-06-27 | 2008-10-07 | Agere Systems Inc. | Structured interleaving/de-interleaving scheme for product code encoders/decorders |
| US7734984B2 (en) * | 2006-04-13 | 2010-06-08 | Trident Microsystems (Far East) Ltd. | Erasures assisted block code decoder and related method |
| US20090177943A1 (en) * | 2008-01-09 | 2009-07-09 | Broadcom Corporation | Error correction coding using soft information and interleaving |
| US8910012B2 (en) * | 2012-10-16 | 2014-12-09 | International Business Machines Corporation | Block-interleaved and error correction code (ECC)-encoded sub data set (SDS) format |
| GB2608878B (en) | 2018-06-29 | 2023-04-12 | Imagination Tech Ltd | Guaranteed data compression |
| GB2575435B (en) * | 2018-06-29 | 2022-02-09 | Imagination Tech Ltd | Guaranteed data compression |
| GB2575434B (en) | 2018-06-29 | 2020-07-22 | Imagination Tech Ltd | Guaranteed data compression |
| GB2575121B (en) | 2018-06-29 | 2022-12-28 | Imagination Tech Ltd | Guaranteed data compression |
| GB2575436B (en) | 2018-06-29 | 2022-03-09 | Imagination Tech Ltd | Guaranteed data compression |
| US11190209B2 (en) * | 2019-01-30 | 2021-11-30 | International Business Machines Corporation | Expansion for Blaum-Roth codes |
| US11175986B1 (en) | 2020-07-01 | 2021-11-16 | International Business Machines Corporation | Storage systems implementing offset erasure code stripes |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58171146A (ja) * | 1982-04-01 | 1983-10-07 | Mitsubishi Electric Corp | 復号化装置 |
| JPS61283225A (ja) * | 1985-06-10 | 1986-12-13 | Nec Corp | 誤り訂正符号復号器 |
| JPH02246440A (ja) * | 1989-03-18 | 1990-10-02 | Canon Inc | 符号伝送方法 |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4559625A (en) * | 1983-07-28 | 1985-12-17 | Cyclotomics, Inc. | Interleavers for digital communications |
-
1991
- 1991-11-14 US US07/792,113 patent/US5299208A/en not_active Expired - Fee Related
-
1992
- 1992-10-08 JP JP4270145A patent/JP2520551B2/ja not_active Expired - Lifetime
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58171146A (ja) * | 1982-04-01 | 1983-10-07 | Mitsubishi Electric Corp | 復号化装置 |
| JPS61283225A (ja) * | 1985-06-10 | 1986-12-13 | Nec Corp | 誤り訂正符号復号器 |
| JPH02246440A (ja) * | 1989-03-18 | 1990-10-02 | Canon Inc | 符号伝送方法 |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2003518800A (ja) * | 1999-12-20 | 2003-06-10 | コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ | 改善されたデコーダーを備えた受信機 |
| WO2001076078A1 (en) * | 2000-03-31 | 2001-10-11 | Mitsubishi Denki Kabushiki Kaisha | Communication apparatus and communication method |
| WO2001091307A1 (en) * | 2000-05-22 | 2001-11-29 | Mitsubishi Denki Kabushiki Kaisha | Communication apparatus and communication method |
| JP2010152745A (ja) * | 2008-12-25 | 2010-07-08 | Nec Corp | ディスクアレイ装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2520551B2 (ja) | 1996-07-31 |
| US5299208A (en) | 1994-03-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2520551B2 (ja) | インタ―リ―ブ式の誤り訂正符号を復号化するための復号器能力強化方法 | |
| EP0136604B1 (en) | Decoding method and system. | |
| US7146553B2 (en) | Error correction improvement for concatenated codes | |
| CN1113475C (zh) | 通过收缩非有效符号提供不等误差保护的编码系统和方法 | |
| US20030079171A1 (en) | Forward error correction | |
| US7802167B1 (en) | Apparatus and method for detecting extended error bursts | |
| US8032812B1 (en) | Error correction decoding methods and apparatus | |
| CN105024706A (zh) | 一种基于bch+rs级联纠错编码方法及系统 | |
| JPH0661872A (ja) | 通信システム | |
| JP2001524274A (ja) | 短縮ファイア符号エラートラッピング復号方法および装置 | |
| CN110492889A (zh) | 检测纠正两位错误的编码解码方法、编码解码器及处理器 | |
| JP3283122B2 (ja) | 符号訂正方法及び装置 | |
| CN112994838A (zh) | 信道编码及译码方法和装置、信息传输系统 | |
| US5809042A (en) | Interleave type error correction method and apparatus | |
| CN107659319B (zh) | 一种对Turbo乘积码编码的方法和装置 | |
| US6961891B2 (en) | High-efficiency error detection and/or correction code | |
| JP3703466B2 (ja) | 積符号を復号するための低コストな方法及び装置 | |
| CN110034847B (zh) | 级联编码方法及装置 | |
| US7181677B1 (en) | System and method for producing data and ECC code words using a high rate restricted-symbol code | |
| US6718505B1 (en) | Method and apparatus for error correction in a process of decoding cross-interleaved Reed-Solomon code (CIRC) | |
| RU2340088C2 (ru) | Способ синдромного декодирования циклического кода (варианты) | |
| JP3252477B2 (ja) | 誤り訂正符復号化方法、誤り訂正符復号化装置、誤り訂正復号化装置 | |
| CN108281160B (zh) | Dvd纠错码的设计方法 | |
| CN120011129B (zh) | 一种非易失性存储器的编码方法和译码方法及相关装置 | |
| JPH10290216A (ja) | 誤り訂正復号方法およびその装置 |