JPS58171145A

JPS58171145A - 復号化装置

Info

Publication number: JPS58171145A
Application number: JP5421782A
Authority: JP
Inventors: Shigeyuki Kawarabayashi; 河原林　成行; Toru Inoue; 徹井上; Yasuo Sugiyama; 杉山　康夫; Sadanobu Ishida; 禎宣石田; Takeshi Onishi; 健大西; Masayuki Ishida; 雅之石田; Hiroshi Sugano; 宏菅野
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1982-04-01
Filing date: 1982-04-01
Publication date: 1983-10-07

Abstract

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

Description

【発明の詳細な説明】本発明はディジタル清報の復号化装置に係り。

特にディジタル情報の誤り訂正機能および誤り検出機能
をもつ符号の復号化装置の改良に関するものである。

従来この種の装置として矛１図、牙２図、矛３図、第１
４図および第５図に示すものがあった。

矛１図において（１）は復号化装置への入力端子。

（２）は矛ｌの復号器（以後Ｃ１復号器と呼ぶ）　、　
ｆ３＋はデ・インターリーブ回路（遅延回路）、（４）
は矛２の復号器（以後Ｃ１復号器と呼ぶ）　、　（５ａ
）、（５ｂ）はそれぞれ復号化装置のフラグ（検出情報
）とデータの出力端子である。

矛２図はＣ１復号器の構成図を示したものであり１図中
、（６）は上記Ｃ１復号器の出力端子、（７）は記憶回
路、（８）は誤り訂正回路、（９）はシンドローム演算
回路、ｕＯ）は誤りなし検出回路、　ｕｌｌは１重誤り
であることを検出する回路、α力は１１誤りの位置と大
きさを演算する回路、（１３１は上記回路を制御する制
御回路である。

矛３図は従来の０２復号器の構成図を示したものであり
１図に８いて圓はＣ２復号器への入力端子、０５）は人
力データの記憶回路、ｕＯ）は誤り訂正回路、ａηはシ
ンドローム演算回路・０８１は誤りなし検出回路、ｕ９
）は１　ｆｉＬ””誤りを検出する回路、ｔ２［１は１
重誤りの位置と大きさを演算する回路、　＋２１１はフ
ラグを発生する回路、囚は上記各回路を制御する制御回
路である。

矛４図は従来のＣ１復号器の復号動作の７０−チャート
であり、矛５図は従来のＣ２復号器の復号動作のフロー
チャートである。

次に動作について矛１図、矛２図、矛３図。

矛４図８よび矛５図を参照しながら説明する。

符号Ｃ１，Ｃ，としてはガロア体ＵＦ（２’）上におけ
る（３２．２８．５　）リード・ンロモン符号ｇよび（
２８゜２４、５　）　リード・ンロモン符号をそれぞれ
用いた場合を例にとって説明する。Ｃ１復号器、Ｃ２復
号器ではそれぞれＣ，、Ｃ２を復号する。内符号とも最
小距ＡＩｔｔは５であるので２シンボル誤り（ｌシンボ
ルは８ビツトで朽成される）まで訂正可能であるが、見
逃し誤りとなる割合を減じるためにｃｌ、　Ｃ，復号器
ではいずれも１シンボル誤りのみ訂正するものとする。

通信路あるいは磁気記録その他の記録媒体において誤り
が混入したデータ３２シンボルが入力端子（１）からＣ
１復号器（２）へ人力する。Ｃ１復号器（２）では、入
力データ３２シンボルのうち１シンボル誤りがあれはこ
れを訂正して情報部２８シンボル（３２シンボルのうち
、２８シンボルが情報部、４シンボルが検査部である）
を出力し、それ以外の場合には入力データ３２シンボル
のうち情報部２８シンボルをそのままデ・インターリー
ブ回路（遅延間１ｇ　）　ｆ３＋へ出力する。デ・イン
ターリーブ回路（３）では各シンボルが遅延され、バー
スト誤りはランダム誤りに変換される。

Ｃ２復号器（４）では入力データ２８シンボルのうちｌ
シンボル誤りがあればこれを訂正し、情報部２４　　シ
ンボルを出力し、それ以外の場合には入力データ２８シ
ンボルのうち情報部２４シンボルをそのまま出力端子（
５ｂ）へ出力する。ただし。

ｌシンボル誤り以外の誤りが検出された場合には入力デ
ータに対応してフラグ発生回路ｆ２１１でフラグを付加
して出力端子（５ａ）より出力する。

次にＣ１復号器（２＋　０）復号動作について矛２図に
よび矛４図を参照しながら詳細に説明する。

人力データ３２シンボル（２８シンボルガ情報ｅ。

残り４シンボルが検査部である）が入力端子＋１１より
人力し、ａピ憶回路（７）とシンドローム演算回路（９
）へ入力する。シンドローム演算回路（９）では上記３
２シンボルｒ＝＝　（ｒｏ＋　ｒｌ＋　ｒ２．　＋＋＋＋°、　ｒ
ｓ＋ｌ　°曲−−聞“°四−−°°（１１によって次式
のとおりシンドロームＳ。ｌｓ、　ｐＳ２，８３　ヲＲ
７Ｊする。

Ｓｏ”、Σｒｉ・・−・・・・・・・・・・・・・・・
・・・・・−曲・・・・・・曲・・曲間・・−・・　ｆ
２１３０Ｓ＋＝、Σｒｉ・αゴー・・・・・・・・・・・・・・
・・・・・卯・・・・曲間・・・・・・・・・　（３１
−０８２＝　Σｒｉ・（αす２・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・開・・川・　（
４１−ＯＳ、＝、Σｒｉ・（αす３・・・・・・・曲間曲・・・
・・・・曲・・・・四・・・・　（５）＋＝０但し。

ｒｉＥ（０，Ｃ１）（０≦１≦３１，０≦ｉ≦２５４１
−・−・−−（６）Ｓｋ　Ｅ　（０，α！）（０≦に≦
３．０≦夏≦２５４）・・・・・・・・−・・・　（７
）であり、（２）式、（３）式、（４）式および（５）
式に８ける和は２を法とする。αはガロア体Ｇｋ’（２
”）上の根である。

上記シンドローム８ｇ＋　ｓｌ、　Ｓ　２＋　８３　（
Ｅ（０，Ｕ’　）（０≦ｉ≦２５４１１を入力として、
誤りなし検出回路Ｕαでは、シンドロームＳ。、Ｓ□、
Ｓ２．Ｓ、が丁べて０かどうかを判定する。シンドロー
ムＳＵ＋ＳＬ＋８２、　Ｓ３がすべて０であれば、誤り
が発生していなかったと判定し、そうでなけれは、１重
以上の誤りが発生していたと判定する。

誤りなし検出回路（１４１１で、誤りが発生していなか
ったと判定した場合には、誤りＫＪ正回路＋８１では訂
正動作なせずに記憶回路（７）から人力データ３２ンン
ボルのうち情報部２８シンボルをそのまま出力端子（６
）へ出力する。

誤りなし検出回路ｕｌＪで、１車以上の誤りが発生して
いたと判定した場合には、１車勝り検出回路（Ｉｌｌで
１重誤りかどうかを利足する動作をおこなう。シンドロ
ーム８０１８１　＋　８３＋　８３を入力として、１に
誤り検出回路αＤでは。

８ｕ”ｅＯ，Ｓ１’？０．８２”ＦＯ、Ｓ３”ＦＯ力）
つ８ｘ７Ｓｏ＝８２／５ｘ＝Ｓ３／Ｓｔが満足されているかどうかを判定する。上記の条件が満
足されていれは、１重誤りが発生していたと判定する。

上記の条件が満足されていなければ、２車以上の誤りが
発生していたとｆ（ＩＶ１重誤り検出回路０１１で１東
誤りが発生していたと判定した場合には、１東誤りの位
置と大きさの演算回路＠で誤りの位置α８（α、Ｅ（α
ｉ）、０≦ｉ≦３１１と大きさ、ｅｘ（ｅｘＥ（Ｃ１）
、０≦ｉ≦２５４）をαウーＳｓ力０・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
−・・・・・・・・・・・・・・・・・　（８）ｅｚ＝
８６　・・・・・・・・−・・・・・・・・・・・・・
・・・・・・・・・・−曲・・・・・・・・・・・・・
・曲−＋９１と演算する（演算はいずれもガロア体にお
ける演算である）。Ｃｘｄ号器（２）への人力データ３
２シンボルと誤りパターンを多項式で表現するとそれぞ
れｒｌＸｌ　＝＝、Σｏｒ、・Ｘト・・・・・・・・・・
・・叩曲・・・・叩・・聞・曲・・　ｏＯ）ｅ（Ｘ）＝
ｅｘ−Ｘｘ・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・−・・・・・・
・・・　０ｖと皆けるから誤り訂正回路（８）ではＣ（Ｘｌ含ΣＣｉＸ’＝ｒ（Ｘ）（ｉｅｔＸ）　＋・＋
＋Ｈ１ｌＨ＋＋−・・・・・　αり＋＝０但し。

ＣＩＥ（０，α；）、（ｏ≦ｊ≦２５４）によって誤り
を訂正しく■は２を法とする）Ｊ＋］算である）、出力
端子（５ｂ）へ清＠ｉ部２８シンボルを出力する。

１重誤り検出回路αＤで、２重以上の誤りが発生してい
たと判定した場合には、誤り訂正回路（８）で誤り訂正
動作をせずに、入力データ３２シンボルのうち情報部２
８シンボルをそのまま出力端子（６）へ出力する。

以上Ｃ二よって、入力端子（１）より人力された３２シ
ンボルのデータに対するＣ１傷号器の復号動作が終ｒす
る。

さらシニ、Ｃ２復号器（４１の動作については矛３図の
Ｃ２復号器の構成図Ｓよび矛５図の動作フローチャート
を参照しなか、ら説明する。

上記Ｃ２復号器の入力端子圓より２８シンボル（２４シ
ンボルが情報部であり、残りの４シンボルが検査部であ
る）のデータが人力し、記憶回路１５１とシンドローム
演算回路σ７）へ人力する。

シンドローム演算回ｇａｒ＋では上記２８シンボル１ｒ
＝Ｌｒｏ＋　ｒｌ＋　ｒ２．・・・、　ｒ２７１　・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・−・・　（１３１を用いてＳｏ＝　Σｒ１・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・叩・　４１４１−０８ｔ＝、Σｒｉ・α墓・・・・・・・・・・曲・・・・
・・・・・・・曲・聞・・・・・・・・・・・・・・　
αω−０７Ｓ２＝　Σｒｉ・（αｉ１２　・・・・・・・・・曲・
・・・・・・・・曲・曲・・開開・　（１６）−ＯＳ、二、Σｒ・（αｉｌｌ　・・・・・−・曲−・・・
・・・・・・・・・・・・・・・開開−・・　０η、−
０１によってシンドローム８０１８１１８２１８ｇを計算す
る。ここで。

ｒ、Ｅ（（）１ａｉｌｌＯ≦ｉ≦２７．０≦１≦２５４
１−・−−−−−−−−−・−（１８）であり、αはカ
ロア体０Ｆ（２”）上の根である。

上記シンドローム５Ｌ１１８１．８２１　ｓ、ＩＥ（ｏ
、Ｃ１）。

（０≦≦ｚ５４１１　全人力とシテ、誤すナシ検出ｌ！
ｌ！１ｖｌｒｕ８）では、シンドロームＳｏｎ　８１　
＋　８２１８Ｂが丁べて０かどうかを判定する。シンド
ロームＳｏ、　Ｓｓ、　８２．Ｓｍがすべて０であれば
、誤りが発生していなかったと判定し、そうでなければ
、１重以上の誤りが発１していたと判定する。

誤りなし検出回路ｕ８Ｉで誤りが発生していなかったと
判定した場合には、誤り訂正回路ｔ１６Ｉでは訂正動作
なせずに、記憶回路αωから入力データ２８シンボルの
うち情報ｓ２４シンボルをそのまま出力端子（５ｂ）へ
出力する。同時に、フラグ発生回路（２１１でそのブロ
ック（ｌブロックは２４シンボルで構成される）に対応
したフラグな０にリセットして出力端子（５ａ）へ出力
する。

誤りなし検出回路０８１で１重以上の誤りが発生してい
たと判定した場合には、１重誤り検出回路ａωで１重誤
りかどうかを判定する動作をおこなう。１重誤り検出回
路α９ではシンドロームＳ　Ｏ＋Ｓ！、　８２．　Ｓｍ
を入力としてＳｏ＼０＋８１＼０．Ｓ２＼０．８　ｓ　ＮＯＯ１９ｓｔ／８０−８２／Ｓ１＝Ｓｍ／８２が満足されているかどうかを判定する。上記の条件が満
足されていれば、１重誤りが発生していたと判定する。

上記の条件が満足されていなければ、２重以上の誤りが
発生していたと判定する。

１重誤り検出回路１９１で１重誤りが発生していたと判
定した場合には、１重誤りの位置と大きさの演算回路□
□□で１重誤りの位置α８と大きさｅｘを０１復号器と
同様Ｋ（８）式および（９）式で計算する。

Ｃ２復号器（４）への入力データ２８シンボルおよび誤
りパターンを多項式で表現するとそれぞれｅ　（Ｘｉ　
＝　ｅｘＸＸ・・・−・・・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
−・・　■と書けるので誤り訂正回路（１６）ではによ
って誤りを訂正しく■は２を法とする加算である）、情
報部２４シンボルを出力端子（５ｂ）へ出力する。

と同時にフラグ発生回路１２Ｄでそのブロックに対応し
たフラグをリセットして出力端子（５ａ）へ出力する。

１重誤り検出回路ａ印で、２重以上の誤りが発生してい
たと判定した場合には、誤り訂正回路（１Ｇ＋で誤り訂
正動作をせずに、入力データ２８シンボルのうち情報部
２４シンボルをそのまま出力端子（５ｂ）へ出力する。

同時にフラグ発生回路Ｃ２１１では、訂正不能な誤りが
検出されたとしてそのブロックに対応したフラグをセッ
ト（ｌにセット）して出力端子（ｓｂ）へ出力する。

このようにして入力端子−より入力された２８シンボル
のデータに対するＣ２復号器の復号動作が終了する。

以上に示されたＣ１復号器、Ｃ２復号器の動作によって
、入力端子（１）より入力した３２シンボルのデータと
デ・インタリーブされた２８シンボルのデータの復号が
終了し、所望の情報部２４シンボルが得られる。このよ
うな復号動作を繰り返して次々とすべての入力データを
復号する。

従来の復号化装置は以上のように構成されているので、
Ｃ１復号器で誤りを見逃すのは通信路あるいは記録媒体
等で２シンボル以上の誤りが生じた場合であるからＣ２
復号器で誤りを検出する確率のオーダーはＰｓ’（Ｐｓ
は通信路あるいは記録媒体等におけるシンボル誤り率で
ある）に比例し、誤りを見逃す確率のオーダーはＰｓ”
に比例する。このように従来の復号化装置は二重に構成
されているにもかかわらず誤りを検出する確率あるいは
誤りを見逃す確率があまり改善されないという欠点がめ
った。

本発明は上記のような従来のものの欠点を除去するため
になされたもので、上記Ｃ１復号器において誤り検出情
報を消失とし、上ＨｅＣ２復号器における復号の際上記
消失情報を利用することにより、誤りを検出する確率お
よび誤りを見逃す確率を改善できる復号化装置を提供す
ることを目的としている。

以下、この発明の一実施例を図について説明する。第６
図において（１）は復号化装置への入力端子、（２３１
はガロア体ＧＦ（２”ｌ上におけるＣ１符号（ガロア体
ＧＦ　（２８１上における（　３２．２８．５１リード
・ソロモン符号）を復号するためのＣｘ復号器、Ｈはフ
ラグとデータとをデ・インターリーブするデ・インター
リーブ回路、□□□はＣ２符号（ガロア体ＧＦ　＋２”
ｌ上における（２８．２４．５１リード・ソロモン符号
）を復号するためのＣ２復号器、　＋５ａｌはＣ２復号
器からのフラグ（０２フラグ）の出力端子。

（５ｂ）はＣ２復号器からの復号データの出力端子であ
る。

第７図は上記Ｃ１復号器の構成例を示したものであり９
図において□□□は入力端子はｊより入力した復号化す
るデータを記憶する記憶回路、縮はシンドローム演算回
路、＠は誤りなし検出回路。

（３ｏ）′＃よ１重誤りを検出する回路、　（３１１は
１重誤りの位置と大きさを演算する回路、弼は２重誤り
を検出する回路、（３３１は２重誤りの位置と大きさを
演算する回路、（財）は１重誤りおよび２重誤りを訂正
する回路、　ｃＪＳｌは２重以上の誤りのときにフラグ
をたてるフラグ発生回路、＋３６）は上記各回路を制御
する制御回路、　（２６ａｌはフラグ（Ｃエフラグ）の
出力端子であり、　＋２６ｂｌは復号データの出力端子
である。

第８図は上記Ｃ２復号器の構成例を示したものであり９
図において（３７ａｌはフラグ（Ｃｉミツラグの入力端
子、　＋３７ｂｌはデータ（２８シンボルを１ブロツク
とする）の入力端子１時はフラグのたっているシンボル
の位置と個数を記憶し、０２フラグを発生する記憶回路
、＠は入力端子（３７ｂｌより入力した復号化するデー
タを記憶する記憶回路、　（［はシンドローム演算回路
、　＋４１１は誤りなし検出回りの位置と大きさを演算
する回路、　＋４４１は２重誤りを検出する回路、　１
４５＋は２重誤りの位置と大きさの演算回路、　（４６
１は誤り訂正回路、　ｆｔ？）は２重誤りが検出された
ときにその誤りの位置にフラグが付いているかどうかを
判定する比較回路であり、（機はフラグ発生回路、（４
９は３重消失の大きさ演算回路、Ｃ５０＋は３重消失と
して訂正されたデータなで旦記憶する記憶回路、（５υ
は３重消失訂正動作の確認回路、（５２）は上記各回路
を制御する制御回路である。

第９図は本発明による上記Ｃ１復号器の復号動作のフロ
ーチャートであり、第１Ｏ図は本発明による上記Ｃ２復
号器の復号動作のフローチャートである。

次に動作について第６図、第７図、第８図。

＠９図および第１Ｏ図を参照しながら説明する。

符号Ｃ１，Ｃ２としては前述のようにガロア体ＧＦ　（
２”ｌ上における＋３２．２８．５＋　リード・ソロモ
ン符号および（２８，２４，５１１Ｊ−ド・ソロモン符
号を用いた場合を例にとって説明する。符号Ｃ１，Ｃ２
とも最小距離αは５であるのでＣ１復号器では１重誤り
および２重誤りは訂正するものとし、２重以上の誤りを
検出した場合にはそのブロックに消失情報（フラグ）を
付加する１２重誤りの場合は誤りを訂正しかつフラグを
付４加する）。Ｃ２復号器では上記消失情報を用いてＣ
，復号器で見逃されたＮｅ個以下の誤りと上記消失情報
の付加されたＮｘｉ固以下の誤りが訂正され、訂正能力
を超える誤りのうち検出できるものにはそのブロックに
フラグを付加し、Ｃ２復号器における検出情報とする。

ただし、Ｎｅ、Ｎｘは２　（Ｎｘ＋Ｎｅｔ　＋１≦５・・・・・・・・・・・
・・・−・・・・・・・・・・・・・・・・・・・・・
・・　＠を満足する整数であり６本発明においてはＮｘ
。

Ｎｅの組み合せとしては（１）　Ｎｘ＝２．Ｎｅ＝０１消失情報の付加された２
個以下の誤りを訂正する）（ｉｉＪ　Ｎｘ＝１．Ｎｅ＝＝１　（消失情報の付加さ
れたｉ＋ｉの誤りとＣ１復号器で見逃された１個の誤り
を訂正する）（Ｉｉｉ）　Ｎｘ＝０．Ｎｅ＝２　（Ｃ１復号器で見逃
された２個以下の誤りを訂正する）について考える。

まず＋Ｃ１復号器内の動作について説明する。

入力端子（υより３２シンボル（２８シンボルが情報部
であり、残りの４シンボルが検査部である）の１ブロツ
クのデータが入力し、記憶回路−とシンドローム演算回
路（２）へ入力する。シンドローム演算回路（支）では
上記３２シンボル）ｒ　＝＝；（ｒｏ、ｒｒ＋　ｒ２°
１°＋’ｌｏ、’ｌｌｌ　＋＋＋＋＋＋＋＋ｌｌ＋＋＋
＋＋＋＋＋＋＋°Ｅｌｌ罠よって１次式のとおりシンド
ローム５ＬＳ１＋８ｘ、Ｓ＝を計算する。

Ｓ０＝Σｒ１・・−・・・−・−・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・−・・・・・　（至）ｍＯ１Ｓ０＝Σｒ１・αｉ・・・・・・・・・・・−・・−・
・・・・・・・・・・・・−・・・・・・・・・・−・
・・・・・　（２５）−〇Ｓ２−Σｒｉ・（Ｃ１）２・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・　団）１雪Ｏ８，＝　ΣｒＨ・（α１戸・−・・・・・・・・・・・
・・・・・・・−・・・・・・・・・・・・・・・・・
・・・　万−０但し。

ｒｉ　ｇ　（０，Ｃ１）（０≦１≦３１，０≦ｊ≦２５
４）・・・・・・・・−・・・　（ハ）８１（０，αｒ
）　Ｃｏ≦に≦３．０≦；≦２５４）・・・・・・・・
−・・・・・　（支）であり、αはガロア体ＧＦ（２８
１上の根である。

上５己シンドロームＳｏ、　Ｓｔ、　８２．８８　（Ｆ
ｉ　（０，αｉｌ　（０≦ｉ≦２５４１１を入力として
、誤りなし検出回路（支）では、シンドローム８０．Ｓ
ｌ、　８２．　Ｓ−がすべて０かどうかを判定する。シ
ンドロームＳＯ＋　８１＋　８２＋　８ｓがすべてＯで
あれば誤りが発生していなかったと判定し、そうでなけ
れば１重以上の誤りが発生していたと判定する。

誤りなし検出回路（支）で、誤りが発生していなかった
と判定した場合には、誤り訂正回路図では訂正動作なせ
ずに記憶回路□□□から入力データ３２シンボルのうち
情報部２８シンボルをそのまま出力端子＋２６ｂｌへ出
力する。

誤りなし検出回路（２）で１重以上の誤りが発生してい
たと判定した場合には、１重誤り検出回路側で１重誤り
かどうかを判定する動作をおこなう。シンドローム８Ｇ
、Ｓｌ、Ｓ２．Ｓ、を入力として。

１重誤り検出回路（至）では８０＼０．Ｓ１＼０．Ｓ２＼０．Ｓ、＼０カ１つＳ＋／Ｓｏ　＝８２／Ｓ　１　＝８−／８２が満足され
ているかどうかを判定する。上記の条件が満足されてい
れば、１重誤りが発生していたと判定する。

１重誤り検出回路（３０）で１重誤りが発生していたと
判定した場合には、１重誤りの位置と大きさの演算回路
−で（８）式および（９）式によって誤りの位置αＸと
大きさｅｘを計算する。但し、ｅｘＥ（αす、（ｏ≦ｉ
≦３１１であり、ｅｘＥ（α’１１（０≦ｉ≦２５４）
である。Ｃ，復号器（２）への入力データ３２シンボル
および誤りパターンを多項式で表現するとそれぞれｒ（Ｘｌ”＝ΣｒｉＸｉ・・・・・・・・・・・・・−
・・・・・・・・−・・・・・・・・・・・・・・・・
・　（至）トＯｅ　（Ｘｉ　＝　ｅｘＸＸ・・・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
−・・・・・・・・　３１１と書けるから、誤り訂正回
路（財）ではＣ（Ｘ１分ΣＣ＋）（ｉ＝ｒｌＸｌ■ｅ（
ＸＩ・・・・・・・・・・・・・・・・・・　国−〇によって誤りを訂正しく■は２を法とする加算である）
・情報部２８シンボルを出力端子（２６ｂ）へ出力する
。同時にフラグ発生回路□□□では上記あシンボルに対
応したフラグをリセットして出力端子（２６ａ）へ出力
する◎ ２重誤り検出回路図で２亀誤りが検出された場合には２
重誤りの位置と大きさの演算回路（２）で例えば下記の
ように位置αＸ−αｙ（Ｃ８，αｙＥ（αす。

０≦ｉ≦３１１と大きさｅｘ、ｅｙｌｅｘ、ｅｙＦ３（
αＱ、０≦６２５４１を算出する。

位置ｎｚ　、ｅｙについては例えはチーンサーチ（Ｃｈ
ｉｅｎ　５ｅａｒｃｈ）と呼ばｔＬ　ル方法（：　ヨッ
”ｃなるｆ　（ＸｌへαＯ１αｌ、α２・・・、α＄１
を代入していってｆ（Ｘｌ＝０・・・・・・・・・・・
・・・・・・・・−・・・・・・・・・・・・・・・−
・・・・・・・・・・・・・・・・・・・・　（財）を
満足する２＠αＸ、ｅｙを求める。上記２根αＸα、が
求まったとき、２重誤りが検出され々とじてもよい。上
記２根α１ｑ、アが求まればｅｙ　＝＝　８６　＋　ｅ
ｘ　　・・・・・・・・・・・・−・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・（至）によって大きさｅｚｇｅｙが求められる
　（演算はいずれもガロア体における演算）。

Ｃ１復号器（ハ）への入力データ３２シンボルおよび誤
りパターンを多項式で表視するとｒ’Ｘ）””　；Ｚｏ　ｒ　ｉＸ’　　・・・・・・・
・・・・・・・・・・・・・・・・−・・・・・・・・
・・・中　　（ｅ（Ｘｌ＝　ｅｚＸＸ＋ｅｙＸＹ・・・
・・・・・−・・・・・・・・・・・・・・・・・・・
・・・・・・・・　（至）と書けるので、誤り訂正回路
例ではｃ＋ｘｔ傘、ｚｏＣ，ｘｔ＝ｒ（Ｘｌ■ｅ　（Ｘ）・・・・・・・・・・・・・・
−・・・・・・・・・・・・・・・・・・・・　（至）
によって誤り訂正しく■は２を法とする加算である）、
情報部２８シンボルを出力端子（２６ｂ）へ出力する。

と同時にこの場合にはフラグ発生回路（へ）では上記２
８シンボルに対してフラグをたて出力端子（２６ａ）へ
出力する。

最後に、シンドロームＳｏｎ　８１＋　８２．Ｓａのう
ち０でないものが少なくとも１つありかつ１重誤りでも
２本誤りでもない場合には誤り訂正回路（至）では誤り
訂正動作なせず、情報部２８シンボルをそのまま出力端
子（２６ｂ）へ出力し、同時にフラグ発生回路（ト）で
は打止不能な誤りが検出されたとして上記２８シンボル
に対応してフラグ（Ｃｌフラグ）をたて消失情報として
出力端子（２６ａ％出力する。

以上のようにしてＣ１復号器（２）で３２シンボルデー
タから情報部２８シンボルが復号され、同時に消失情報
も付加される。

このようにＣ１復号器（２）で復号されたデータはデ・
インターリーブ回路（至）へ人力し、ここで各シンボル
が遅延され、バースト誤りはランダム誤りに変換される
。

最後にＣ２復号器（ハ）の動作について説明する。

入力端子（３７ａ）よりＣ１復号器で得た消失情報（Ｃ
ｌフラグ）が入力し、Ｃ１フラグがたっている位置とそ
の開数が記憶回路間へ入力される。入力端子（３７ｂ）
よりデ・インターリーブされた銘シンボル（２４シンボ
ルが情報部であり、残り４シンボルが検査部である）を
１ブロツクとするデータが入力し、記憶回路３９）とシ
ンドローム演算回路（軸へ入力する。

シンドローム演算回路（幻では上記２８シンボル１ｒ−
＝　（ｒＣｈ　ｒｌ＊　ｒｚ、・・・、　ｒｚ７）・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・　　（ａによって１次式のとおりシンドロ
ームＳ。、Ｓｌ。

８２　ｅ　８３を計算する＠８ｏ＝　Σ　ｒｌ・・・・・・・・・・・・・・−・・
・・・・・・・・−・・・・・・・・・・・・・・・・
・・・・・・・・　＋４１１−Ｏ８！＝　Σ　ｒｉ・α冨・・・・・・・・・・・・・・
・・・・・・・・・・・・−・・・・・・・・・・・・
・・・・・・　（４ｚｉ＝Ｏ８２＝、Σ　ｒｉ・（αす２　・・・・・・・・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・
・・・　　（４３１鳳−０但し。

ｒＨＥ　（０，α！ｌ　（０≦ｉ≦２７．０≦ｊ≦２５
４）８ｋＢ（０，αｊ）（０≦に≦３．０≦ｉ≦２５４
）であり、αはガロア体ＧＦ（２”）上の根である。

上記シンドローム８ｏ、　ｓｌ、　ｓ、、　５３（Ｅｏ
ｏ、αｉｌ。

（Ｏ≦ｉ≦２５４）ｌを人力として、誤りなし検出回路
１１１ではシンドロームＳｏ、８１．８ｚ、Ｓｓ　カ’
ｆヘテ０かどうかを判定する。シンドロームＳ。、Ｓｌ
、Ｓ。

Ｓ３　が丁べてＯであ五は誤りが発生していなかったと
判定し、そうでなければ、ｌＮ以上の誤りが発生してい
たと利足する。

誤りなし検出回路（４］Ｊで誤りが発生していなかった
と判定した場合には、誤り訂正回路（ト）では訂正動作
なせずに記憶回ｇ（支）から入力データおシンボルのう
ち情報部あシンボルをそのまま出力端子（５ｂ）へ出力
する。同時に、フラグ発生回路−でそのブロック（ｌブ
ロックは２４シンボルで構成される）に対応したフラグ
を０にリセットして出力端子（５ａ）へ出力する。

誤りなし検出回路（４υで１１以上の誤りが発生してい
たと判定した場合には、ｒｌ誤り検出回路（４２１で１
東誤りかどうかを判定する動作を８こなう。シンドロー
ムＳ。、Ｓ□１８２１８Ｂ　を入力として、１重誤り検
出側＠（転）ではｇ　ｏ　”Ｆ　Ｏ、Ｓ　ｌ’？　０　、８２　”？　０
　、　Ｓ　３　”ｅ　Ｏ力）つＳｔ／Ｓｏ　＝　８２／８１＝　Ｓｓ／Ｓｔが満足され
ているかどうかを利足する。上記の条件が満足されてい
ればＸＺ誤りが発生していたと判定する。上記の条件が
満足されていなければ２１以上の誤りが発生していたと
刊犀する。

１］１誤り検出回路（転）でｒｌ誤りが発生していたと
判定した場合には、１車誤りの位置と大きさの演算回路
（転）で１重誤りの位置αＸと大きさｅｚを（８）式お
よび（９）式でそれぞれ計算する。

但し。

である。ＣＺＪ号器に）への入力データ２８シンボル８
よび誤すパターンを多項式で表視するとそれぞれｒ（Ｘｌ＝　、Ｘ：ｏｒＨＸ’ ｅ　ｉＸｌ　＝　ｅｘＸＸと皆けるから、誤り訂正回路囮ではＣＩＸＩ礼Σ。（：：、）（ｉ＝　ｒ　（Ｘｉ■ｅ　ｆＸｌ・・・・・・・・・・・−
・・・・・・・・・・・・・−・・・−・・・・・・　
（４５）によって誤りを訂正しく■は２を法とする加算
である）、情報部２４シンボルを出力端子（５ｂ）へ出
力する。同時に、フラグ発生回路−で上記２４シンボル
に対応したフラグな０にリセットして出力端子（５ａ）
へ出力する。

２重誤り検出回路（４４１でＣｘ４ｉ号器の場合と同様
にして２亜誤りが検出されたときには曳式、（２）式に
よって誤り位置αＸ　ｌ　ａｙ　　をそれぞれ計算し。

価）式および（至）式によって誤りの大きさｅｚ＋ｅｙ
を計算する。次に、誤りの位置αＸ、αｙにＣｌフラグ
が付加されているかどうかを２重誤りの位置とフラグの
位置との比較回路（４力で調べ、以下のように場合を分
けて復号する。

（１）位置αＸ、αｙの両方に７ラグが付加されている
場合、１ブロツク内のフラグの総数が４以下のときには
Ｃ１復号器と同様にしてＣＴＸ詮ΣＣ，）（ｉ −ｉ！０＝、Σｏｒｉ−Ｘｉ■（ｅｘＸＸ　＋ｅｙＸ３’ｌ　・
・−＝・＝・・（８によって誤り訂正回路−で２個の消
失（フラグの付加された誤り）が訂正され（■は２を法
とする加算である）、同時にフラグ発生回路（財）では
上記２４シンボルに対応したフラグな０にリセットする
。

一方１ブロック内のフラグの総数が５以上のときには誤
り訂正回路（ト）では訂正動作なせず、上記２４シンボ
ルに対応したフラグをたてる。フラグの情報は出力端子
（５ａ）から出力しデータは出力端子（５ｂ）から出力
する。

（１１）　　位置ｆｆ）（、αアのいずれか一方にのみ
フラグが付加されている場合、１ブロツク内のフラグの
総数が３以下のときには、開式によって誤り訂正回路（
４６１で消失１１１ｉ！ｉｌと誤り（見逃し）１１向が
訂正され、同時にフラグ発生回路にでは上記２４シンボ
ルに対応したフラグをリセットする。−万、ｌブロック
内の７ラグの総数が４以上のときには誤り訂正回路（４
６１では訂正動作をせず、上記２４シンボルに対応した
フラグをたてる。

フラグの情報は出力端子（５ａ）から出力し・データは
出力端子（５ｂ）から出力する。

６１１）位置αＸ、αｙのいずれにもフラグが付加され
た場合、ｌブロック内のフラグの総数が０あるいは１の
ときは（碕式によって誤り訂正回路嘔で２閾の誤りが訂
正され、同時にフラグ発生回路（４８１では上記２４シ
ンボルに対応したフラグを０にリセットする。

一方、１ブロック内の７ラグの総数が２および４以上の
ときには、誤り訂正回路Ｉでは訂正動作なせず、上記２
４シンボルに対応したフラグをたてる。フラグの情報は
出力端子（５ａ）から出力し、データは出力端子（５ｂ
）から出力する。

１ブロツク内の７ラグの総数が３のときは３個の消失が
発生したものとみなして一旦、３１消失の大きさ演算回
路（４１でこれらの大きさＥ。

Ｅｉ　Ｆｉｋ　（Ｅ（０，αｉＬ　ｔｏ≦ｊ≦２５４）
を消失の位置α１゜αｉ、αｋＴＢ（αｉ）、　（Ｑ≦
ｉ≦３１１とシンドロームを用いてなる式によって計算し、誤り訂正回路（転）で訂正動作
をし、訂正されたデータを記憶回路−に記憶する。次に
、この訂正動作が正しかったかどうかを確認するために
、記憶回路−から訂正されたデータを３重消失訂正動作
の確認回路６Ｄへ入力する。３重消失訂正動作の確認回
路（５１１では先ず、上記の訂正されたデータ１〆＝（
ｙ（，１′１．　ｎ−０−、ｒ２７１より新たに作が正しかったものとしてフラグ発生回路（４８１では
フラグを０に）セットして出力端子（５ａ）へ出力し、
データは出力端子（５ｂ）へ出力する。シンドロームが
１つでもＯ″′ｃなければ訂正動作が誤っていたものと
みなしてフラグ発生回路咽ではフラグを１にセットして
出力端子（５ａ）へ出力しデータは出力端子（５ｂ）へ
出力する。

さらに、シンドロームＳｏ、　Ｓｌ、　Ｓ２．　Ｓ、の
うち０でないものが少なくとも１つありしかも１重誤り
でも２重誤りでもないと判定しかっ１ブロツク内のフラ
グの総数が３でない場合には誤り訂正回路（鉛では訂正
動作をせずにデータをそのまま出力端子（５ｂ）へ出方
する。同時に、フラグ発生回路囮では訂正不能な誤りが
検出されたとして情報部２４シンボルに対応してフラグ
をたて（１にセットして）、出方端子（５ａ）へ出力Ｔ
る。

シンドＣ’　　ｌｈ　Ｓｏ、　ｓｌ、　ｓ、、　ｓ、　
０）うち０テナイものが少なくとも１つありしかも１重
誤りでも２重誤りでもないと刊足し、かつフラグの総数
が３のときには、上記３重消失の復号と全く同様にして
復号動作をおこなう。

以上のように入力端子山より人力した諺シンボルぶんの
データがＣ１復号器（ハ）で復号され、消失情報を付加
され、ヂ・インタリープ回路例でデ・インタリーブされ
、Ｃ２復号器島では上ＧＵ、消失情報をオリ用して３シ
ンボルぶんのデータを復号する。

このような復号動作を繰り返して次々とすべて人力デー
タを復号する。

（２８）上の（３２，２８，５）　！ノード・ンロモン
符号を用い、Ｃ２符号としてガロア体ＯＦ　（２つ上の
（２８，２４５）リード・ンロモン符号を用いた場合を
示したが＋Ｃ１，ｃ、符号としてはそれぞれ任意の線形
符号でもよい。

以上のように１本発明にょれｌ”［：Ｃｔ復号器で１重
誤りおよび２重誤りを訂正しかつ２重以上の誤りがある
場合には消失情報（フラグ）を付加し、Ｃ２復号器では
上記消失情報を利用して２重の誤りまで訂正するように
構成したので、誤りを検出する確率のベキ乗の最小項が
ＰＬｏに比例し、誤りを見逃丁確率のベキ乗の最小項が
ｐ　Ａ　１に比例し一性能が大幅に向上するという効果
がある。

【図面の簡単な説明】

、１−１図は従来の復号化装置の構成図、矛２図は従来
におけるｃｌ復号器の構成図、矛３図は従来におけるＣ
２復号器のｌ＃構成図矛４図は従来におけるＣ１復号器
の復号動作のフローチャート。矛５図は従来におけるＣ２復号器の復号動作のフローチ
ャート、矛６図は本発明の復号化装置の構成図、１・７
図は本発明の特徴をなすｃｌ復号器の構成図、矛８図は
本発明の特徴をなすＣ２復号器の構成図、矛９図は本発
明の特徴をな丁ｃｌ復号器の復号動作のフローチャート
、矛１ｏ図は本発明の特徴をなすＣ２復号器の復号動作
のフローチャートである。図中・ｆｉ＋は復号化装置への入力端子、（２）は従来
のＣ１復号器、（３）はデ・インターリーブ回路。（４）は従来のＣ２復号器・（５ａ）はフラグ（誤り検
出情報）の出力端子、（５ｂ）は復号データの出力端子
。（６）は従来のＣ１復号器における復号データの出力端
子、（７）は人力データの記憶回路、（８）は誤り訂正
回路、（９）はシンドローム演算回路、　（ＩＱ＋は誤
りなし検出回路、αＤは１重誤り検出回路、　（１２＋
は１重誤りの位置と大きさの演算回路、　Ｃ３１は制絢
回路、０引ま従来のＣ２復号器における入力端子、Ｃ５
）は入力データの記憶回路、Ｃ６）は誤り訂正回路。面はシンドローム演算回路、αＱは誤りなし検出回路２
日は１重誤り検出回路、圓は１重誤りの位置と大きさの
演算回路、３υはフラグ（誤り検出情＊）発生回路、（
支）は制御回路、（ハ）は本発明の特徴をなすＣ１復号
器、（２４１はデ・インターＩＪ　−プ回路、内は本発
明のＣ２復号器、　（２６ａ）はフラグ（消失情報）の
出力端子、　（２６ｂ）は復号データの出力端子、＠は
記憶回路、＠はシンドローム演算回路、＠は誤りなし検
出回路、ａｌｌは１恵誤り検出回路、ＳυはｌＮ誤りの
位置と大きさの演算回路、Ｃ１２１は２重誤りの検出回
路、（至）は２車誤りの位置と大きさの演算回路１３４
１は誤り訂正回路。 ω）はフラグ（消失情報）発生回路、　Ｃ％ｌは制御回
路、　（３７ａ）は本発明の特徴をなすＣ２復号器にお
けるフラグ（消失情報）の入力端子、　（３７ｂ）はデ
ータの入力端子、（支）は消失情報（位置と個数）を記
憶しまた新たに皆変えるための記憶回路、鴎はデータの
記憶回路、　ｔ４ｔＪ）はシンドローム演算回路、（財
）は誤りなし検出回路、　＋４２１は１重誤り検出回路
、（転）は１亀誤りの位置と大きさの演算回路。（財）は２重誤り検出回路、（句は２車誤りの位置と大
きさの演再回路、嘔は誤り訂正回路、（資）は２Ｎ誤り
の位置にフラグが付加されているかと己かを調べるため
の２重誤りの位置とフラグの代置との比較回路、囮はフ
ラグ発生回路、（ａは３重消失の大きさ演算回路、ωは
記憶回路、５１１！Ｉ；３重消失訂正動作の確認回路、
■は上記の回−を制御ｔｌする制御回路である。なお１図中同一あるいは相当部分には同−省号を付して
示しである。代理人　葛　野　信　− 第１図鴇　　　　　　　　　　　　　　　　　　　−第４図第６図第９図第１頁の続き０発　明　者　石田雅之長岡京市馬場図所１番地三菱電機株式会社電子商品開発研究所内０発　明　者　菅野宏長岡京市馬場図所１番地三菱電機株式会社電子商品開発研究所内２５４−

Claims

【特許請求の範囲】

誤り検出および誤り訂正の機能をもつ矛１の復号器と、
矛１の復号器の出力データをデ・インターリーブ回路お
よび誤り検出ｇよび誤り訂正の機能をもつ矛２の復号器
とから成る復号化装置において、上記矛ｌの復号器には
誤りを訂正するとともに誤りを検出した場合にはデータ
にフラグを付加して消失情報とする回路を備え上記矛２
の復号器には２蘭の誤りまでを訂正する機能を有し、復
号器が１個の誤りと判定した場合にはこれを訂正し、２
１ｆｉ！ｉｔの誤りと判定した場合には２個の誤りにフ
ラグが付いているかどうかを判別し、２１１ｉ！ｉｌの
誤りの内方にフラグが付いているときはフラグの総数が
４以下であればこの誤りを訂正し、５以上であれば誤り
検出の処理をし、２１固の誤りのうちどちらか一万のみ
にフラグが付いているときはフラグの総数が３以下であ
ればこの誤りを訂正し、４以上であれば誤り検出の処理
をし、２個の誤りのいずれにもフラグが付いていないと
きはフラグの総数が１以下であればこの誤りを訂正し、
フラグの総数が３であれば３蘭の消失が発生していたも
のとみなして復号動作をおこない、フラグの総数が２あ
るいは４以上のときには誤り検出の処理をし、復号器が
３１固以上の誤りと判定した場合にはフラグの総数が３
であれば、上記と同様に３個の消失として復号処理し、
それ以外の場合には誤り検出の処理を行う機能回路を備
えたことを特徴とする復号化装置。