誤り訂正装置
【発明の詳細な説明】
産業上の利用分野 本発明はPCM（パルス・コード・モジュレーション）音声の再生などの際に適用できるディジタル符号伝送における誤り訂正装置に関するものである。
従来の技術 PCM音声等のディジタル信号を伝送する際、伝送途中でのビット誤りを訂正するために送信側で誤り訂正用検査符号を付加して送信し、受信側で誤り訂正装置を用いてビット誤りを訂正する方法が用いられる。たとえば、訂正符号にはBCH符号があり、その誤り訂正装置として第４図のようなものがよく知られている。
以下、図面を参照しながら、上述した従来の誤り訂正装置の一例について説明する。
第４図に従来の誤り訂正装置のブロック図を示す。第４図４図において、41,42は除算器で、符号生成用の生成多項式を成すそれぞれ２つの既約多項式に基づいて入力信号を除算し、それぞれの剰余を出力するものである。43,44は符号変換器で、除算器41,42で得られた剰余符号を入力し、入力信号の誤りのある位置を示す誤り位置符号を出力するもので、通常ROM（リード・オンリー・メモリ）で実現される。45,46は一致検出器、47はカウンター、50はOR回路で、カウンタ47によって出力する信号の位置を計数し、一致検出器45,46で誤り位置符号とカウンタ47の出力とを比較して、出力する信号の位置が誤りである場合にそれぞれ誤り訂正信号を出力し、OR回路50によって前述の２つの誤り訂正信号の論理和がとられる。48は遅延器で、入力信号を遅延させて、誤り訂正信号とのタイミングを合せるものである。49はビット反転器で、遅延器48によって遅延された入力信号を、OR回路50で得られた誤り訂正信号でビット反転することで誤りを訂正し、出力するものである。
以上のように構成された誤り訂正装置について、BCH（15,7）符号を用いて説明する。
BCH（15,7）符号は、７ビットの情報に８ビットの誤り訂正符号を付加して15ビットで伝送し、誤り訂正装置によって伝送中に発生した符号中の２個以下の誤りを訂正できる符号である（参考文献、羽物俊秀「BCH符号による誤り訂正」，放送技術，昭58.11,p.1111）。
たとえば、BCH（15,7）符号の生成多項式は、Ｇ＝x8＋x7＋x6＋x4＋１、２つの既約多項式は、G1＝x4＋ｘ＋１、および、G2＝x4＋x3＋x2＋ｘ＋１であり、生成多項式Ｇは２つの既約多項式G1，G2を乗算して得られるものである。
第４図において、除算器41,42を、既約多項式G1，G2に基づいた除算器とすると、それぞれ、第２図および第３図３図に示すような構成になる。第２図および第３図において、21a〜21d,31a〜31dはフリップ・フロップで、信号を１クロック遅延させるものである。22a〜22b,32a〜32dは加算回路で、２を法とした加算を行うもので、EX−OR回路で実現できる。23a〜23d,33a〜33dはそれぞれの除算器の出力端子で、24,34はそれぞれ除算器の入力端子である。
第４図において、符号変換器43,44はROMで構成でき、除算器41,42が出力する剰余符号を連結したのもをROMのアドレスとし、すべての２個以下の誤りについて、そのときの除算器41,42が出力する剰余符号をアドレスとして与えたときに、その誤りの位置が出力されるようにROMのデータを設定しておく。
いま、伝送された信号が入力端子51から入力されると、入力信号は遅延器48によって１符号分（本例では15ビット分）遅延され、また、同時に入力信号は除算器41,42によって除算される。入力信号が１符号分入力されると、除算器41,42によって剰余符号が求められ、符号変換器43,44によって入力された信号中の誤りの位置を示す符号を得る。次に、除算器41,42を停止させ、カウンタ47を起動してカウンタ47で出力信号の位置をカウントしながら、遅延器48から信号を出力する。このとき、一致検出器45,46によって、符号変換器43,44の出力とカウンタ47の出力とを比較し、符号変換器43,44で示される誤りの位置とカウンタで示される出力符号の位置が一致したときに誤り訂正信号を出力し、OR回路50で論理和された誤り訂正信号によって、ビット反転器49で出力信号を反転することで誤りを訂正し、出力端子52から出力する。
なお、除算器41,42内のフリップ・フロップの初期状態をすべて零とし、入力信号は生成多項式Ｇによって生成された符号とする。
発明が解決しようとする問題点 しかしながら上記のような構成では、符号変換器に用いられるROMに、２つの剰余符号を連結したビット数のアドレスを持ち、各アドレスに誤りの位置を表現し得るだけのビット数の出力を持つROMが必要となり、ROMの容量が非常に大きく、誤り訂正装置の回路規模が大きなものになるという問題を有していた。更には、誤り訂正に用いる符号長が大きくなると、ROMの容量が符号長に大して指数関数的に増加して、誤り訂正装置の回路規模が莫大なものとなる。
たとえば、15ビットの符号長を持つBCH（15,7）符号の場合、２つの除算器の出力するそれぞれの剰余符号が４ビットでROMのアドレスは８ビットとなり、１アドレスで出力するデータのビット数は符号長15ビット中のビット位置を示すために４ビットで、そのROMが符号変換器43,44に１個づつ計２個あるため、ROMの容量は合計2048（＝２×４×28）ビット必要であり、63ビットの符号長を持つBCH（63,51）符号では、ROMの容量が49152ビット必要である。
そこで、本発明は符号変換器に用いるROMの容量を小さくし、回路規模の小さな誤り訂正装置を提供するものである。
問題を解決するための手段 上記問題点を解決するために本発明の誤り訂正装置は、２個以下の誤りを訂正する誤り訂正符号発生用の生成多項式を成す２つの既約多項式のうち原始多項式である第１の既約多項式で除算を行なう第１の除算器と、他の一方の既約多項式である第２の既約多項式で除算を行なう第２の除算器と、第１の除算器で得られた第１の剰余符号を変換して検査符号を出力する符号変換器と、第２の除算器で得られた第２の剰余符号と検査符号の比較して誤り訂正信号を出力する一致検出器とを備えたものである。
作用 本発明は上記した構成によって、符号変換器にROMを用いた場合に、ROMのアドレスとして入力する剰余符号を２つの除算器のうち一方の除算器の出力する剰余符号のみとし、一致検出器で他方の除算器の出力する剰余符号と符号変換器の出力とを比較して誤り訂正信号を発生することによって、符号変換器に用いるROMの容量を小さくでき、誤り訂正装置の回路規模を小さくすることができる。
実施例 以下本発明の一実施例の誤り訂正装置について、図面を参照しながら説明する。
第１図は本発明の誤り訂正装置の一実施例の構成を示すブロック図である。第１図において、１は除算器で、誤り訂正符号発生用の生成多項式を成す２つの既約多項式のうち原始多項式である第１の既約多項式に基づいた除算を行ない、剰余符号を出力するものである。２は除算器で、前記の２つの既約多項式うち第１の既約多項式でない方の既約多項式である第２の既約多項式に基づいた除算を行ない、剰余符号を出力するものである。３は符号変換器で、除算器１で得られた剰余符号を入力して検査符号を出力するものである。４は一致検出器で、除算器２で得られた剰余符号と検査符号との一致を検査して、誤り訂正信号を出力するものである。５は選択器で、入力信号と誤り訂正信号のいずれかを選択して、除算器１および除算器２に入力するように制御されるものである。６は遅延器で、入力信号を所定のクロックパルス数だけ遅延させ、誤り訂正信号とのタイミングをとるものである。７はビット反転器で、遅延器６によって遅延された入力信号を誤り訂正信号によって反転するもので、EX−OR回路で実現できる。
以上のように構成された誤り訂正装置について、前述されたBCH（15,7）符号を用いて説明する。
ここで、生成多項式Ｇおよび既約多項式G1，G2は前述ものと同じで、原始多項式である既約多項式は既約多項式G1であり、除算器１は既約多項式G1に基づいた除算を行なうもので、たとえば第２図に示すようなものである。また、除算器２は既約多項式G2に基づいた除算を行なうもので、たとえば第３図に示すようなものである。
いま、誤り訂正符号の先に伝送される信号から順に番号を付け、第１ビット〜第15ビットとする。また、伝送途中で第ｉビットと第ｊビットに誤りが発生した誤り訂正符号が除算器1,2に入力されたとき、除算器1,2から出力される４ビットの剰余符号をそれぞれR1（i,j），R2（i,j）とし（ただし、ｉ＜ｊ）、第ｉビットだけに誤りが発生した場合に、除算器1,2から出力される剰余符号をそれぞれR1（i,i），R2（i,i）とする。
符号変換器３はROMを用いて構成し、１≦ｉ≦15なるｉについて、R1（1,i）をROMのアドレスとし、そのアドレスにおいてR2（1,i）が出力されるようにあらかじめROMを設定しておく。ここで、除算器１では原始多項式である既約多項式に基づいて除算を行なうため、１≦ｉ≦15,1≦ｊ≦15,i≠ｊなるｉおよびｊについて、R1（1,i）≠R1（1,j）となることは容易に示される。第１表にROMに設定するデータを示す。第１表のアドレスおよびデータの剰余符号R1（1,i），R2（1,i）は左側が最小位ビットを示し、剰余符号R1（1,i）の左側のビットから順に第２図の出力端子23a〜23dの出力に、剰余符号R2（1,i）の左側のビットから順に第３図の出力端子33a〜33dの出力に対応する。なお、除算器１の出力する剰余符号が零（0000）である場合、すなわち、誤りが無い場合の処理は後述する。
ここで、２≦ｉ≦15,i≦ｊ≦15,1≦ｋ≦15なるi,jおよびｋにおいて、除算器１からR1（i,j）なる剰余符号が出力された場合、R1（i,j）＝R1（1,k）なる剰余符号R1（1,k）が存在し、符号変換器３（ROM）は剰余符号R1（1,k）の入力で検査符号としてR2（1,k）を出力する。誤り訂正符号の定義より、R1（i,j）＝R1（1,k）とR2（i,j）＝R2（1,k）は同時に成り立たないため、剰余符号R1（i,j）を符号変換器３で変換して得られた検査符号R2（1,k）と除算器２で得られた剰余符号R2（i,j）とは一致せず、一致検出器４からは誤り訂正信号が出力されない。
以下に、第２ビットおよび第６ビットに誤りが生じた信号が入力された場合を仮定して本発明の誤り訂正装置の動作を説明する。
まず、除算器1,2内のシフトレジスタをすべて零にし、入力端子８からの入力信号が除算器1,2に入力されるように選択器５を制御する。
次に、入力端子８から入力信号を遅延器６と、選択器５を経て除算器1,2とに与える。除算器1,2と遅延器６とを動作させながら順次信号を入力し、信号が１符号分入力されると、選択器５を制御し、一致検出器４で得られる誤り訂正信号が除算器1,2に入力されるようにする。入力信号は、遅延器１によって１符号分遅延して出力され、以後順次出力される。
信号が１符号分入力された時点において、除算器1,2からそれぞれR1（2,6），R2（2,6）なる剰余符号が出力され、符号変換器３によってR1（2,6）を変換した検査符号が一致検出器４に与えられる。この場合、符号変換器３によってR1（2,6）を変換した検査符号とR2（2,6）は一致しないため誤り訂正信号は出力されず、遅延器６から出力された第１ビットの信号はビット反転器７を経てそのまま出力端子９から出力される。
続いて、遅延器６および除算器1,2を１クロック動作させると、遅延器６から第２ビットの信号が出力され、除算器1,2からはそれぞれR1（1,5），R2（1,5）なる剰余符号が出力されることになる。このときの除算器の動作は、第２図，第３図に示す除算器の回路図から容易に確かめられる。たとえば、除算器１において前述の動作の場合、剰余符号R1（2,6）は1110すなわち第２図におけるフリップ・フロップ21a〜21dの状態はそれぞれ1,1,1,0で、一致検出器４からは誤り訂正信号が出力されていないため除算器１の入力は０であり、その状態から除算器を１クロック動作させると第２図におけるフリップ・フロップ21a〜21dの状態はそれぞれ0,1,1,1となり、剰余符号は0111すなわちR1（1,5）となることがわかる。除算器２の動作についても第３図を用いて同様に確かめられ、また、以下の説明において除算器の詳細な動作は省略する。この場合、符号変換器３によってR1（1,5）を変換した検査符号とR2（1,5）は一致し、誤り訂正信号が出力され、誤り訂正信号によって遅延器６から出力された第２ビットの信号はビット反転器７で反転され、誤りが訂正されて出力端子９から出力される。
続いて、遅延器６および除算器1,2を１クロック動作させると、遅延器６から第３ビットの信号が出力され、除算器1,2からはそれぞれR1（4,4），R2（4,4）なる剰余符号が出力されることになる。この除算器1,2の動作では、先の誤り訂正信号が選択器５を経て除算器1,2に入力されるため、第２図，第３図における除算器の入力端子24,34には１が入力されている。この場合、符号変換器３によってR1（4,4）を変換した検査符号R2（4,4）は一致しないため誤り訂正信号は出力されず、遅延器６から出力された第３ビットの信号はビット反転器７を経てそのまま出力端子９から出力される。同様の動作で、第4,第５ビットの信号は出力端子９からそのまま出力される。
続いて、遅延器６および除算器1,2を１クロック動作させると、遅延器６から第６ビットの信号が出力され、除算器1,2からはそれぞれR1（1,1），R2（1,1）なる剰余符号が出力されることになる。この場合、符号変換器３によってR1（1,1）を変換した検査符号とR2（1,1）は一致し、誤り訂正信号は出力され、誤り訂正信号によって遅延器６から出力された第６ビットの信号はビット反転器７で反転され、誤りが訂正されて出力端子９から出力される。また誤り訂正信号は選択器５を経て除算器1,2に入力され、剰余符号は零になり、以後、誤りがない状態を示す。
続いて、遅延器６および除算器1,2を１クロック動作させると、遅延器６から第７ビットの信号が出力され、除算器1,2からはそれぞれ零符号が出力されることになる。この場合、一致検出器から誤り訂正信号が出力されなくなり、遅延器６から出力された第７ビットの信号はビット反転器７を経てそのまま出力端子９から出力される。以後同様の動作で、第８ビット〜第15ビッイの信号は出力端子９からそのまま出力され、誤り訂正は完了する。
また、前述の第３ビット以後の誤り訂正装置の動作から、符号中の１ビットだけが誤った場合も正しく訂正できることがわかる。
なお、本実施例において、誤りのない場合または誤りが途中ですべて訂正された場合、すなわち除算器1,2の出力する剰余符号が零である場合に誤り訂正信号を出力しないようにするため、符号変換器３は除算器１の出力する剰余符号が零であるとき検査符号と合わせて訂正制御信号を出力し、一致検出器４で誤り訂正信号を出力しないようにしたり、除算器１の出力する剰余符号が零であるときに符号変換器３から検査符号として零以外の符号を出力するようにし、誤りのないときに一致検出器で除算器２の剰余符号（零）と検査符号が一致しないようにする。
以上のように誤り訂正装置を本実施例のような構成にすれば、符号変換器にROMを用いた場合に、ROMのアドレスとして入力する剰余符号を１つとし、一致検出器で残りの剰余符号と符号変換器の出力とを比較して誤り訂正信号を発生することによって、符号変換器に用いるROMの容量を小さくでき、誤り訂正装置の回路規模が小さくすることができる。
たとえば、15ビットの符号長をもつBCH（15,7）符号の場合、剰余符号は４ビットでROMのアドレスは４ビットとなり、１アドレスで出力するデータのビット数は４ビットであるため、ROMの容量は合計64（＝４×24）ビットあればよく、本発明のROM容量を極めて小さくするものであり、更には、63ビットの符号長を持つBCH（63,51）符号では、ROMの容量が384ビットあればよく、誤り訂正符号の符号長が大きいほど本発明の効果は顕著になる。
第２表に、誤り訂正符号の符号長に対し、第４図に示される従来の誤り訂正装置および第１図に示される本発明の誤り訂正装置の符号変換器に用いられるROMの容量を示す。第２表からわかるように本発明の誤り訂正装置はROMの容量を極めて小さくでき、更に、誤り訂正信号の符号長が大きくなるほど本発明の効果は顕著になる。
発明の効果 以上のように本発明は、２個以下の誤りを訂正する誤り訂正符号発生用の生成多項式を成す２つの既約多項式のうち原始多項式である第１の既約多項式で除算を行なう第１の除算器と、他の一方の既約多項式である第２の既約多項式で除算を行なう第２の除算器と、第１の除算器で得られた剰余符号を変換して検査符号を出力する符号変換器と、第２の除算器で得られた剰余符号と検査符号の一致を検査して誤り訂正信号を出力する一致検出器とを備えることにより、符号変換器に用いるROMの容量を極めて小さくすることができ、回路規模の極めて小さな誤り訂正装置を提供することができる。
【図面の簡単な説明】
第１図は本発明による誤り訂正装置の構成を示すブロック図、第２図および第３図は第１図または第４図の誤り訂正装置に用いられる除算器の構成を示す回路図、第４図R>図は従来例による誤り訂正装置の構成を示すブロック図である。
１……原始多項式なる既約多項式に基づいた除算器、２……残りの既約多項式に基づいた除算器、３……符号変換器、４……一致検出器、５……選択器、6,48……遅延器、7,49……ビット反転器、21a,21b,31a〜31d……フリップ・フロップ、22a〜22d,32a〜32d……加算器、41,42……除算器、43,44……符号変換器、45,46……一致検出器、47……カウンタ。
産業上の利用分野 本発明はPCM（パルス・コード・モジュレーション）音声の再生などの際に適用できるディジタル符号伝送における誤り訂正装置に関するものである。
従来の技術 PCM音声等のディジタル信号を伝送する際、伝送途中でのビット誤りを訂正するために送信側で誤り訂正用検査符号を付加して送信し、受信側で誤り訂正装置を用いてビット誤りを訂正する方法が用いられる。たとえば、訂正符号にはBCH符号があり、その誤り訂正装置として第４図のようなものがよく知られている。
以下、図面を参照しながら、上述した従来の誤り訂正装置の一例について説明する。
第４図に従来の誤り訂正装置のブロック図を示す。第４図４図において、41,42は除算器で、符号生成用の生成多項式を成すそれぞれ２つの既約多項式に基づいて入力信号を除算し、それぞれの剰余を出力するものである。43,44は符号変換器で、除算器41,42で得られた剰余符号を入力し、入力信号の誤りのある位置を示す誤り位置符号を出力するもので、通常ROM（リード・オンリー・メモリ）で実現される。45,46は一致検出器、47はカウンター、50はOR回路で、カウンタ47によって出力する信号の位置を計数し、一致検出器45,46で誤り位置符号とカウンタ47の出力とを比較して、出力する信号の位置が誤りである場合にそれぞれ誤り訂正信号を出力し、OR回路50によって前述の２つの誤り訂正信号の論理和がとられる。48は遅延器で、入力信号を遅延させて、誤り訂正信号とのタイミングを合せるものである。49はビット反転器で、遅延器48によって遅延された入力信号を、OR回路50で得られた誤り訂正信号でビット反転することで誤りを訂正し、出力するものである。
以上のように構成された誤り訂正装置について、BCH（15,7）符号を用いて説明する。
BCH（15,7）符号は、７ビットの情報に８ビットの誤り訂正符号を付加して15ビットで伝送し、誤り訂正装置によって伝送中に発生した符号中の２個以下の誤りを訂正できる符号である（参考文献、羽物俊秀「BCH符号による誤り訂正」，放送技術，昭58.11,p.1111）。
たとえば、BCH（15,7）符号の生成多項式は、Ｇ＝x8＋x7＋x6＋x4＋１、２つの既約多項式は、G1＝x4＋ｘ＋１、および、G2＝x4＋x3＋x2＋ｘ＋１であり、生成多項式Ｇは２つの既約多項式G1，G2を乗算して得られるものである。
第４図において、除算器41,42を、既約多項式G1，G2に基づいた除算器とすると、それぞれ、第２図および第３図３図に示すような構成になる。第２図および第３図において、21a〜21d,31a〜31dはフリップ・フロップで、信号を１クロック遅延させるものである。22a〜22b,32a〜32dは加算回路で、２を法とした加算を行うもので、EX−OR回路で実現できる。23a〜23d,33a〜33dはそれぞれの除算器の出力端子で、24,34はそれぞれ除算器の入力端子である。
第４図において、符号変換器43,44はROMで構成でき、除算器41,42が出力する剰余符号を連結したのもをROMのアドレスとし、すべての２個以下の誤りについて、そのときの除算器41,42が出力する剰余符号をアドレスとして与えたときに、その誤りの位置が出力されるようにROMのデータを設定しておく。
いま、伝送された信号が入力端子51から入力されると、入力信号は遅延器48によって１符号分（本例では15ビット分）遅延され、また、同時に入力信号は除算器41,42によって除算される。入力信号が１符号分入力されると、除算器41,42によって剰余符号が求められ、符号変換器43,44によって入力された信号中の誤りの位置を示す符号を得る。次に、除算器41,42を停止させ、カウンタ47を起動してカウンタ47で出力信号の位置をカウントしながら、遅延器48から信号を出力する。このとき、一致検出器45,46によって、符号変換器43,44の出力とカウンタ47の出力とを比較し、符号変換器43,44で示される誤りの位置とカウンタで示される出力符号の位置が一致したときに誤り訂正信号を出力し、OR回路50で論理和された誤り訂正信号によって、ビット反転器49で出力信号を反転することで誤りを訂正し、出力端子52から出力する。
なお、除算器41,42内のフリップ・フロップの初期状態をすべて零とし、入力信号は生成多項式Ｇによって生成された符号とする。
発明が解決しようとする問題点 しかしながら上記のような構成では、符号変換器に用いられるROMに、２つの剰余符号を連結したビット数のアドレスを持ち、各アドレスに誤りの位置を表現し得るだけのビット数の出力を持つROMが必要となり、ROMの容量が非常に大きく、誤り訂正装置の回路規模が大きなものになるという問題を有していた。更には、誤り訂正に用いる符号長が大きくなると、ROMの容量が符号長に大して指数関数的に増加して、誤り訂正装置の回路規模が莫大なものとなる。
たとえば、15ビットの符号長を持つBCH（15,7）符号の場合、２つの除算器の出力するそれぞれの剰余符号が４ビットでROMのアドレスは８ビットとなり、１アドレスで出力するデータのビット数は符号長15ビット中のビット位置を示すために４ビットで、そのROMが符号変換器43,44に１個づつ計２個あるため、ROMの容量は合計2048（＝２×４×28）ビット必要であり、63ビットの符号長を持つBCH（63,51）符号では、ROMの容量が49152ビット必要である。
そこで、本発明は符号変換器に用いるROMの容量を小さくし、回路規模の小さな誤り訂正装置を提供するものである。
問題を解決するための手段 上記問題点を解決するために本発明の誤り訂正装置は、２個以下の誤りを訂正する誤り訂正符号発生用の生成多項式を成す２つの既約多項式のうち原始多項式である第１の既約多項式で除算を行なう第１の除算器と、他の一方の既約多項式である第２の既約多項式で除算を行なう第２の除算器と、第１の除算器で得られた第１の剰余符号を変換して検査符号を出力する符号変換器と、第２の除算器で得られた第２の剰余符号と検査符号の比較して誤り訂正信号を出力する一致検出器とを備えたものである。
作用 本発明は上記した構成によって、符号変換器にROMを用いた場合に、ROMのアドレスとして入力する剰余符号を２つの除算器のうち一方の除算器の出力する剰余符号のみとし、一致検出器で他方の除算器の出力する剰余符号と符号変換器の出力とを比較して誤り訂正信号を発生することによって、符号変換器に用いるROMの容量を小さくでき、誤り訂正装置の回路規模を小さくすることができる。
実施例 以下本発明の一実施例の誤り訂正装置について、図面を参照しながら説明する。
第１図は本発明の誤り訂正装置の一実施例の構成を示すブロック図である。第１図において、１は除算器で、誤り訂正符号発生用の生成多項式を成す２つの既約多項式のうち原始多項式である第１の既約多項式に基づいた除算を行ない、剰余符号を出力するものである。２は除算器で、前記の２つの既約多項式うち第１の既約多項式でない方の既約多項式である第２の既約多項式に基づいた除算を行ない、剰余符号を出力するものである。３は符号変換器で、除算器１で得られた剰余符号を入力して検査符号を出力するものである。４は一致検出器で、除算器２で得られた剰余符号と検査符号との一致を検査して、誤り訂正信号を出力するものである。５は選択器で、入力信号と誤り訂正信号のいずれかを選択して、除算器１および除算器２に入力するように制御されるものである。６は遅延器で、入力信号を所定のクロックパルス数だけ遅延させ、誤り訂正信号とのタイミングをとるものである。７はビット反転器で、遅延器６によって遅延された入力信号を誤り訂正信号によって反転するもので、EX−OR回路で実現できる。
以上のように構成された誤り訂正装置について、前述されたBCH（15,7）符号を用いて説明する。
ここで、生成多項式Ｇおよび既約多項式G1，G2は前述ものと同じで、原始多項式である既約多項式は既約多項式G1であり、除算器１は既約多項式G1に基づいた除算を行なうもので、たとえば第２図に示すようなものである。また、除算器２は既約多項式G2に基づいた除算を行なうもので、たとえば第３図に示すようなものである。
いま、誤り訂正符号の先に伝送される信号から順に番号を付け、第１ビット〜第15ビットとする。また、伝送途中で第ｉビットと第ｊビットに誤りが発生した誤り訂正符号が除算器1,2に入力されたとき、除算器1,2から出力される４ビットの剰余符号をそれぞれR1（i,j），R2（i,j）とし（ただし、ｉ＜ｊ）、第ｉビットだけに誤りが発生した場合に、除算器1,2から出力される剰余符号をそれぞれR1（i,i），R2（i,i）とする。
符号変換器３はROMを用いて構成し、１≦ｉ≦15なるｉについて、R1（1,i）をROMのアドレスとし、そのアドレスにおいてR2（1,i）が出力されるようにあらかじめROMを設定しておく。ここで、除算器１では原始多項式である既約多項式に基づいて除算を行なうため、１≦ｉ≦15,1≦ｊ≦15,i≠ｊなるｉおよびｊについて、R1（1,i）≠R1（1,j）となることは容易に示される。第１表にROMに設定するデータを示す。第１表のアドレスおよびデータの剰余符号R1（1,i），R2（1,i）は左側が最小位ビットを示し、剰余符号R1（1,i）の左側のビットから順に第２図の出力端子23a〜23dの出力に、剰余符号R2（1,i）の左側のビットから順に第３図の出力端子33a〜33dの出力に対応する。なお、除算器１の出力する剰余符号が零（0000）である場合、すなわち、誤りが無い場合の処理は後述する。
ここで、２≦ｉ≦15,i≦ｊ≦15,1≦ｋ≦15なるi,jおよびｋにおいて、除算器１からR1（i,j）なる剰余符号が出力された場合、R1（i,j）＝R1（1,k）なる剰余符号R1（1,k）が存在し、符号変換器３（ROM）は剰余符号R1（1,k）の入力で検査符号としてR2（1,k）を出力する。誤り訂正符号の定義より、R1（i,j）＝R1（1,k）とR2（i,j）＝R2（1,k）は同時に成り立たないため、剰余符号R1（i,j）を符号変換器３で変換して得られた検査符号R2（1,k）と除算器２で得られた剰余符号R2（i,j）とは一致せず、一致検出器４からは誤り訂正信号が出力されない。
以下に、第２ビットおよび第６ビットに誤りが生じた信号が入力された場合を仮定して本発明の誤り訂正装置の動作を説明する。
まず、除算器1,2内のシフトレジスタをすべて零にし、入力端子８からの入力信号が除算器1,2に入力されるように選択器５を制御する。
次に、入力端子８から入力信号を遅延器６と、選択器５を経て除算器1,2とに与える。除算器1,2と遅延器６とを動作させながら順次信号を入力し、信号が１符号分入力されると、選択器５を制御し、一致検出器４で得られる誤り訂正信号が除算器1,2に入力されるようにする。入力信号は、遅延器１によって１符号分遅延して出力され、以後順次出力される。
信号が１符号分入力された時点において、除算器1,2からそれぞれR1（2,6），R2（2,6）なる剰余符号が出力され、符号変換器３によってR1（2,6）を変換した検査符号が一致検出器４に与えられる。この場合、符号変換器３によってR1（2,6）を変換した検査符号とR2（2,6）は一致しないため誤り訂正信号は出力されず、遅延器６から出力された第１ビットの信号はビット反転器７を経てそのまま出力端子９から出力される。
続いて、遅延器６および除算器1,2を１クロック動作させると、遅延器６から第２ビットの信号が出力され、除算器1,2からはそれぞれR1（1,5），R2（1,5）なる剰余符号が出力されることになる。このときの除算器の動作は、第２図，第３図に示す除算器の回路図から容易に確かめられる。たとえば、除算器１において前述の動作の場合、剰余符号R1（2,6）は1110すなわち第２図におけるフリップ・フロップ21a〜21dの状態はそれぞれ1,1,1,0で、一致検出器４からは誤り訂正信号が出力されていないため除算器１の入力は０であり、その状態から除算器を１クロック動作させると第２図におけるフリップ・フロップ21a〜21dの状態はそれぞれ0,1,1,1となり、剰余符号は0111すなわちR1（1,5）となることがわかる。除算器２の動作についても第３図を用いて同様に確かめられ、また、以下の説明において除算器の詳細な動作は省略する。この場合、符号変換器３によってR1（1,5）を変換した検査符号とR2（1,5）は一致し、誤り訂正信号が出力され、誤り訂正信号によって遅延器６から出力された第２ビットの信号はビット反転器７で反転され、誤りが訂正されて出力端子９から出力される。
続いて、遅延器６および除算器1,2を１クロック動作させると、遅延器６から第３ビットの信号が出力され、除算器1,2からはそれぞれR1（4,4），R2（4,4）なる剰余符号が出力されることになる。この除算器1,2の動作では、先の誤り訂正信号が選択器５を経て除算器1,2に入力されるため、第２図，第３図における除算器の入力端子24,34には１が入力されている。この場合、符号変換器３によってR1（4,4）を変換した検査符号R2（4,4）は一致しないため誤り訂正信号は出力されず、遅延器６から出力された第３ビットの信号はビット反転器７を経てそのまま出力端子９から出力される。同様の動作で、第4,第５ビットの信号は出力端子９からそのまま出力される。
続いて、遅延器６および除算器1,2を１クロック動作させると、遅延器６から第６ビットの信号が出力され、除算器1,2からはそれぞれR1（1,1），R2（1,1）なる剰余符号が出力されることになる。この場合、符号変換器３によってR1（1,1）を変換した検査符号とR2（1,1）は一致し、誤り訂正信号は出力され、誤り訂正信号によって遅延器６から出力された第６ビットの信号はビット反転器７で反転され、誤りが訂正されて出力端子９から出力される。また誤り訂正信号は選択器５を経て除算器1,2に入力され、剰余符号は零になり、以後、誤りがない状態を示す。
続いて、遅延器６および除算器1,2を１クロック動作させると、遅延器６から第７ビットの信号が出力され、除算器1,2からはそれぞれ零符号が出力されることになる。この場合、一致検出器から誤り訂正信号が出力されなくなり、遅延器６から出力された第７ビットの信号はビット反転器７を経てそのまま出力端子９から出力される。以後同様の動作で、第８ビット〜第15ビッイの信号は出力端子９からそのまま出力され、誤り訂正は完了する。
また、前述の第３ビット以後の誤り訂正装置の動作から、符号中の１ビットだけが誤った場合も正しく訂正できることがわかる。
なお、本実施例において、誤りのない場合または誤りが途中ですべて訂正された場合、すなわち除算器1,2の出力する剰余符号が零である場合に誤り訂正信号を出力しないようにするため、符号変換器３は除算器１の出力する剰余符号が零であるとき検査符号と合わせて訂正制御信号を出力し、一致検出器４で誤り訂正信号を出力しないようにしたり、除算器１の出力する剰余符号が零であるときに符号変換器３から検査符号として零以外の符号を出力するようにし、誤りのないときに一致検出器で除算器２の剰余符号（零）と検査符号が一致しないようにする。
以上のように誤り訂正装置を本実施例のような構成にすれば、符号変換器にROMを用いた場合に、ROMのアドレスとして入力する剰余符号を１つとし、一致検出器で残りの剰余符号と符号変換器の出力とを比較して誤り訂正信号を発生することによって、符号変換器に用いるROMの容量を小さくでき、誤り訂正装置の回路規模が小さくすることができる。
たとえば、15ビットの符号長をもつBCH（15,7）符号の場合、剰余符号は４ビットでROMのアドレスは４ビットとなり、１アドレスで出力するデータのビット数は４ビットであるため、ROMの容量は合計64（＝４×24）ビットあればよく、本発明のROM容量を極めて小さくするものであり、更には、63ビットの符号長を持つBCH（63,51）符号では、ROMの容量が384ビットあればよく、誤り訂正符号の符号長が大きいほど本発明の効果は顕著になる。
第２表に、誤り訂正符号の符号長に対し、第４図に示される従来の誤り訂正装置および第１図に示される本発明の誤り訂正装置の符号変換器に用いられるROMの容量を示す。第２表からわかるように本発明の誤り訂正装置はROMの容量を極めて小さくでき、更に、誤り訂正信号の符号長が大きくなるほど本発明の効果は顕著になる。
発明の効果 以上のように本発明は、２個以下の誤りを訂正する誤り訂正符号発生用の生成多項式を成す２つの既約多項式のうち原始多項式である第１の既約多項式で除算を行なう第１の除算器と、他の一方の既約多項式である第２の既約多項式で除算を行なう第２の除算器と、第１の除算器で得られた剰余符号を変換して検査符号を出力する符号変換器と、第２の除算器で得られた剰余符号と検査符号の一致を検査して誤り訂正信号を出力する一致検出器とを備えることにより、符号変換器に用いるROMの容量を極めて小さくすることができ、回路規模の極めて小さな誤り訂正装置を提供することができる。
【図面の簡単な説明】
第１図は本発明による誤り訂正装置の構成を示すブロック図、第２図および第３図は第１図または第４図の誤り訂正装置に用いられる除算器の構成を示す回路図、第４図R>図は従来例による誤り訂正装置の構成を示すブロック図である。
１……原始多項式なる既約多項式に基づいた除算器、２……残りの既約多項式に基づいた除算器、３……符号変換器、４……一致検出器、５……選択器、6,48……遅延器、7,49……ビット反転器、21a,21b,31a〜31d……フリップ・フロップ、22a〜22d,32a〜32d……加算器、41,42……除算器、43,44……符号変換器、45,46……一致検出器、47……カウンタ。
【特許請求の範囲】
１．２個以下の誤り訂正を行なう誤り訂正装置であって、２個以下の誤りを訂正する誤り訂正符号発生用の生成多項式を成す２つの既約多項式のうち原始多項式である第１の既約多項式で除算を行なう第１の除算手段と、前記第１の既約多項式でない方の既約多項式である第２の既約多項式で除算を行なう第２の除算手段と、前記第１の除算手段で得られた第１の剰余符号を変換して検査符号を出力する符号変換手段と、前記第２の除算手段で得られた第２の剰余符号と前記検査符号とを比較して誤り訂正信号を出力する一致検出手段と、入力信号と前記誤り訂正信号のいずれかを選択して前記第１の除算手段および前記第２の除算手段に入力するように制御される選択手段と、前記入力信号を所定のクロックパルス数だけ遅延させる遅延手段と、前記遅延手段の出力信号を前記誤り訂正信号で反転させるビット反転手段とを備え、前記符号変換手段が所定のビットないし前記所定のビットと他の１ビットが誤った場合に前記第１の除算手段に得られる第１の剰余符号を前記第２の除算手段に得られる第２の剰余符号に変換し検査符号として出力することを特徴とする誤り訂正装置。
１．２個以下の誤り訂正を行なう誤り訂正装置であって、２個以下の誤りを訂正する誤り訂正符号発生用の生成多項式を成す２つの既約多項式のうち原始多項式である第１の既約多項式で除算を行なう第１の除算手段と、前記第１の既約多項式でない方の既約多項式である第２の既約多項式で除算を行なう第２の除算手段と、前記第１の除算手段で得られた第１の剰余符号を変換して検査符号を出力する符号変換手段と、前記第２の除算手段で得られた第２の剰余符号と前記検査符号とを比較して誤り訂正信号を出力する一致検出手段と、入力信号と前記誤り訂正信号のいずれかを選択して前記第１の除算手段および前記第２の除算手段に入力するように制御される選択手段と、前記入力信号を所定のクロックパルス数だけ遅延させる遅延手段と、前記遅延手段の出力信号を前記誤り訂正信号で反転させるビット反転手段とを備え、前記符号変換手段が所定のビットないし前記所定のビットと他の１ビットが誤った場合に前記第１の除算手段に得られる第１の剰余符号を前記第２の除算手段に得られる第２の剰余符号に変換し検査符号として出力することを特徴とする誤り訂正装置。
【第１図】
【第２図】
【第３図】
【第４図】
【第２図】
【第３図】
【第４図】
【特許番号】第２６８５１８０号
【登録日】平成９年（１９９７）８月１５日
【発行日】平成９年（１９９７）１２月３日
【国際特許分類】
【出願番号】特願昭６２−８９４７５
【出願日】昭和６２年（１９８７）４月１０日
【公開番号】特開昭６３−２５４８２９
【公開日】昭和６３年（１９８８）１０月２１日
【審判番号】平８−１２００５
【出願人】（９９９９９９９９９）松下電器産業株式会社
【合議体】
【参考文献】
【文献】特開 昭５８−１７５３３４（ＪＰ，Ａ）
【文献】特開 昭６１−２８８５２４（ＪＰ，Ａ）
【文献】特開 昭５６−４４９７４（ＪＰ，Ａ）
【文献】特開 昭５５−１０９０５４（ＪＰ，Ａ）
【登録日】平成９年（１９９７）８月１５日
【発行日】平成９年（１９９７）１２月３日
【国際特許分類】
【出願日】昭和６２年（１９８７）４月１０日
【公開番号】特開昭６３−２５４８２９
【公開日】昭和６３年（１９８８）１０月２１日
【審判番号】平８−１２００５
【出願人】（９９９９９９９９９）松下電器産業株式会社
【合議体】
【参考文献】
【文献】特開 昭５８−１７５３３４（ＪＰ，Ａ）
【文献】特開 昭６１−２８８５２４（ＪＰ，Ａ）
【文献】特開 昭５６−４４９７４（ＪＰ，Ａ）
【文献】特開 昭５５−１０９０５４（ＪＰ，Ａ）
[ Back to top ]