JPH10510689A

JPH10510689A - 特質データをメインデータのエラーチェック記号にエンコードおよびデコードするデジタル伝送システム

Info

Publication number: JPH10510689A
Application number: JP8518462A
Authority: JP
Inventors: ウォン、ウィン・タク・ケニス
Original assignee: British Telecommunications PLC
Current assignee: British Telecommunications PLC
Priority date: 1994-12-12
Filing date: 1995-12-12
Publication date: 1998-10-13
Also published as: AU687286B2; CA2206688C; US6044482A; WO1996019054A1; EP0797877A1; CA2206688A1; AU4182896A

Abstract

(57)【要約】データは、第１のエラー補正コードによってコード化されて、第１のコード化されたビットを生成する。制御データは、大きな冗長度をもつ第２のエラー補正コードを使用してコード化され、第１のコード化されたビットにモジュロ２加算される。結果が第１のコードにしたがってデコードされるときに、最小のエラーカウントを与えるのがどの第２の有効なコードワードであるかを（受信したコードワードに加えられるとき）確かめることによってデコードを行なう。

Description

【発明の詳細な説明】特質データをメインデータのエラーチェック記号にエンコードおよびデコードするデジタル伝送システム本発明は、フォワードエラー補正を使用するデータ伝送、すなわち冗長（度のある）コードを使用してデータをエンコードし、エラーの存在の下で受信して、エラーが発生していることが受信機で認識できて、好ましくは（最大許容エラー率まで）補正できるようなデータ伝送に関する。とくに記載した内容は、補助データも伝送する必要があり、しかも高レベルのエラー保護を必要とするときのことである。本発明の１つの態様によると、第１の冗長コードにしたがって第１のデータをコード化して第１のコードビットを作り、第２の冗長コードにしたがって第２のデータをコード化して第２のコード化されたビットを作り、さらに第２のコード化されたビットを第１のコード化されたビットに加えることによってコード化されたデータをデコードするための装置であり、第１のコードにしたがって複数のエラー値を決定するために受信したデータに動作する手段であって、各エラー値が第２のコード化されたビットが第２のコードの複数の許可されたコードワードのそれぞれを構成するという仮定に対応するものと、最小のエラー値に対応する前記許可されたコードワードの１つを識別する信号を出力する手段と、受信したデータから識別したコードワードの効果を取除いて、修正したデータを作る手段と、第１の冗長コードにしたがって修正したデータをデコードする手段とを含む装置が提供される。好ましくは、第１のコードは組織（体系）的コードであって、第１のコード化されたビットは第１のデータビットおよびパリティビットを含み、第２のコード化されたビットはパリティビットにのみ付加されており、エラー値を決定するために動作可能な手段が、（ａ）第１のコードにしたがって受信したデータのシンドロームを計算する手段と、（ｂ）このシンドロームを第２の冗長コードの各有効なコードワードと比較する比較手段とを含み、該エラー値はコードワードとシンドロームとの間のハミング距離である。本発明の別の態様によると、伝送のためのデータをコード化する装置であり、伝送される第１のデータを受信し、第１の冗長コードにしたがってデータをコード化して、伝送される第１のコード化されたビットを生成するコード化手段と、伝送される第２のデータを受信し、第２の冗長コードにしたがってデータをコード化して、伝送される第２のコード化されたビットを生成するコード化手段と、第２のコード化されたビットを第１のコード化されたビットに加えるための手段とを具備する装置が提供される。ここで本発明の幾つかの実施形態が、例示的に添付の図面を参照して記載される。図１は、本発明によるデータコード化装置の１形態のブロック図である。図２は、対応するデコーダのブロック図である。この例では、連続する各９６ビットの各データフレームに対して５１データビットを送る要求があることと、これらのビットが（９６、５１）バーストエラー補正巡回コードを使用してコード化されることとを想定している。これは組織的コードであり、すなわちデータビットそれ自身はコード化することによって修正されないままであるので、５１データビットに４５パリティビットを加えて伝送することを要求している。この生成多項式は、Ｘ⁴⁵＋Ｘ⁴⁰＋Ｘ³⁵＋Ｘ²⁵＋Ｘ²⁰＋Ｘ⁵＋１である。このようなコードは、エラー補正技術を使用してデコードすることのように一般的である。したがって図１では、入力１でのユーザデータ入力は、フレーム化（フレーミング）装置２で５１ビットのグループにフォーマット化され、巡回コードのためのコーダ３に供給されて、４５パリティビットを生成する。図示されているように、データおよびパリティビットはレジスタ４でアセンブルされる。明白にするために、図１の装置の内部データパスは、並列接続のように示されているが、所望であれば、標準デジタル信号処理技術を使用して信号をシーケンスで処理することができる。さらに、例えばモデムのような遠隔装置の制御のために補助データを伝送する要求があることと、１１のこのような制御ワードが高いレベルのエラー保護と共に望まれ、伝送エラーが存在するときに受信機でそれらを正確に認識できるようにしていることが想定されている。加えて、既に記載した９６ビットより大きい別の伝送容量は利用できないとする。この装置は、１１の所定の４５ビットの制御ワードの１つを生成して、レジスタ４においてこれらのビットモジュロ２を４５のパリティビットに加えることによってこれを達成する。したがって図１では、入力５は、１組の１１の制御ワードを含むルックアップ表メモリ６でエントリを識別し、選択したエントリは排他的ＯＲゲート７を使用してレジスタ４からの４５パリティビットに結合される。結果として得られる修正されたビットは、別のレジスタ８で５１のデータビットとアセンブルされて、そこから所望のフォーマットで出力９へ出力される。図２には対応する受信機が示されており、ここで信号は入力11で受信され、データおよびパリティビットはレジスタ12の各部分でアセンブルされる。これらのビットはデコーダ13に供給され、同じ（９６、５１）の巡回コードを使用して、エラーを補正し、出力14で補正されたデータを供給する。その表面では、パリティビットにこの余分な情報を加えることによって、受信機が受信したデータ内のエラーを検出し、補正する能力を破壊または少なくとも劣化すると予想することができる。しかしながら、受信機が次の前提条件で動作するとすると、ワードはパリティビットから減算されて、それによってエラー補正があたかも制御ワードがかつて送られてきたことがなかったかのように実行できる。条件は制御ワードが受信したデータとパリティビットの検査から受信機で正しく識別できることである。したがって誤認識によって誤ったコードワードの減算をし、その結果たいていの場合にデータを著しく損なうことになるので、正しい認識が重要である。この危険性を最小にするために、 −制御ワードに対して多数の（組内のワード数に対して）ビットを選択し、また、 −制御ワードは互いに可能な限り異なっているべきである。これは、２つのコードワード間のハミング距離が可能な限り大きくなるように制御コードワードを選択することを意味する。次の表は、２４の２つのコードワード間に最小のハミング距離を有する１１の適切な４５ビットのワードを示している。一般に、ｍビットの制御コードワードに対して、ハミング距離は好ましくはｍ／３であり、理想的には少くともｍ／２である。原則として、制御コードワードは次の（ａ）乃至（ｄ）を行なうことによって認識することができる。（ａ）パリティビットからコードワードを減算する；（ｂ）関係するデコード処理をデータとパリティビットとの和に適用して、エラーとなっているビット数を確かめる；（ｃ）他のコードワードに対して（ａ）および（ｂ）を反復する；（ｄ）最小エラーカウントを与えるコードワードを選択する（伝送エラーがないときは、これはもちろんゼロである）。場合によっては、この処理手順にしたがうことが必要となる。しかしながら、図２の実施形態では、（ｉ）組織的コードワードを使用し、（ii）制御ワードは、パリティビットに対してのみ加えられるので、一層迅速な方法が提案されている。この方法を理解するために、コーディング／デコーディング処理の数学的表現を検討するのが有用である。（ｎ、ｋ）巡回コードで、パリティビットＲ（ｘ）は、生成多項式Ｇ（ｘ）によって除算されたｋ情報ビットの残りである。（組織的コードに対して、Ｄ（ｘ）はここでは、ｎ−ｋによってシフトしたデータを表している。−すなわちｎ− ｋ個のゼロが後続していることに注意すべきである）。したがって、Ｄ（ｘ）＝Ｑ（ｘ）Ｇ（ｘ）＋Ｒ（ｘ） …（１）なお、Ｑ（ｘ）は商であり、“＋”は、ビットごとのモジュロ２の加算である。したがってｎビットのコード化された結果Ｃ（ｘ）は、Ｃ（ｘ）＝Ｄ（ｘ）＋Ｒ（ｘ） …（２）である。デコーダで、受取ったワードがＣ’（ｘ）であると仮定すると、Ｃ’（ｘ）がＧ（ｘ）によって除算されるとき、余りであるシンドロームを計算する。エラーのない条件のもとで、Ｃ’（ｘ）＝Ｃ（ｘ）＝Ｄ（ｘ）＋Ｒ（ｘ） …（３）＝Ｑ（ｘ）Ｇ（ｘ）＋Ｒ（ｘ）＋Ｒ（ｘ） …（４）＝Ｑ（ｘ）Ｇ（ｘ） …（５）したがって、Ｃ’（ｘ）はＧ（ｘ）によって除算することができ、この除算のシンドロームすなわち余りはゼロである。Ｃ’（ｘ）が検出可能なエラーを含むときは、シンドロームはゼロではない。ここで、伝送前に制御ワードをＣ（ｘ）に加えるときの状況を考慮するとし、それをｉ番目の制御ワードをＩ_i（ｘ）であるとする。したがって、式（２）は次のようになる：Ｃ（ｘ）＝Ｄ（ｘ）＋Ｒ（ｘ）＋Ｉ_i（ｘ） …（６）したがって、受信機では、各可能な制御ワードが受信した信号から減算され、またシンドロームが計算されるサーチプロセスが必要である。 S_j(x)＝REM[(C'(X)+I_j(x)/G(x)]j=1…B …（７）なお、Ｂは制御ワード表の大きさ（この例では１１に等しい）であり、所望のワードは、（エラーのない条件のもとで）Ｓ_j（ｘ）はゼロに対するものである。都合悪く、エラーがあるときには、Ｃ’（ｘ）＝Ｃ（ｘ）＋Ｅ（ｘ）であり、式（２）は、 S_j(x)＝REM[(C'(X)+E(x)+I_j(x)/G(x)] …（８）となり、ここでＥ（ｘ）は伝送チャンネルによって導入されるエラーパターンである。これは、ｊ、ｋのある値に対してＥ（ｘ）＋Ｉ_j（ｘ）＝Ｉ_k（ｘ）であるときに誤って認識する危険を表している。この危険は上述のように、制御ワード間のハミング距離を最大にすることによって最小にすることができる。図２のデコーダでは、装置15で制御ワードを減算せずに、シンドロームＳ（ｘ）を装置15で計算する。すなわち、 S(x)＝REM[(C'(X)/G(x)] ＝REM[(D(x)+R(x)+E(x)+I_i)/G(x)] Ｄ（ｘ）＋Ｒ（ｘ）はＧ（ｘ）によって除算することができるので（上記の式３乃至５のように）、Ｓ（ｘ）は実際は、 S(x)=REM[(E(x)+I_i(x)/G(x))]に等しい。Ｅ（ｘ）＝０であるとき、Ｓ（ｘ）＝１であり、そうでないときは、エラー量に応じて、Ｓ（ｘ）は多数のビット位置においてＩｉ（ｘ）と異なるようになる。したがって、シンドロームＳ（ｘ）はコンパレータ16で、制御ワードメモリ17 からの１１の各制御ワードと比較されて、最も短いハミング距離を有するワードを確かめ、このワードＩ_i（ｘ）は、このワードを識別する識別信号ＩＤとー緒に制御信号出力18へ出力される。しかしながらこの最良のハミング距離が９よりも大きいとき（すなわち、３６よりも少ないビットが整合するとき）、コンパレータ16は出力19でアラーム信号ＦＡを生成して、制御ワード認識が信頼できないことを示す。出力制御ワードは、エラー補正回路13によって受信される前に減算器20で受信したパリティビットから減算される。アラーム信号ＦＡが生成されるときは、これはエラー補正回路13の動作を抑制することができるので、データビットは修正されずに出力14を通る（補正されていないデータビットは、破壊されたパリティビットを使用する補正後のデータビットよりも、通常は一層有益である）。また、アラーム信号出力19は、ＩＤ出力 18は使用できないことと、データ出力が出力14で補正されてないことを後段の装置に信号で知らせることができる。制御ワードを誤認識した場合、例えばＩ_j（ｘ）の代わりにＩ_i（ｘ）を想定した場合、パターンＩ_i（ｘ）乃至Ｉ_j（ｘ）によってシンドロームは破壊される。試験中に、記載した特定のコードおよび制御ワードを使用して、チャンネルエラー率が高くても不正確な制御ワード認識が生じない（すなわち、誤った検出の全てがアラーム信号によって識別される）ことが分かった。しかしながら、（チャンネルエラー数が、使用中のコードを補正できる範囲内にあると仮定すると）、シンドロームの幾つかの値がパリティビットのみのエラーに対応し、一方で他の値がデータエラーに対応していることが判明した。したがって、（すべてのｉ、ｊに対して）Ｉ_i（ｘ）＋Ｉ_j（ｘ）のもたらす効果がパリティビットのエラーのみをシミュレートするように制御ワードを選択できるので、制御ワードの誤認識を検出しなかったために、−少なくとも幾つかのエラーパターンに対して、データが損なわれることはない。しかしながら、この方法による制御ワードの選択は、制御ワード間のハミング距離を減少するので、誤認識が検出されない危険性が増加する。明白に、これらの２つの要素間ではトレードオフが存在する。

【手続補正書】特許法第１８４条の８第１項【提出日】１９９６年１０月３１日【補正内容】請求の範囲１．複数の許可されたコードワードを有する第１の冗長コードにしたがって第１のデータをコード化して第１のコード化ビットを作り、より少ない数の許可されたコードワードを有する第２の冗長コードにしたがって第２のデータをコード化して第２のコード化されたビットを作り、さらに第２のコード化されたビットを第１のコード化されたビットに加えることによってコード化されたデータをデコードするための装置であり、第１のコードにしたがって複数のエラー値を決定するために受信したデータに対して動作する手段（15,16,17）であって、各エラー値が第２のコード化されたビットが第２のコードの複数の許可されたコードワードのそれぞれを構成するという仮定に対応するものと、最小のエラー値に対応する前記許可されたコードワードの１つを識別する信号を出力する手段（16）と、受信したデータから識別したコードワードの効果を取除いて、修正したデータを生成するために前記出力信号によって制御される手段（20）と、第１の冗長コードにしたがって修正したデータをデコードする手段（13）とを含む装置。２．第１のコードが組織的コードであり、第１のコード化されたビットが第１のビットおよびパリティビットを含み、第２のコード化されたビットがパリティビットにのみ付加され、エラー値を決定するように動作することができる手段が、（ａ）第１のコードにしたがって受信したデータのシンドロームを計算する手段（15）と、（ｂ）このシンドロームを第２の冗長コードの各有効なコードワードと比較する比較手段（16）とを具備し、エラー値がコードワードとシンドロームとの間のハミング距離である請求項１記載の装置。３．最小のハミング距離が所定の閾値よりも大きいときに、比較手段がアラーム信号を生成するように動作することができる請求項２記載の装置。４．デコード手段（13）がアラーム信号の存在に応答して、エラー補正を抑制する請求項３記載の装置。

Claims

【特許請求の範囲】１．第１の冗長コードにしたがって第１のデータをコード化して第１のコード化ビットを作り、第２の冗長コードにしたがって第２のデータをコード化して第２のコード化されたビットを作り、さらに第２のコード化されたビットを第１のコード化されたビットに加えることによってコード化されたデータをデコードするための装置であり、第１のコードにしたがって複数のエラー値を決定するために受信したデータに対して動作する手段（15,16,17）であって、各エラー値が第２のコード化されたビットが第２のコードの複数の許可されたコードワードのそれぞれを構成するという仮定に対応するものと、最小のエラー値に対応する前記許可されたコードワードの１つを識別する信号を出力する手段（16）と、受信したデータから識別されたコードワードを取除いて、変更したデータを生成する手段（９）と、第１の冗長コードにしたがって修正したデータをデコードする手段（13）とを含む装置。２．第１のコードが組織的コードであり、第１のコード化されたビットが第１のビットおよびパリティビットを含み、第２のコード化されたビットがパリティビットにのみ付加され、エラー値を決定するように動作することができる手段が、（ａ）第１のコードにしたがって受信したデータのシンドロームを計算する手段（15）と、（ｂ）このシンドロームを第２の冗長コードの各有効なコードワードと比較する比較手段（16）とを具備し、エラー値がコードワードとシンドロームとの間のハミング距離である請求項１記載の装置。３．最小のハミング距離が所定の閾値よりも大きいときに、比較手段がアラーム信号を生成するように動作することができる請求項２記載の装置。４．デコード手段（13）がアラーム信号の存在に応答して、エラー補正を抑制する請求項３記載の装置。５．第１の冗長コードにしたがってデータを伝送し、コード化する第１のデータを受信して、伝送のために第１のコード化されたビットを生成するコーディング手段（３）と、第２の冗長コードにしたがってデータを伝送し、コード化する第２のデータを受信して、伝送のために第２のコード化されたビットを生成するコーディング手段（６）と、第２のコード化されたビットを第１のコード化されたビットに付加する手段（７）とを含むコード化データを伝送する装置。６．第１の冗長コードが組織的コードであるので、第１のコード化されたビットが第１のデータおよびパリティビットを含み、付加手段（７）が第２のコード化されたビットにのみパリティビットを付加するようにされている請求項５記載の装置。７．第１のコードが巡回コードである請求項６記載の装置。８．第２のコードがｎビットを生成し、その２つの有効なコードワード間のハミング距離が少くともｎ／３である請求項５乃至７の何れか１項記載の装置。