JPS5929016B2 - ランダム誤り訂正装置 - Google Patents

Description

【発明の詳細な説明】 本発明はデジタル伝送路等に生じたランダム誤りを訂正
するランダム誤り訂正装置に関する。

デジタル情報の中に生じた誤りを自動的に訂正する誤り
訂正装置は電子計算機及び通信機器の分野において、そ
の信頼性向上に欠かせない技術として近年のＬＳＩ技術
の進歩に伴ない急速に実用化されつつある。本発明は上
述の誤り訂正装置に係るものであり、とりわけ離散的な
誤りであるランダム誤りを訂正する装置に関するもので
、少ない回路規模で能率的に誤りの伝播を抑圧すること
ができる装置を提供するものである。

誤りを訂正する符号は情報デジットと、この情報デジッ
トとある規則で関係づけられる冗長デジット（パリテイ
検査デジット）から構成される。

パリテイ検査デジットが１つのブロック内でそのブロッ
ク内の情報デジットのみに関係づけられる符号をブロッ
ク符号と呼ぶ。これに対して検査デジットが１つのブロ
ック内の情報に限らず、多数のブロックの情報デジット
と関係づけられる符号をたたみ込み符号という。本発明
は上記のたたみ込み符号を用いたランダム誤り訂正装置
であり、以下本発明を詳細に説明する。

本発明の説明にあたり、たたみ込み符号の基本概念につ
いて説明を施す。

まず、たたみ込み符号をパリテイ検査方程式の集合を満
足する。

と１の２元系列の集合として定義する。ここでパリテイ
検査行列はつぎの形をしているものとする。但し、上記
の行列において斜線部以外はすべて０の要素である。

ＢＯはｂ列で半無限の行をもつ行列で零でない元を有す
る行を有限個だけもつており、最初のｍ行は一次独立で
あるとする。

さらにＢｉをＢＯと同じ次元の行列でＢ。の行をｉ行だ
け下にずらしたものとする。すなわち最初のｉ行はＯで
あり、Ｂｉの（１＋ｊ）番目の行はＢ。の』番目の行と
等しい（ｊ＝１，２，・・・・・・）。このようにして
ｉ＝ｍのパリテイ検査行列ＨはＨ＝〔ＢＯＢｍＢ２ｍ・
・・・・・〕（ｍは整数）で与えられる。

いま符号語Ｘ（半無限の列ベクトル）とするとＸは、
ＨＸ＝０ （２）を満足する。

符号語Ｘはｉ番目の元としてＸｉをもつているとすると
、Ｈの最初のｍ行はＸｌ，・・・，Ｘｂ（このｂデジツ
トをまとめてプロツクと呼ぶ）を定数としてもつｍ個の
線形方程式（パリテイ検査方程式）を定数し、Ｈの最初
のｍ行は一次独立であるから、Ｘの最初のｂデジツトの
中からｂ−ｍデジツトを任意に選べ、また残りのｍデジ
ツトはこのパリテイ検査方程式を解くことにより得られ
る。こうして一度Ｘｌ，・・・・・・，Ｘｂが最初のｍ
個の方程式を満足するようにとられたなら、次のＨのｍ
個の行はさらにｍ個の方程式を未知のＸｂ＋１，・・・
，Ｘ２ｂ（７）ｂ個の元に対して与えることとなり、再
びｂ−ｍ個をこの中から自由に選べることになる。この
手順をｂ個の元をもつ各々のプロツクに対して続ける。
このとき各々のプロツクのｂ−ｍ個の元は任意に選べ、
残りのｍ個の元はパリテイ検査方程式によつて決定され
る。このようにして符号Ｘのすべてのｂ個の元に対して
ｍ個の検査の元が存在し冗長度はｍ／ｂとなる。例えば
Ｂ。

をと定め、ｍ＝１とすると、 Ｈは ＼ ● ● ′とな
る。

符号化されるべき情報系列を１１０１００・・・とする
と最初のパリテイ検査方程式はＸ１＋Ｘ２＝ｏとなり、
ここでＸ１）Ｘ３ツＸ５９ｌ９Ｘ２ｋ＋１を情報ビツト
としておくとＸ１＝１であり、これよりＸ２＝−Ｘ１＝
１が得られ、２番目の方程式は１＋Ｘ３＋Ｘ４＝０とな
る。この過程を続けることにより符号化されたものは１
１１００１１１０１００・・・である。次に、受信符号
はパリテイ検査符号に対する一般的な方法で計算される
シンドロームの検査によつて復号される。

Ｅを誤りパターンのベクトル（誤りの場所においては非
零元をもつている半無限列ベクトル）、Ｙ＝Ｘ＋Ｅを受
信符号であるとするとシンドロームＳはつぎのようにな
る。

このようにＳは誤りデジツトに相当するＨの列の和（Ｍ
Ｏｄ２）の半無限列ベクトルである。

また、受信符号はｂデジツトが同時に復号されると仮定
する。ところで、ある与えられたプロツクのｂデジツト
を復号するとき、全部のシンドロームを見る必要はなく
、そのプロツクが影響を及ぼすシンドロームを見ればよ
い。このようにある一つのプロツクが影響を及ぼすシン
ドロームをＮ′デジツトとし、マに等しいか、またはそ
れより大きく、かつｍで割り切れるような最小数をＮと
すると、１つのプロツクに生じた誤りを考える場合Ｈの
はじめのＮ行（Ｎ／ｍ）ｂ列からつくられた行列が関係
するだけであり、これを短縮パリテイ検査行列ＨＮとい
う。なお、上記のマは非零元を有するＢ。

の最後の行の行番号の値と等しく、またＮ≧マである。
またＢおよびＴについてつぎのように定義する。Ｂ：Ｂ
の行Ｂ。のはじめのＮ行であるＮＸｂ行夕１ｉ）Ｔ：Ｎ
元列ベクトルをｍ行以下にシフトしてはじめのｍ行をＯ
の行とした線形変換を示すＮＸＮ行列。この定義にする
と、ＨＮはＢ，Ｔにより次のように表わされる。

以上、たたみ込み符号についての基本概念を述べた。

次に、上述の誤り訂正たたみ込み符号を用いて構成する
本発明について説明する。

本発明においては、基本パリテイ検査行列として、〜′ で表現される行列Ｇを用いる。

第１図は、上記（６）式で示される基本パリテイ検査行
列として、で表現される基本パリテイ検査行列を用いる
ときの送信側符号器である。

本図において、１は直一並列変換器、２は並一直列変換
器、３はシフトレジスタ、４は法２進加算器である。伝
送されるべき情報信号は直一並列変換器に入力し、シフ
トレジスタ３、法２進加算器４によつて符号化され、さ
らに直一並列変換器２により直列信号として伝送される
。本図における符号器についての符号化手順は以下の如
くである。

まず、直列に入力した３ビツトの情報信号は直一並列変
換器において並列に変換される。そして、第１ビ゛ント
目をシフトレジスタ３により１ビツト分シフトした信号
と第２ビツトの信号との法２進加算が行われ、この法２
進加算の結果を更に１ビツト分シフトした信号と第３ビ
ツトとの法２進加算が行われる。更に、この法２進加算
出力を１ビツト分シフトした信号と現在送信中のパリテ
イ検査ビツトとを法２進加算し、更にその結果を１ビツ
ト分シフトしたものと第１，２，３ビツトの法２進加算
した結果をパリテイ検査ビツトとして出力する。従つて
符号化された直列出力としては、第１〜第３ビツトにパ
リテイ検査ビツトが付加された１プロツクが４ビツトの
信号として出力される。上述の符号化回路は式（７）の
Ｇ４で示される基本パリテイ検査行列に対応するもので
あるが、一般的なＧｂに対しても同様に構成できる。

上述の符号化された信号を復号化するランダム符号復号
器の従来例を第２図に示す。

本図に於いて、２１は直一並列変換器、２２は並一直列
変換器、点線で囲んだ部分Ａはシンドローム計画回路、
Ｂはシンドロームレジスタ、Ｃは誤り訂正のための加算
器である。

シンドローム計算回路Ａにおいて、２３−１〜２３−４
はシフトレジスタで、それぞれ１区切りで示したますに
１ビツト分の信号をレジストするものとする。

２４は法２進加算器を示す。

また、シンドロームレジスタＢにおいて２４は法２進加
算器、２６−１〜２６−４はシフトレジスタ、２７はア
ンド回路であり、誤り訂正回路Ｃにおける２４−１〜２
４−３は法２進加算器である。

ここで、伝送された信号の誤り訂正機能を説明するため
に、直一並列変換器２１に（００１１），（０１００）
，（０１１１），（１０００），（１０１０），（１１
０１），（１１１１），（００１１）の信号が入力した
ときを例にとつて説明する。

尚、上記の信号は実際には直列に入力するものであるが
、直一並列変換器２１によつて４ビツトずつの並列信号
に変換した形で示したものである。いま、上記信号の最
初の４ビツト（００１１）の中で、第３ビツトに伝送路
中で誤りを生じ、（００♂１）となつたとする。

※印がエラー信号を示す。

入力信号はシンドローム計算回路Ａにおけるシフトレジ
スタにレジストされ、法２進加算回路で法２進計算され
てシンドロームレジスタＢに入力し、更に法２進加算計
算及びアンド計算される。

ここで直並列変換器２１の出力が計算された結果、すな
わち第２図のＢにおける信号がシフトレジスタ２３−１
〜２３−４、シフトレジスタ２６−１〜２６−４にレジ
ストされる過程を以下に示す。（直一並列変換器）ｊ さて、上記５） の次の段階で、 シフトレジスタ ２３−３のエラー信号庁は、法２進加算器２４−３に入
力される。

また、シフトレジスタ２６−４の信号と、シフトレジス
タ２６−２の信号はともに１であるのでアンド回路２７
−２の出力は１とな雫？六泳叫≦二叫／＝↓られ、１と
なり出力される。

したがつて誤つてＯとなつた信号は極性が反転して元に
戻り、誤りが訂正されたことになる。このようにして誤
りが訂正されたので、その誤りのシンドロームに対する
影響、すなわちシフトレジスタ２６−２および２６−４
の中の信号１を除くためにアンド回路２７−２の出力が
法２進加算器にフイードバツクされているので、シンド
ロームレジスタが次にシフトされるときには１がＯに変
わり、この誤りの影響が消える。ところが、上述の従来
の構成の復号器においては、伝送路中に誤りが連続して
生じると誤り訂正の能力を越えてしまい、誤りがそのま
ま伝播するという欠点を有している。

このような場合の一例を以下に説明する。いま、直一並
列変換器２１は（００１１），（０１００），（０１１
１），（１０００），（１０１０），（１１０１），（
１１１１），（００１１），（０１０１），（０１１０
），（１０００），（１１００）の信号が入力したとす
る。

そして、最初のプロツクの４ビツト中の第３ビツト目が
誤つて（００客１）、第３番目のプロツクの４ビツト中
の第２ビツト目が誤つて（０♂１１）、第８番目のプロ
ツク４ビツト中の第３ビツト目が誤つて（００客１）と
なつているものと仮定し、前に述べたと同様にシフトレ
ジスタ２３−１〜２３−４、シフトレジスタ２６−１〜
２６−４にレジストされる信号を以下に示す。

ノブ Ｊ０）の段階において、矢印で示したシフトレジスタ２
６−４および２６−２の２つのレジスタにレジストされ
た信号１が結びついてシフトレジスタ２３−３のＯ第１
０の最後のＯが誤つていると見なし、これを誤つて訂正
して１にしてしまう，本発明においてはこの誤り伝播が
抑圧されるものである。

そしてこの誤つた訂正ののち２６−２２６−４のレジス
タの内容はアンド回路２７−２の出力のフイードバツク
によりＯとされるが（１０で示す室がつぎの時点でシン
ドロームレジスタに入力され、これが再び他の誤つた訂
正に結びつく（誤り伝播）可能性がある。すなわち本願
構成においては、第２図に示したシンドロームレジスタ
Ｂの最終段出力に適当な変換を施したのちシンドローム
レジスタの初段入力に帰還してこの誤り伝播を抑圧する
ものである。本発明の一実施例を第３図に示す。

本図において、２４，２５は法２進加算器、３１，３２
はアンド回路、３３はシンドロームレジスタ、３４はフ
リツプフロツプ回路、３５は遅延線であり、点線で囲ん
だ部分Ｂは第２図の点線で囲んだ部分Ｂと同一構成であ
る。フリツプフロツプ回路３４において、Ｓはセツト入
力端子、Ｒはりセツト入力端子、Ｑ，Ｑはそれぞれ出力
端子である。本図における＠，０，７は第２図における
＠，＠，７と対応する。本図の如くの構成をシンドロー
ムレジスタに付加することによつて前に述べた６）の段
階以降のシフトレジスタ（２６−１〜２６−４）のレジ
ス卜される内容が以下に述べるように変化する。

まず、５）の段階では、である。

次の段階で、シフトレジスタ２６−４の出力１がフリツ
プフロツプ３４をセツトし、先の６）でのシンドローム
１は今度はシンドロームレジスタ２６への入力を阻止さ
れる。

従つてこのときのシフトレジスタ２６−１〜２６−４の
状態は次の様になる。となり、訂正不能誤りのシンドロ
ームに対する影響が除かれ、誤りの伝播を抑圧すること
ができる。

以下、次の段階のそれぞれのシフトレジスタの状態を示
す。”ｌ”一゛ となり、シンドロームレジスタ中のパターン（０１０１
）により法２進加算器２４−３で誤り※信号０が１に訂
正されることがわかる。

従つて６）で行つた誤り伝播抑圧以後の誤り訂正機能も
正常に働いていることがわかる。

尚、第３図においてフリツプフロツプ３４に入力するり
セツト信号は、セツト信号に対して一定の遅延時間をも
つ必要がある。

このために遅延線３５及びアンド回路３２を用いて、シ
ンドローム計算回路とフリツプフロツプ回路の出力を一
定時間遅延させた信号とのアンド条件を満足する信号を
りセツト信号としている。以上述べたように、本願発明
によれば、簡単な構成で連続したランダム誤りに対する
誤り伝播を抑圧することができるものである。

【図面の簡単な説明】

第１図はランダム誤り訂正装置の送信側符号器、第２図
は同じく受信側復号器、第３図は本発明による付加回路
の一実施例である。 第２図に於いて、２１は直一並列変換器、２２は並一直
列変換器、Ａはシンドローム計算回路、Ｂはシンドロー
ムレジスタ、Ｃは誤り訂正のための加算器、第３図に於
いて、３１，３２はアンド回路、３３はシンドロームレ
ジスタ、３４はフリツプフロツプ回路、３５は遅延線で
ある。

Claims (1)

1. 【特許請求の範囲】 １ 送信された誤り訂正たたみ込み符号を受信し、該誤
   り訂正たたみ込み符号系列よりシンドロームを計算する
   シンドローム計算回路、該シンドローム計算回路に接続
   され、所要のシンドローム系列を生成するシンドローム
   レジスタを含んでなる復号器を有し、所定の基本パリテ
   イ検査行列に従つて送信された信号中に生じたランダム
   誤りを訂正するランダム誤り訂正装置において、所定長
   を越えるシンドローム系列の“１”が検出されたとき、
   該“１”の信号を該シンドロームレジスタの最終段出力
   として該シンドロームレジスタの初段に帰還することを
   特徴とするランダム誤り訂正装置。 ２ 該シンドロームレジスタの出力をフリップフロップ
   回路のセット入力端子に入力し、該フリップフロップ回
   路のセット信号入力時の出力信号と該シンドローム計算
   回路の出力信号を入力するアンド回路を介して該シンド
   ロームレジスタの初段入力に帰還することを特徴とする
   特許請求の範囲第１項のランダム誤り訂正装置。 ３ 該フリップフロップ回路のリセット入力信号として
   該シンドローム計算回路の出力信号と該フリップフロッ
   プ回路の出力を一定時間遅延させた信号とのアンド条件
   を満足する信号を用いることを特徴とする特許請求の範
   囲第２項のランダム誤り訂正装置。