JPS642293B2 - - Google Patents

Info

Publication number
JPS642293B2
JPS642293B2 JP57102808A JP10280882A JPS642293B2 JP S642293 B2 JPS642293 B2 JP S642293B2 JP 57102808 A JP57102808 A JP 57102808A JP 10280882 A JP10280882 A JP 10280882A JP S642293 B2 JPS642293 B2 JP S642293B2
Authority
JP
Japan
Prior art keywords
error
detection circuit
circuit
code
error position
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
JP57102808A
Other languages
English (en)
Other versions
JPS58219850A (ja
Inventor
Jun Inagawa
Tadashi Kojima
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.)
Toshiba Corp
Original Assignee
Tokyo Shibaura Electric 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 Tokyo Shibaura Electric Co Ltd filed Critical Tokyo Shibaura Electric Co Ltd
Priority to JP57102808A priority Critical patent/JPS58219850A/ja
Publication of JPS58219850A publication Critical patent/JPS58219850A/ja
Publication of JPS642293B2 publication Critical patent/JPS642293B2/ja
Granted legal-status Critical Current

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/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

Landscapes

  • Physics & Mathematics (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Detection And Correction Of Errors (AREA)
  • Error Detection And Correction (AREA)

Description

【発明の詳細な説明】 〔発明の技術分野〕 この発明はCRCC(Cyclic Redundancy Check
Code)によるエラー訂正装置に係り、特にその
誤り位置検出回路の改良に関する。
〔発明の技術的背景〕
近時、デジタルオーデイオ機器の開発が進めら
れているが、この種の機器にあつてはそのエラー
訂正符号として巡回符号とも呼ばれるCRCC符号
が採用されている。
すなわち、かかるCRCC符号によるエラー訂正
の原理は、生成多項式で情報ビツトを割算した剰
余を検査ビツトとして用いるもので、復号時に再
度割算を行なつて剰余がなければつまり割り切れ
れば符号誤り(エラー)がないものとし、且つ剰
余があればつまり割り切れなければ符号誤り(エ
ラー)があると判別することにより、単一誤り訂
正と二重誤り検出を可能としたものである。
今、一例として原始多項式G(x)=1+x5+x12+
x16を生成多項式とする情報ビツト:80、検査ビ
ツト:16、符号長96ビツトのCRCC符号の復号に
ついてみてみる。
この場合、受信系列r0,r1……r95を受信多項式
(Rx)により R(x)=r0+r1x+r2x2+……+r95x95 のように表わしたとすると、このR(x)を上記G(x)
で割つた剰余として与えられるシンドロームによ
り誤りの有無およびその内容を判定するものであ
る。
ここで、シンドロームすなわち剰余はG(x)の根
をαとすればR(α)で与えられ、R(1)、R
(α)により (1) R(1)=0、R(α)=0では誤りなし (2) R(1)=1、R(α)≠0では単一誤り (3) R(1)=0、R(α)≠0では二重誤り の如く判定し、(2)の単一誤りと判定された場合に
はその誤り位置を求めることによつてエラー訂正
を可能ならしめる。また、(3)の二重誤りと判定さ
れた場合には適宜な補正をなすのに供せられる。
そして、上記単一誤り時における誤り位置の検
出は、r95から数えてi番目(0≦i≦95)が誤
りであつたとした場合のシンドロームR(α)=
α95-iに対してαを適数回乗じて行く過程でR
(α)=α95になつた時点の乗算回数つまり(i)
を求める如くしてなされている。
第1図は以上のような原理に基いて構成された
従来の誤り位置検出回路を示すもので、先ず除算
回路11に入力端子INを介して受信系列がr95,
r94,……r6の順に入力される。そしてすべての
受信系列が入力されると除算回路11の出力Q0,
Q1……Q15が必然的にシンドロームR(α)とな
る。
この場合、除算回路11は第2図に示すように
フリツプフロツプFF0〜FF15とエクスクルシブオ
アEX―OR11〜EX―OR13を用いて多項式G(x)=
1+x5+x12+x16の形に結合された線形シフトレ
ジスタで構成されているものとすれば、これを後
述するクロツクパルスによつてi回シフトしてや
ればその内容R(〓)をαi倍したことになる。
つまり、単一誤りがr95から数えて(i)番目
に生じていたとすれば除算回路11を構成するシ
フトレジスタにはR(α)=α95-iが残つているも
のであるが、これをクロツク端子CKからのクロ
ツクパルスでもつて、(i)回シフトしてやるこ
とによりR(α)=α95となる。
すると、除算回路11の出力Q0,Q1,……Q15
がα95=(0010 1100 0010 0111)になつたのをパ
ターン検出回路12が検出してラツチパルスを出
力するようになる。
このラツチパルスは上記クロツクパルスによる
シフト回数をカウントしている7ビツトカウンタ
13の内容をラツチするラツチ回路14に供給さ
れ、これによつてラツチ回路14から誤り位置
(i)出力を得ることができることになる。
〔背景技術の問題点〕
しかしながら、以上のような従来の誤り位置検
出回路にあつては、誤り位置を検出するために必
要となるαの乗算回数が上述の例で最高96回にも
なる如く符号長のビツト数に等しいだけの乗算回
数を必要とするので、それだけ検出に要する処理
時間が長時間化するという問題を有していた。
〔発明の目的〕
そこで、この発明は以上のような点に鑑みてな
されたもので、可及的に短時間で誤り位置を検出
し得るように改良した極めて良好なる誤り位置検
出回路を提供することを目的としている。
〔発明の概要〕
すなわち、この発明による誤り位置検出回路
は、CRCC符号を構成する符号長Nビツトの受信
系列を所定の生成多項式の形に結合された線形シ
フトレジスタで除算せしめる除算回路と、この除
算回路の出力から誤り位置を与える特定パターン
を検出するパターン検出回路と、前記除算回路の
レジスタ内容が前記特定パターンに一致するまで
該レジスタをシフトせしめる手段と、この手段に
よるシフト回数をカウントして誤り位置出力を導
出する手段とを具備し、前記パターン検出回路の
特定パターン検出数を複数(m個)として前記シ
フトレジスタの、シフト回数(N)を最高N/m
回に低減可能に構成したことを特徴としている。
〔発明の実施例〕
以下図面を参照してこの発明の一実施例につき
詳細に説明する。
すなわち、第3図は前述した第1図の場合と同
様に原始多項式G(x)=1+x5+x12+x16を生成多
項式とする情報ビツト:80、検査ビツト:16、符
号長96ビツトのCRCC符号の復号に適用される誤
り位置検出回路であつて、入力端子INからの受
信系列がr94,r95……r0の順に除算回路21に入
力される。このようにして、すべての受信系列が
入力されると除算回路21の出力Q0,Q1……Q15
が必然的にシンドロームR(〓)となる。
ここで、除算回路21は第2図に示したように
多項式G(x)=1+x5+x12+x16の形に結合された
線形シフトレジスタで構成されているもので、こ
れを後述するクロツクパルスによつて(i)回シ
フトしてやればその内容R(〓)をαi倍したことにな
る。
そして、除算回路21の出力Q0,Q1,……Q15
が供給されるパターン検出回路22は、この場合
Q0,Q1,……Q15がα95=(0010 1100 0010
0111)、α63=(0000 0100 0010 1011)、α31=
(0001 1001 1101 1000)に一致したとき、α95、
α63、α31の各出力がそれぞれ“1”になる如く構
成されている。このパターン検出回路22のα95、
α63、α31の各出力はオアゲート23を介して7ビ
ツトラツチ回路24のラツチパルスとして供給さ
れると共に、そのうちのα63およびα31出力が7ビ
ツトラツチ回路24の上位2ビツト25および26の
セツトパルスとして供給される。
ここで、7ビツトラツチ回路24は、前記クロ
ツクパルスによる除算回路21のシフト回数をカ
ウントする5ビツトカウンタ25の出力20〜24が
対応する下位5ビツト20〜24に入力される如くな
されている。
而して、以上の構成において、今受信系列r95,
r94……r0でr95から数えてi番目(0≦i≦95)
が誤つていたとすると、該受信系列の入力が終了
した時点で除算回路21を構成するシフトレジス
タにはR(〓)=α95-iが残つているものであるが、こ
れをクロツク端子CKからのクロツクパルスでも
つて適数回シフトせしめることにより、その出力
がα95またはα63またはα31に一致するようにして
やる。
つまり、(i)が 0≦i≦31の場合i回のシフトでα95 32≦i≦63の場合(i−32)回のシフトで
α63 64≦i≦95の場合(i−64)回のシフトで
α31 にそれぞれ一致するものであるが、これを検出す
るパターン検出回路22においてα95出力が“1”
になつた場合には、この出力によりラツチ回路2
4でラツチされる5ビツトカウンタ25の出力が
そのまま誤り位置(i)を与える。
また、パターン検出回路22においてα63また
はα31出力が“1”になつた場合には、この出力
によりラツチ回路24の25または26ビツト目がセ
ツトされるので、これによる32または64を5
ビツトカウンタ25の出力に加えたものがそのと
きの誤り位置(i)として導出されることにな
る。
すなわち、以上のような誤り位置検出回路で
は、パターン検出回路22においてα95だけでな
く、α63およびα31のパターンを検出し得るように
しているので、必要となるシフト回数つまりαを
乗じる回数を最高でも32回に低減できるので、処
理時間を従来の1/3とし得る如く大幅に軽減す
ることができる。
そして、これは一般的には符号長Nビツトの誤
り位置検出に必要な最高シフト回数を従来のN回
から2m回(但し2m≦N)に軽減し得るもので、こ
の場合に必要となるパターン検出数(P)は P=N/2m(N/2mが整数のとき) P=〔N/2m〕+1(N/2mが整数でないときで〔
〕 はガウス記号とする。) なお、この発明は上記し且つ図示した実施例の
みに限定されることなく、この発明の要旨を逸脱
しない範囲で種々の変形や適要が可能であること
は言う迄もない。
〔発明の効果〕
従つて、以上詳述したようにこの発明によれ
ば、可及的に短時間で誤り位置を検出し得るよう
に改良した極めて良好なる誤り位置検出回路を提
供することが可能となる。
【図面の簡単な説明】
第1図は従来の誤り位置検出回路要部を示す構
成図、第2図は第1図に用いられる除算回路の具
体例を示す構成図、第3図はこの発明に係る誤り
位置検出回路の一実施例を示す要部の構成図であ
る。 IN……入力端子、21……除算回路、22…
…パターン検出回路、23……オア回路、24…
…7ビツトラツチ回路、25……5ビツトカウン
タ、CK……クロツク端子。

Claims (1)

    【特許請求の範囲】
  1. 1 CRCC符号を構成する符号長Nビツトの受信
    系列を所定の生成多項式の形に結合された線形シ
    フトレジスタで除算せしめる除算回路と、この除
    算回路の出力から誤り位置を与える特定パターン
    を検出するパターン検出回路と、前記除算回路の
    レジスタ内容が前記特定パターンに一致するまで
    該レジスタをシフトせしめる手段と、この手段に
    よるシフト回数をカウントして誤り位置出力を導
    出する手段とを具備してなる誤り位置検出回路に
    おいて、前記パターン検出回路の特定パターン検
    出数を複数(m個)として前記レジスタのシフト
    回数(N)を最高N/m回に低減可能に構成した
    ことを特徴とする誤り位置検出回路。
JP57102808A 1982-06-15 1982-06-15 誤り位置検出回路 Granted JPS58219850A (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP57102808A JPS58219850A (ja) 1982-06-15 1982-06-15 誤り位置検出回路

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP57102808A JPS58219850A (ja) 1982-06-15 1982-06-15 誤り位置検出回路

Publications (2)

Publication Number Publication Date
JPS58219850A JPS58219850A (ja) 1983-12-21
JPS642293B2 true JPS642293B2 (ja) 1989-01-17

Family

ID=14337346

Family Applications (1)

Application Number Title Priority Date Filing Date
JP57102808A Granted JPS58219850A (ja) 1982-06-15 1982-06-15 誤り位置検出回路

Country Status (1)

Country Link
JP (1) JPS58219850A (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07104738A (ja) * 1993-10-01 1995-04-21 Maruyasu Kanagata:Kk 大正琴

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0834441B2 (ja) * 1987-11-17 1996-03-29 株式会社日立製作所 誤り位置算出方法
JP2532917B2 (ja) * 1988-04-20 1996-09-11 三洋電機株式会社 デ―タ誤り検出回路

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4142174A (en) * 1977-08-15 1979-02-27 International Business Machines Corporation High speed decoding of Reed-Solomon codes
JPS5778608A (en) * 1980-10-31 1982-05-17 Matsushita Electric Ind Co Ltd Decoding method of reed-solomon code

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07104738A (ja) * 1993-10-01 1995-04-21 Maruyasu Kanagata:Kk 大正琴

Also Published As

Publication number Publication date
JPS58219850A (ja) 1983-12-21

Similar Documents

Publication Publication Date Title
EP0032055B1 (en) Document processing system
JPH0728227B2 (ja) Bch符号の復号装置
EP0233075A2 (en) Method and apparatus for generating error detection check bytes for a data record
JPS59124011A (ja) 多数バイトエラ−訂正システム
JPS5864844A (ja) 同期検出方式
JPS632370B2 (ja)
EP0629052B1 (en) Method of and circuit for correcting errors
GB1402613A (en) Detection and correction of errors in information words
JP3099890B2 (ja) Bch符号の誤り訂正装置
JP3398560B2 (ja) 短縮化誤り訂正復号装置
JP2935305B2 (ja) 短縮化ファイア符号の高速復号器
JP2694794B2 (ja) 誤り訂正処理方法
JP2599001B2 (ja) 誤り訂正処理回路
JPS62233932A (ja) Bch符号の復号回路
JP2585361B2 (ja) リ−ド・ソロモン符号の誤り位置と誤りパタ−ンの抽出装置
KR900001066Y1 (ko) 에러 정정용 데코오더 회로의 소거신호 계수회로
JP2823158B2 (ja) 誤り訂正装置
JP2685186B2 (ja) 誤り訂正装置
JP2553571B2 (ja) ガロア体演算装置
JP2600130B2 (ja) 誤り訂正回路
JPS6278920A (ja) フアイア符号の符号化・復号化装置
JP2710626B2 (ja) ブロック同期回路
JPS6029071A (ja) 誤り訂正装置
JPS58219850A (ja) 誤り位置検出回路
JPH05335969A (ja) 誤り訂正装置