[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JPH0137048B2 - - Google Patents

Info

Publication number
JPH0137048B2
JPH0137048B2 JP58223601A JP22360183A JPH0137048B2 JP H0137048 B2 JPH0137048 B2 JP H0137048B2 JP 58223601 A JP58223601 A JP 58223601A JP 22360183 A JP22360183 A JP 22360183A JP H0137048 B2 JPH0137048 B2 JP H0137048B2
Authority
JP
Japan
Prior art keywords
code
error
decoding
symbols
minimum distance
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.)
Expired
Application number
JP58223601A
Other languages
English (en)
Other versions
JPS60116230A (ja
Inventor
Tatsuo Sugimura
Isao Sato
Akira Ichinose
Yuzuru Kuroki
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Holdings Corp
Original Assignee
Matsushita Electric Industrial Co Ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Matsushita Electric Industrial Co Ltd filed Critical Matsushita Electric Industrial Co Ltd
Priority to JP22360183A priority Critical patent/JPS60116230A/ja
Priority to US06/649,718 priority patent/US4653051A/en
Priority to EP84110958A priority patent/EP0136604B1/en
Priority to DE8484110958T priority patent/DE3484331D1/de
Priority to CA000463060A priority patent/CA1217868A/en
Publication of JPS60116230A publication Critical patent/JPS60116230A/ja
Publication of JPH0137048B2 publication Critical patent/JPH0137048B2/ja
Granted legal-status Critical Current

Links

Classifications

    • GPHYSICS
    • G11INFORMATION STORAGE
    • G11BINFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/10Digital recording or reproducing
    • G11B20/18Error detection or correction; Testing, e.g. of drop-outs
    • G11B20/1833Error detection or correction; Testing, e.g. of drop-outs by adding special lists or symbols to the coded information
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00Coding, 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/29Coding, 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

Landscapes

  • Engineering & Computer Science (AREA)
  • Signal Processing (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)

Description

【発明の詳細な説明】
産業上の利用分野 本発明は高信頼性を要求されるデイジタル情報
データの伝送または記録に際して、その誤り制御
に用いられる最小距離2および最小距離tの二つ
の符号により構成される最小距離2tの積符号の
復号に関する。 従来例の構成とその問題点 デイジタル情報データの伝送または記録に際し
ては、誤り伝搬を防止するという観点から、デー
タ系列を一定長に区切り、その各々に対してブロ
ツク符号化を行なう。また、伝送するための通信
路または記録するための記録媒体の信頼性・誤り
特性があまり良くない場合にはランダム誤りとバ
ースト誤りが混在する、いわゆる、複合誤りを訂
正する必要が生じる。そこで、インターリーブに
よりバースト誤りをランダム化し、ランダム誤り
訂正を行なう方法がとられる。誤り訂正の対象が
ランダム誤りのみの場合または復合誤りの場合の
いずれの場合にも誤り訂正符号の高いランダム誤
り訂正能力がデイジタル情報データの高い信頼性
に寄与する。積符号は、その訂正能力に比べ構成
要素の符号の復号が容易であるという特徴をち、
復合誤り訂正のためのインターリーブとよく調和
するため、デイジタル情報データの伝送または記
録のための誤り制御に用いられる。しかし、積符
号のような二つ以上の構成要素を有する符号にお
いては、それぞれの構成要素の復号が有機的にか
かわりあうことが必要である。たとえば、二つの
符号により構成された積符号の復号においては、
第1の構成要素の符号の復号をした後、その結果
を用いて第2の構成要素の符号の復号を行ない、
必要とあらば第1の構成要素の符号の復号にもど
るというように、このような復号操作の繰り返し
が必要となる。したがつて、積符号の復号におい
ては個々の構成要素の符号の復号は比較的簡単で
あるがそれらの復号を有機的に結びつけるアルゴ
リズムが複雑となり、一般的なアルゴリズムは与
えられていない。積符号の一つである最小距離2
および最小距離tの二つの符号により構成される
最小距離2tの積符号の復号方法に関しても同様で
ある。そして、デイジタル情報データの伝送また
は記録においては、誤り訂正操作の処理速度が高
速であることが要求されるため、積符号の高速の
復号方法が必要となつてくる。 発明の目的 本発明は積符号の復号方法として、装置化が容
易であり、かつ高速処理が可能な復号アルゴリズ
ムを与えるものであり、誤り制御に用いることに
より、高速かつ信頼性の高いデイジタル情報デー
タの伝送または記録を可能にするものである。 発明の構成 本発明は、(k×l)の行列状に配置されたk
×lジンボルの情報に対して、行方向のlシンボ
ルに最小距離2の符号を形成するチエツクサムシ
ンボルをk行の各行に付加し、列方向のkシンボ
ルに最小距離tの符号を形成するパリテイチエツ
クシンボルをチエツクサムシンボルの列を含めた
(l+1)列の各列に付加することにより構成さ
れた最小距離2tの積符号の復号に際し、(l+
1)個の列方向の復号操作を行ない、その復号操
作過程から得られる誤り個数フラグに誤り個数の
多いものから高い優先順位をつけ、生起した誤り
個数フラグのうち最も高い優先順位に誤り個数フ
ラグの生起回数および種類により3つの誤り訂正
モードに分類し、各誤り訂正モードに応じて誤り
検出、行方向の符号を用いた一重消失誤り訂正お
よび行方向の符号を用いた誤り検出を行ない、積
符号全体として(t−1)シンボル以下の誤り訂
正およびtシンボル誤り検出を行なう積符号の復
号方法である。 実施例の説明 以下、本発明の実施例について説明するが、そ
の前に本発明の原理について説明する。 第1図は本発明の復号方法が適用される積符号
の符号構成原理図である。第1図において、1は
情報データ、2はチエツクサムシンボル、3は検
査記号である。(k×l)行列に表せるように情
報データ1を配列する。ここで行列の要素をシン
ボルと呼ぶことにし、1シンボルはiビツト組で
表わされるものとする。次にチエツクサムシンボ
ル2は前記(k×l)行列の各行において、lシ
ンボルの対応するビツト毎の排他的論理和をとつ
た結果得られるものである。そして、前記の処理
により得られた(k×〔l+1〕)行列の各列にお
いて、最小距離tの符号を形成するように符号化
を行ないrシンボルの検査記号を個々の列に付加
する。以上のようにして構成された(〔k+r〕×
〔l+1〕)行列の符号は最小距離2tの積符号と
なる。ここで、注意しなければならないことは第
(l+1)列に付加されたrシンボルの検査記号
3は、それぞれ第(k+1)行から第(k+r)
行のチエツクサムシンボル2となつていることで
あり、符号化の順序を入れ換えても全く同じ符号
が構成できることである。また、第(l+1)列
の(k+r)シンボルのチエツクサムシンボル2
は〔i×(k+r)〕ビツトの一つのチエツクサム
とも見ることができ、また(i×k)ビツトのチ
エツクサムと(i×r)ビツトのチエツクサムの
二つのチエツクサムと見ることもできる。そし
て、以後における説明の便宜上、行方向の符号を
外符号、列方向の符号を内符号と呼ぶことにす
る。 本発明の復号方法は第2図に示す復号フローチ
ヤートに従い実行される。まず最初に内符号の復
号操作を行なう。そして、この過程から誤り個数
フラグを生成する。すなわち、最小距離tの内符
号においては、「t−1/2」個以下の誤り訂正およ び「t+1/2」個以上のの誤り検出が行なえる。 ただし、「x」はxを超えない最大の整数を示す。
その過程において、次のような誤り個数フラグFi
をどれか一つたてる。 もし、内符号の訂正能力を越えた誤りが生起し
た場合には、誤り訂正不能で
【式】が立つ か、誤つたj重誤り訂正を実行しFjが立つか、も
しくは生起した誤りがたまたま符号語を形づくり
Fpが立つかは不定である。以上のように(l+
1)個の内符号の復号を行なう。次に上記の(l
+1)個の誤り個数フラグの統計処理をして、そ
の結果三つのコレクシヨンモードに分類する。ま
ず誤り個数フラグを誤り個数毎にカウントする。
Fiの生起した個数をCiとすると次式のようにな
る。 ここで、Ciの添字iの大きなものより高い優先
順位をつける。そして、次に示すようなコレクシ
ヨンモードに分類する。 (i) コレクシヨンモード1
【式】すなわち誤り検出を2回以上行 なつた場合。 (ii) コレクシヨンモード2 非零の最も優先順位の高いCiが1の場合。 (iii) コレクシヨンモード3 上記二つのモード以外の場合。 これら三つのコレクシヨンモードにおいて、外
符号を用いた誤り訂正操作または誤り検出操作は
次のように行なう。 (a) コレクシヨンモード1 無条件に訂正不能の誤りを検出したことをア
サートする。 (b) コレクシヨンモード2 非零の最も優先順位の高いCiを1としたFi
生起した内符号の列にポインタを立てる。そし
て、受信語または再生語の外符号におけるチエ
ツクサムをとり、ポインタの立つた列に排他的
論理和で加える。もしくは、ポインタが立つた
列を除いて外符号のチエツクサムをとり、その
列に置き換える。 (c) コレクシヨンモード3 受信語または再生語の外符号におけるチエツ
クサムをとる。 (ア) チエツクサムが零の場合 誤りなし。 (イ) チエツクサムが非零の場合 訂正不能の誤りを検出したことをアサート
する。 以上説明したように復号することにより最小距
離2tの積符号において、(t−1)シンボル以
下の誤り訂正およびtシンボル誤り検出が可能と
なる。もちろん、内符号の復号において誤り訂正
の個数を少なくすることは可能ではあるが、積符
号全体としての誤り訂正能力は劣化する。 以下、本発明の復号方法の一実施例として、内
符号の最小距離が5であるような最小距離10の積
符号の復号を例にとつて説明する。この積符号は
最小距離が10であるため、理論上4シンボル以下
の誤り訂正および5シンボル誤り検出が可能であ
る。ここで、第3図に5シンボル以下のすべての
誤りパターンを示す。第3図においては積符号全
体に生起した誤りの個数eと内符号の列における
誤りの個数により場合(CASE)を分類してい
る。そして、内符号の復号において生成される誤
り個数フラグの各場合の下に示す。誤りのない内
符号の列においてはF0が生成されるが、eが1
以上の場合においては表示していない。さらに、
内符号は最小距離が5であるため、内符号の各列
においては2シンボル以下の訂正が可能である
が、その訂正能力以上の誤りすなわち3シンボル
以上の誤りが生起した場合には必らずしも誤り検
出F3が生成されるとはかぎらない。そこで、
CASE7、10、14および17の場合のように一つの
内符号の列が3シンボルの誤りが生起したとき
は、、内符号の最小距離が5であるため、誤り訂
正不能または誤つた2シンボル誤り訂正の二つの
処理が考えられ、前者はF3、後者はF2が生成さ
れる。同様に4シンボル誤りのCASE11および16
に対してF3、F2、F1のいずれかが、そして5シ
ンボル誤りCASE18に対してはF3、F2、F1、F0
のいずれかが生成され、さらに場合分けされる。
ここで、これらの場合をコレクシヨンモードに分
類する。 (A) コレクシヨンモード1 なし (B) コレクシヨンモード2 CASE2、4、6、7、9、10、11、13、14、
16(i)、16(ii)、17(i)、18(i)、18(ii)および18(iii) (C) コレクシヨンモード3 CASE1、3、5、8、12、15、16(iii)、17(ii)、
18(iv) コレクシヨンモード2に類別された場合のなか
には、内符号の復号において、生起した誤りがす
べて訂正されている場合があり、その場合にも外
符号を用いた誤り訂正操作が行なわれるが、新た
な誤りが付加されるおそれはない。それ以外の場
合には内符号の復号によりポインタの立つた列以
外は正しく訂正されているため、外符号を用いた
誤り訂正操作により、ポインタの立つた列は正し
く訂正される。コレクシヨンモード3は、内符号
により正しく訂正されたか否かを検証するモード
であり、CASE16(iii)、17(ii)および18(iv)の場合のみ
誤り訂正不能の誤りの検出をアサートする。以上
説明したように、例にとつた最小距離10の積符号
において、本発明の復号方法を用いれば理論上可
能な4シンボル以下の誤り訂正および5シンボル
誤り検出が可能となる。同様にして、内符号の最
小距離が2、3、4および6以上の場合において
も理論上可能な誤り制御能力を発揮できることが
証明できる。前記の例にあげた最小距離10の積符
号を行方向すなわち外符号の方向に伝送または記
録し、本発明の復号方法を用いるならば、2行分
すなわち2×(l+1)シンボル長までのバース
ト誤りと1シンボルランダム誤り、1行分すなわ
ち(l+1)シンボル長までのバースト誤りと2
シンボルランダム誤り等の複合誤りが同時に生起
した場合においても訂正可能である。 本発明の復号方法において最も重要な過程は誤
り個数フラグの統計処理によるコレクシヨンモー
ドの決定である。ここでこの過程の装置化の一具
体例を前記の例の最小距離10の積符号を例にとつ
て説明する。ただし、(l+1)個の内符号は第
1列より順次シリアルに復号されるものとする。
第4図は誤り個数フラグFiのカウンタの一例であ
る。Fiが生起したとき、第4図aに示されるよう
なパルスが発生されるならば、第4図bの回路で
個数カウントされる。本発明の復号方法におい
て、Fiが生起した個数Ciは0個、1個、2個以上
の三通りの識別しか必要としないため、この回路
で十分である。そして、第4図cに示れたように
識別される。そして、コレクシヨンモードの決定
は次に示すような論理式で行なわれる。コレクシ
ヨンモード1、2、3をそれぞれ1、2、
CM3で示すとすると 1=3031 2=30313031・F202130312021・F1011 CM3=3031・F20・F2130312021・F10・F11303120211011 となり単純なAND・OR回路で実現できる。次に
ポインタ生成回路の一例を示す。ポインタはコレ
クシヨンモード2の時のみ必要であるが、(l+
1)個の内符号の復号が完了するまでコレクシヨ
ンモードは決定されない。そこでポインタが立つ
可能性のある内符号に対して仮のポインタを立
て、より優先順位の高い誤り個数フラツグが生起
したとき、仮のポインタを更新していく方法をと
る。第5図はポインタ指示回路の一具体例であ
る。内符号の復号データを格納するメモリのアド
レスをでラツチする。したがつて最後に生
成されたによりラツチされたメモリアドレ
スがポインタの侯補となり、コレクシヨンモード
2となつたとき、この侯補が真のポインタとな
る。 以上の説明からも容易に理解できるように、本
発明の復号方法は簡単に装置化することが可能で
あり、また、復号アルゴリズムが単純なため、時
間遅延のない高速処理が行なえる。 発明の効果 本発明の積符号の復号方法は、内符号の復号、
その過程から得られる誤り個数フラグの統計処理
によるコレクシヨンモードの分類および前記コレ
クシヨンモード毎の異なつた外符号を用いた復号
により、積符号の理論上可能な訂正能力および検
出能力を実現する。本発明の積符号の複号方法は
そのアルゴリズムが単純であり、マイクロプログ
ラム等を用いなくとも容易に装置化することが可
能となるため、高速かつ信頼性の高いデイジタル
情報データの伝送または記録が可能となり、その
実用的効果は大きい。
【図面の簡単な説明】
第1図は本発明の復号方法が適用される積符号
の符号構成原理図、第2図は本発明の復号方法の
復号フローチヤート、第3図は本発明の復号方法
の一実施例における復号の説明のための誤りパタ
ーン図、第4図は本発明の復号方法の一装置化例
における誤り個数フラグカウンタの説明図、第5
図は前記一装置化例におけるポインタ指示回路図
である。 1……情報データ、2……チエツクサムシンボ
ル、3……検査記号。

Claims (1)

    【特許請求の範囲】
  1. 1 (k×l)の行列状に配置されたk×lジン
    ボルの情報に対して、行方向のlシンボルに最小
    距離2の符号を形成するチエツクサムシンボルを
    k行の各行に付加し、列方向のkシンボルに最小
    距離tの符号を形成するパリテイチエツクシンボ
    ルをチエツクサムシンボルの列も含めた(l+
    1)列の各列に付加することにより構成された最
    小距離2tの積符号に際し、(l+1)個の列方
    向の復号操作を行ない、その復号操作過程から得
    られる誤り個数フラグに誤り個数の多いものから
    高い優先順位をつけ、生起した誤り個数フラグの
    うち最も高い優先順位に誤り個数フラグの生起回
    数および種類により3つの誤り訂正モードに分類
    し、各誤り訂正モードに応じて誤り検出、行方向
    の符号を用いた一重消失誤り訂正または行方向の
    符号を用いた誤り検出を行ない、積符号全体とし
    て(t−1)シンボル以下の誤り訂正およびt−
    シンボル誤り検出を行なうことを特徴とする積符
    号の復号方法。
JP22360183A 1983-09-14 1983-11-28 積符号の復号方法 Granted JPS60116230A (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
JP22360183A JPS60116230A (ja) 1983-11-28 1983-11-28 積符号の復号方法
US06/649,718 US4653051A (en) 1983-09-14 1984-09-12 Apparatus for detecting and correcting errors on product codes
EP84110958A EP0136604B1 (en) 1983-09-14 1984-09-13 Decoding method and system.
DE8484110958T DE3484331D1 (de) 1983-09-14 1984-09-13 Dekodierverfahren und vorrichtung dafuer.
CA000463060A CA1217868A (en) 1983-09-14 1984-09-13 Apparatus for detecting and correcting errors in product codes for error correction in digital information data transmission or recording systems

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP22360183A JPS60116230A (ja) 1983-11-28 1983-11-28 積符号の復号方法

Publications (2)

Publication Number Publication Date
JPS60116230A JPS60116230A (ja) 1985-06-22
JPH0137048B2 true JPH0137048B2 (ja) 1989-08-03

Family

ID=16800734

Family Applications (1)

Application Number Title Priority Date Filing Date
JP22360183A Granted JPS60116230A (ja) 1983-09-14 1983-11-28 積符号の復号方法

Country Status (1)

Country Link
JP (1) JPS60116230A (ja)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS63120528A (ja) * 1986-11-07 1988-05-24 Matsushita Graphic Commun Syst Inc 二重誤り訂正回路
JPH0834438B2 (ja) * 1987-01-27 1996-03-29 松下電器産業株式会社 誤り検出訂正方法
JP2563389B2 (ja) * 1987-11-13 1996-12-11 松下電器産業株式会社 誤り検出訂正方法
JP4039227B2 (ja) 2002-12-13 2008-01-30 日本電気株式会社 復号方法及びプログラム並びにこれを用いた復号回路

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS55161445A (en) * 1979-06-04 1980-12-16 Mitsubishi Electric Corp Coding and decoding system
JPS5710561A (en) * 1980-06-20 1982-01-20 Sony Corp Error correcting method

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS55161445A (en) * 1979-06-04 1980-12-16 Mitsubishi Electric Corp Coding and decoding system
JPS5710561A (en) * 1980-06-20 1982-01-20 Sony Corp Error correcting method

Also Published As

Publication number Publication date
JPS60116230A (ja) 1985-06-22

Similar Documents

Publication Publication Date Title
EP0136604B1 (en) Decoding method and system.
KR960003094B1 (ko) 프로덕트 코드를 디코딩하는 디코더 및 방법
JP3234130B2 (ja) 誤り訂正符号復号化方法およびこの方法を用いる回路
JPH0697542B2 (ja) インタ−リ−ブ回路
JPS59165541A (ja) 多数バイトエラ−訂正システム
JPS6346615B2 (ja)
US20050188292A1 (en) Method and apparatus for encoding special uncorrectable errors in an error correction code
JPH05244020A (ja) インターリーブ式の誤り訂正符号を復号化するための復号器能力強化方法
JPH0126209B2 (ja)
US8566679B2 (en) Error-correcting encoding method with total parity bits, and method for detecting multiple errors
US20050149834A1 (en) (18, 9) Error correction code for double error correction and triple error detection
US4858235A (en) Information storage apparatus
US7392461B2 (en) Decoding for algebraic geometric code associated with a fiber product
US5938773A (en) Sideband signaling with parity bit schemes
JPH0137048B2 (ja)
EP0650266A2 (en) An error correction code decoder and a method thereof
US5544179A (en) Mis-synchronization detection system using a combined error correcting and cycle identifier code
TWI744679B (zh) 利用錯誤碼進行資料處理的方法與裝置
JPH0452660B2 (ja)
JP2684031B2 (ja) データの復号化方法
JP3813337B2 (ja) 消失誤り訂正方法とその装置
US20220190846A1 (en) Single error correct double error detect (secded) error coding with burst error detection capability
CN110928725B (zh) 闪存中基于矩阵表示的多重置换码的构造及译码方法
RU2297030C2 (ru) Самокорректирующееся устройство хранения информации
JPH06244741A (ja) 誤り訂正方法