JPH0482325A - Ｂｃｈ符号の誤り訂正装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） この発明は、２誤り訂正可能なＢＣＨ符号の誤り訂正装
置に関し、特に１誤り訂正可能なＢＣＨ符号の誤り訂正
を行うこともできるＢＣＨ符号の誤り訂正装置に関する
。

（従来の技術） 衛星放送では、テレビ音声をディジタル化して伝送して
おり、直接受信による高画質と合せて、高音質の放送を
視聴者に提供している。このテレビ音声のディジタル音
声伝送では、ＢＣＨ符号と呼ばれる誤り訂正符号が用い
られている。

ＢＣ［（符号は、巡回符号に属する符号であり、ＢＣＨ
符号の符号器と復号器は生成多項式Ｇ（Ｘ）を除数とす
る割り算回路になっている。そして、求めるものは商で
はなくてその余りであるのが特徴となっている。ＢＣＨ
符号の中で２誤り訂正可能なものは、生成多項式Ｇ　（
Ｘ）として、αを根として持つ最小多項式Ｇ１　（Ｘ）
とＧ３を根として持つ最小多項式Ｇ３　　（Ｘ）との積
、即ち、Ｇ（χ）＝０１　　（Ｘ）　　・Ｇ３（Ｘ）と
して得られる。送信側では、情報ビットを生成多項式〇
（Ｘ）で割って、その余りを検査ビットとして情報ビ・
ソトとともに送っている。この情報ビットと検査ビット
からなる送信符号語（ＢＣＨ符号）をＲ（Ｘ）とする。

ここで、伝送系の雑音によってＢＣＨ符号に誤りを生じ
る場合がある。この雑音系列をＥ　（Ｘ）と仮定すると
、受信符号語Ｒ′　（Ｘ＞は、Ｒ’　　（Ｘ）＝Ｒ（Ｘ
）　十Ｅ　（Ｘ）−■と表すことができる。

式■において、受信符号語Ｒ′　（χ）に誤りがなけれ
ば、Ｅ　（Ｘ）　−〇となって、Ｒ’　　（Ｘ）は最小
多項式Ｃｚ　　（Ｘ）及びＧ３　　（Ｘ）で割り切れる
。一方、受信符号語Ｒ’　　（Ｘ）は、０でないＥ（Ｘ
）を含む場合に、割り切れず余りを生じる。

これを式に表すと、 となる。

即ち、受信符号語Ｒ”　　（Ｘ）を最小多項式Ｇ＋　　
（Ｘ）及びＧ３　　（Ｘ）で割ると余りはそれぞれＳｌ
及びＳ３となる。これらｓｌ　、ｓ３はシンドロームと
呼ばれている。今、２個のビット誤りが受信符号語Ｒ”
　　（Ｘ）のｉ桁目、ｊ桁目に発生したと仮定し、γｉ
とγＪを未知の拡大ガロア体ＧＦ（２）の元として、 元（Ｇ０　Ｇ１．α　、α　、・・・）を代入していけ
ば、根はγｉ＝α　、γｊ−α４として直ちに求められ
る。このときのα　、Ｇ１のそれぞれの次数ｉ、ｊが誤
りの位置となる。これらの位置のビットを反転させれば
、受信符号語の誤り訂正を行うことができる。

一方、受信符号語の誤りが１つの場合は、と表すことが
できる。連立方程式Ｑ・を変形すると、 となる。とすると、γｉとγｊは共に以下に示す多項式
（誤り位置方程式）σ（Ｘ）の根として与えられる。

σ（Ｘ）＝Ｘ　　＋ｓＩ　ｘ十（Ｓｌ　”　十Ｓ３／５
ｔ）＝Ｏ・・・■ このような式■に拡大ガロア体ＧＦ（２）のとなる。と
すると、ｓ、　３＝ｓ３となり、Ｓ１２十Ｓ３／５１＝
Ｏとなる。この式を式■に代入すると、 σ（Ｘ）二ｘ２＋ｓ、ｘ＝ｏ・・・■ となる。ここでＸ＝０は拡大ガロア体ＧＦ（２）に含ま
れないので、 σ（Ｘ）＝Ｘ＋Ｓｔ　＝Ｏ・・・■ となる。とすると、２誤りの時と同様に、式■に拡大ガ
ロア体ＧＦ　（２１）の元（α　、α１Ｇ２　Ｇ３　・
・・）を代入していけば、根はγα　として直ちに求め
られる。このときの次数ｉが誤りの位置となる。

復号過程は、上に述べたように、シンドロームＳ＋　　
（Ｘ＞、Ｓ３　　（Ｘ）を求めるシンドローム演算の過
程、式■に示した位置方程式σ（Ｘ）の係数を求める演
算の過程、式■に拡大ガロア体ＧＦ（２）の元を代入し
て誤り位置を求める演算の過程、誤り位置のビットを反
転することにより誤り訂正を行う過程の４段階に分けら
れる。これらの過程を実現する方法は種々考案されてい
る。ここで、Ｓ３／Ｓ＋の演算は割り算なので困難であ
る。これに対応して特公昭５５−２５７４６号公報に記
載されているように、Ｓ３／Ｓ、の演算結果をＲＯＭに
書き込んでおく方法がある。また、別の方法として、Ｓ
ａ／Ｓ＋の演算を避けるために、特開昭６１−２８１７
２０号公報に記載されているように、誤り位置方程式の
項すべてに８１をｍｔｒｆｃａ　（Ｘ）＝Ｓ、Ｘ２　＋
Ｓ、　２Ｘ＋（Ｓ１３＋Ｓ３　）＝Ｏとして解く方法も
ある。

方、誤りの位置方程式σ（Ｘ）を解く方法とじては、チ
ェーンサーチ法と呼ばれるものがある。これは、上記拡
大ガロア体ＧＦ（２）の元（Ｇ０゜　、　　　　３ １　Ｇ２．α　、・・・）をを次数の高い方から順次代
入して行き根を求めることである。そして、この根を求
めると同時に一部バッファに蓄えておいた受信符号語Ｒ
′　（Ｘ）を順次読出しながら誤りの訂正を行っている
。

従来、このような方法を用いて復号過程の簡略化を行っ
ていた。ここで、２誤り訂正可能なＢＣＨ符号と１誤り
訂正可能なＢＣＨ符号は、その訂正能力が異なるだけで
、それらの間に関連を持たせることかできる。１誤り訂
正可能なりＣ）（符号でフォーマットされたディジタル
信号の送受信システムがあるとき、誤り訂正能力を強化
するためデータビットの一部を誤り訂正符号に割き２誤
り訂正可能なシステムにすることは簡単である。すなわ
ち、１誤り訂正可能なＢＣＨ符号の生成多項式を２誤り
訂正可能なりＣＦ（符号の生成多項式の一部に（すなわ
ち、上述のＧ＋（Ｘ））とすることができる。１誤り訂
正可能なＢＣＨ符号と２誤り訂正可能なＢＣＨ符号では
、生成生成多項式が異なるが、この２誤り訂正可能なＢ
ＣＨ符号はその生成多項式の一部に０１　（Ｘ）を待つ
ことにより、従来の１誤り訂正符号の受信装置で復号し
ても１誤りについては問題なく訂正することができる。

ここで、従来の２誤り訂正符号の受信装置で１誤り訂正
可能なＢＣＨ符号を受信する場合、送信符号Ｒ（Ｘ）は
、あくまで０１　（Ｘ）で割りきれるのであって、Ｇ３
　　（Ｘ）で割りきれるとはかぎらない。このため、シ
ンドローム演算＝Ｒ，”（Ｇ３）は不正確な値となる。

これに対応して、２誤り訂正可能なＢＣＨ符号の復号可
能な受信装置に、伝送されているデータが１誤り訂正符
号が、２誤り訂正可能なＢＣＨ符号かを送信側が受信側
に知らせる手段を設るとともに、１誤り訂正可能なＢＣ
Ｈ符号用の誤り位置位置演算回路を２誤り訂正可能なＢ
ＣＨ符号用のものと別に設け、１誤り訂正可能なＢＣＨ
符号を受信した場合に１誤り訂正可能なＢＣＨ符号用の
誤り位置演算回路を切換え選択して、σ（Ｘ）−〇を求
める方法も考えられているが、これでは、回路が複雑で
高価なものになってしまう。

（発明が解決しようとする課題） 前記した従来のＢＣＨ符号誤り訂正装置ては、２誤り訂
正可能なＢＣＨ符号の受信装置で、１誤り訂正可能なＢ
ＣＨ符号を受信する場合、シンドローム５ａ＝Ｒ’（Ｇ
３）は不正確な値となるので、１誤り訂正可能なＢＣＨ
符号用の誤り位置位置演算回路を２誤り訂正可能なＢＣ
Ｈ符号用のものと別に設なければならず、回路が複雑て
高価なものになってしまう。

そこで、本発明は、前記の問題点を除去し、１つの誤り
位置演算回路で、１誤り訂正可能なりＣＦ（符号の１誤
り訂正と、２誤り訂正可能なＢＣＨ符号の２誤り訂正と
を行うことができるＢＣＨ符号誤り訂正装置の提供を目
的とする。

［発明の構成］ （課題を解決するための手段） 第１の発明は、２誤り訂正可能なＢＣＨ符号の誤り訂正
装置であって、ＢＣＨ符号の受信系列からシンドローム
Ｓ１及びＳ３を計算するシンドローム演算回路と、Ｓ１
２を計算する回路と、Ｓ３を計算する回路と、（Ｓ＋　
３＋３３　）を計算する回路と、誤り位置多項式σ（ｘ
）＝ｓ、ｘ２＋ｓｌ　２Ｘ＋　（Ｓ１３＋ｓ３）のにガ
ロア体の元を順次代入して誤り位置を求める誤り位置演
算回路と、１誤り訂正可能なりＣＩ（符号を受信する場
合に、前記誤り位置演算回路の誤り位置多項式σ（Ｘ）
の係数（Ｓ＋　３＋３３　）を０に切り換える回路と、
前記誤り位置演算回路が求めた誤り位置のビットを反転
させることにより、ＢＣＨ符号の誤りを訂正する回路手
段とを具備したことを特徴とする。

第２の発明は、２誤り訂正可能なＢＣＨ符号の誤り訂正
装置であって、ＢＣＨ符号の受信系列からシンドローム
Ｓ】及びＳ３を計算するシンドローム演算回路と、Ｓ１
２を計算する回路と、Ｓ３／Ｓｌを計算する回路と、（
Ｓｌ　２＋Ｓ３／Ｓ１）を計算する回路と、誤り位置多
項式０式％） にガロア体の元を順次代入して誤り位置を求める誤り位
置演算回路と、１誤り訂正可能なＢＣＨ符号を受信する
場合に、前記誤り位置演算回路の誤り位置多項式σ（Ｘ
）の係数（Ｓｌ　２＋Ｓ３／Ｓ１）を０に切り換える回
路と、前記誤り位置演算回路が求めた誤り位置のビ・ｙ
　Ｊ・を反転させることにより、ＢＣＨ符号の誤りを訂
正する回路手段とを具備したことを特徴とする。

（作用） 第１の発明によれば、誤り位置演算回路は、２誤り訂正
可能なりＣ）（符号を受信した場合に、誤り位置多項式
をσ（Ｘ）＝ＳＩＸ”　＋Ｓ＋　２Ｘ＋（Ｓｌ　３＋ｓ
３　）として誤り位置を求め、１誤り訂正可能なりＣ［
（符号を受信した場合に、誤り位置演算回路の誤り位置
多項式σ（Ｘ）の係数（Ｓ＋　２＋５３　／Ｓｌ　）を
０に切り換え、誤り位置多項式をσ（Ｘ）＝ＳＩＸ２＋
５１２Ｘ＋０として誤り位置を求めることができるので
、１つの誤り位置演算回路で、１誤り訂正可能なＢＣＨ
符号の１誤り訂正と、２誤り訂正可能なＢＣＨ符号の２
誤り訂正とを行うことかてきる。

第２の発明によれば、誤り位置演算回路は、２誤り訂正
可能なＢＣＨ符号を受信した場合に、誤り位置多項式を
σ（Ｘ）＝Ｘ２＋ｓ１　ｘ＋（Ｓ＋　２＋５３　／Ｓｌ
　）として誤り位置を求め、１誤り訂正可能なりＣ）（
符号を受信した場合に、誤り位置演算回路の誤り位置多
項式σ（Ｘ）の係数（Ｓ＋　２＋３９　／Ｓ＋　）を０
に切り換え、誤り位置多項式をσ（Ｘ）−σ（Ｘ）＝Ｘ
２＋ｓｊ　Ｘ＋０として誤り位置を求めることができる
ので、１つの誤り位置演算回路で、１誤り訂正可能なＢ
ＣＨ符号の１誤り訂正と、２誤り訂正可能なＢＣＨ符号
の２誤り訂正とを行うことができる。

（実施例） 以下、図面に基づいて本発明の実施例を詳細に説明する
。第１図は本発明に係るＢＣＨ符号誤り訂正装置の一実
施例を示すブロック図である。

第１図において、符号１は、ＢＣＨ符号の受信系列が入
力される入力端子を示す。受信系列がシンドロームＳ】
演算回路２及びシンドロームＳ３演算回路３に供給され
、シンドロームＳ１及びシンドロームＳ３が生成される
。シンドロームＳ１は５１−Ｏ検出回路４に供給される
。このＳ１０検出回路４は、シンドロームＳ１の各要素
の全てが“０“の時、即ち、誤りが無いときに、論理“
１”　（ハイレベル）、それ以外の時論理“０”（ロー
レベル）の検出信号を発生する。この検出信号は否定回
路５に供給される。

シンドロームＳ１は、二乗回路６及び乗算回路７に供給
され、Ｓ１２及びＳ１３がそれぞれ計算される。乗算回
路７は、後述するように、Ｓ１２と８１１とを乗算する
ことによりＳ１３を算出する構成とされる。シンドロー
ムＳ３及びＳ１３が加算回路８に供給され、（Ｓｔ”＋
３３）が算出される。また、（Ｓ１３＋Ｓ３）は、ゲー
ト回路９に供給される。ゲート回路９は、端子１０から
の選択信号により、（Ｓ１３＋Ｓ３）を通過させるか、
０を出力するかを選択する。

ここで、本実施例のＢＣＨの符号誤り訂正装置が適用さ
れるディジタル信号の送受信システムでは、伝送されて
いるデータが１誤り訂正可能なＢＣＨ符号か、２誤り訂
正可能なＢＣＨ符号かを送信側が受信側に知らせるため
の手段（たとえば、訂正可能な誤り数を送信側がディジ
タル信号変えて送信する等）が設けられており、端子１
０からの選択信号ｕＱは、伝送されているデータがデー
タが１誤り訂正可能なＢＣＨ符号の場合“０゛となり、
２誤り訂正可能なＢＣＨ符号の場合“１゛となる。

上述のようにして、誤り多項式σ（Ｘ）ＳＩＸ　　＋ｓ
ｌ　２ｘ＋　（ｓ＋　３＋Ｓ］　）　−〇　（１誤り訂
正可能なＢＣＨ符号の場合、σ（Ｘ）　＝Ｓ１Ｘ　　＋
ｓｌ　２Ｘ＋０＝Ｏ）の係数ｓ、、ｓ、　２Ｓｔ　”　
十Ｓ３　、ｏの各々が得られ、これらの係数が誤り位置
演算回路１１に供給される６誤り位置演算回路１１は、
誤り位置多項式σ（Ｘ）一３Ｉ　Ｘ　　＋ＳＩ　　Ｘ＋
　（Ｓ１３＋Ｓａ　）＝０（１誤りの場合、σ（Ｘ）＝
ＳＩ　Ｘ２＋ｓｌ　２Ｘ＋０＝０）の根をチェーンサー
チ法で求め、誤り位置を検出する。誤り位置演算回路１
１の出力は誤り位置多項式σ（Ｘ＞＝Ｏのとき誤り訂正
を行うため論理“１”を発−生じ、誤り位置多項式σ（
Ｘ）がＯに等しくないとき誤り訂正を行わないための論
理“０”を発生する。

誤り位置演算回路１１からの出力が否定回路５の出力と
ともに、ＡＮＤゲート１３に供給される。否定回路５の
出力は、５１−０検出回路４によって。

シンドロームＳ１の各要素の全てが“０゛′のとき“０
パとなる。ここで８１−〇の場合には、式■■から８２
−０が成り立つ。Ｓ、＝Ｓ２＝Ｏの場合には、誤り位置
多項式の演算結果が式σ（Ｘ）−〇となり、誤り位置演
算回路１１は、誤って誤り位置信号を発生する。この正
しくない誤り位置信号を禁止するために、ＡＮＤゲート
１３が設けられている。

ＡＮＤゲート１３を介した“１”の誤り位置信号がエク
スクル−シブＯＲゲート（以下ＥＸ−ＯＲゲートと称す
る）１４に供給される。ＥＸ−ＯＲゲーｌ〜１４は、誤
り位置と対応して発生する誤り位置信号により、バッフ
ァ回路１５がらの受信系列のとットが反転される。ＥＸ
−ＯＲゲート１４がらの誤り訂正がされたデータ系列が
出力端子１６に導出する。バッファ回路１５は、誤り位
置が検出されるのに必要な時間、受信系列を遅延させる
。

この実施例は、例えば（３１，２１）　ＢＨＣ符号の復
号に対して適用できる。３１は符号長、２１は情報ビッ
ト長、最小距離は５である。従って、２ビツト以下の誤
りを訂正できる。この符号の生成多項式は、 Ｇ（Ｘ）−（Ｘ　　＋Ｘ　　＋１）（Ｘ　　＋Ｘ’＋ｘ
３＋Ｘ２＋１） −ｘ　　＋ｘ　　＋ｘ　　＋ｘ　　十ｘ５十ｘ３＋１ である、αを（Ｘ　　十Ｘ２＋１＝Ｏ）の根としたとき
、α　を根として持つ最小多項式は、＜　ｘ　５＋Ｘ　
　十Ｘ　　十Ｘ　　＋１＞である、（Ｘ５＋Ｘ”＋１＝
Ｏ）で与えられるガロア体ＧＦ　（２５）の元は、以下
の通りである。

第１表 第１表 第２図は、シンドロームＳ１を計算するシンドロームＳ
１演算回路２の一例を示す。シンドロームＳ１は、受信
符号語 γ（Ｘ）＝γｏ＋γ１ｘ＋・コ３０Ｘ３０に対して、γ
（αＪ）を計算することで求められる。

シンドロームＳ１演算回路２は、γ（α）を計算する回
路である。第２図に示すように、入力端子２１からの受
信系列Ｒ（γ３０　、γ２９．・・・γ１γ０）に対し
て１クロツクの遅延量を持つフリ・ツブフロップ２２．
２３．２４．２５．２６が縦続接続される。

多項式（Ｘ５＋Ｘ２＋１）の場合には、入力端子２１と
フリップフロップ２２との間にＥＸ−ＯＲゲート２７が
挿入される。ＥＸ−ＯＲゲート２７は（ｍ。

ｄ・２）の加算回路である。

（ｍｏｄ・２）の加算は、 ０　■　０＝０ ０　■　１＝１ １　■　０＝１ １　■　１＝０ である。

また、フリップフロップ２３とフリップフロップ２４と
の間にＥＸ−ＯＲゲート２８が挿入される。これらのＥ
Ｘ−ＯＲゲート２７．２８の各々には、フリップフロッ
プ２６の出力がフィードバックされる。

上述の入力端子２１に“１”を入力し、順次、フリップ
フロップ２２．２３．２４．２５　２６からなるシフ０
１、、。

トレジスタをシフトさせると、α　、α　。

α３０の２進数表現が各フリップフロップから出力され
る。従って、入力端子２１に受信系列γ３０　。

γ２９．・・・γ１．γ０を順次入力することにより、
シンドロームＳ＋　　（ａｏ、ａｌ、ａ２．ａ３ａ４）
が得られる。

第３図は、シンドロームＳ３を計算するシンドロームＳ
３演算回路３の一例を示す。シンドロームＳ３演算回路
３は、γ（α３〉を計算する回路であり、５個のフリッ
プフロップ３２．３３．３４．３５゜３６が縦続接続さ
れる。多項式＜　ｘ　５＋χ４＋Ｘ３十Ｘ２＋１）の場
合には、入力端子３１とフリップフロップ３２との間に
ＥＸ−ＯＲゲート３７が挿入される。また、フリップフ
ロップ３２とフリップフロップ３３との間にはＥＸ−Ｏ
Ｒゲート３８が挿入され、フリップフロップ３３とフリ
ップフロップ３４との間にはＥＸ−ＯＲゲート３９が挿
入され、フリップフロップ３４とフリップフロップ３５
との間には、ＥＸＯＲゲート４０が挿入される。これら
のＥＸ−ＯＲゲート３７．３８．３９．４０の各々には
、フリップフロラ１３６の出力がフィードバックされる
。

従って、入力端子３１に受信系列Ｒ（γ　、γ・・・γ
１．γ０）を順次入力することにより、シンドロームＳ
ｔ　　（ｄｏ、ｄｔ、ｄ２．ｄ３．ｄ＋）が得られる。

第４図は、シンドロームＳ１　（ａｏ　、ａｌ。

ａ２　、ａ３．ａ＋　）の二乗を計算する二乗回路６の
一例を示す。二乗回路６は、ａＱ及びａ４が入力される
ＥＸ−ＯＲゲート４１とａｌ及びａ４が入力されるＥＸ
−ＯＲゲート４２とａ３及びａ４が入力されるＥＸ−Ｏ
Ｒゲート４３とから構成される。

Ｓ１２を（ｂｏ、ｂｌ、ｂ２　、ｂ３　、ｂ＊　）とす
ると、ＥＸ−ＯＲゲート４１からｂｏが出力され、ＥＸ
−ＯＲゲート４２からｂ２が出力され、ＥＸＯＲゲート
４３からｂ３が出力され、Ｃ２がｂ４として出力され、
Ｃ３がｂｌとして出力される。

上述の二乗回路６によって、シンドローム５１（ａｏ　
、ａｔ　、Ｃ２，Ｃ３，ａｔ　）の二乗を計算できるこ
とを以下に説明する。

Ｓｌ　＝ａ４　ａ　　十ａ３　ａ　　＋ａ２　ａ２＋ａ
１α　十ａ。ａＯ ５ｉ　２＝ｂ４α８＋ｂ３α６＋ｂ２α４＋ｂ１α２＋
ｂＯα０ ８．６ と表す。ここで、α　、α　は表１を用いて次に示すよ
うにα４以下の次数に置き変えることができる。

ｓ、　２＝ｂ４α４＋　（ｂ４　＋ｂ３）α３＋（ｂ＋
　＋ｂｔ　）α２＋ｂ３α１＋ （ｂ＋　＋ｂｏ　）Ｃ０ ココテ、ＥＸ−ＯＲゲート４１．４２．４３は、それぞ
れ各要素の加算（ｂ＋　十ｂｏ　）、（ｂ＋　十ｔｚ　
）、（ｂ＋＋ｂ３）を行っているので、二乗回路６がシ
ンドロームＳ１の二乗を計算できることは明らかである
。

第５図は、乗算回路７の一例の構成を示す。５１は、シ
ンドロームＳ１演算回路２により計算されたシンドロー
ムＳ１　（ａｏ、ａｔ　、Ｃ２，ａ３ａ＋）の入力端子
を示す、シンドロームＳ１は（ｍｏｄ・２）の乗算を行
うＡＮＤ回路５２．５３゜５４、５５．５６に一方の入
力として供給される。

ｍｏｄ・２の乗算は、 ０　■　０＝０ ００１＝１ １００＝１ １０１　　＝０ である、ＡＮＤ回路５６．５５．５４．５３．、５２に
は、その他方の入力としてそれぞれＳ１２　（ｂｏ　、
ｂｚｂ２．ｂ３．ｂ４）が供給される。ＡＮＤ回路５３
゜５４、５５．５６の出力はそれぞれ加算回路５７．５
８．５９６０には一方の入力として供給される。ＡＮＤ
回路５２の出力はα乗算回路６１に供給され、α乗算回
路６１の出力は加算回路５７に他方の入力として供給さ
れる。加算回路５７の出力はα乗算回路６２に供給され
、α乗算回路６２の出力は加算回路５８に他方の入力と
して供給される。加算回路５８の出力はα乗算回路６３
に供給され、α乗算回路６３の出力は加算回路５９に他
方の入力として供給される。加算回路５９の出力はα乗
算回路６４に供給され、α乗算回路６４の出力は加算回
路６０に他方の入力として供給される。加算回路６０か
らは、Ｓ１３　（ｃｏ、ｃ＋　。

Ｃ２、ｃａ　、　Ｃ４）が出力される。即ち、乗算回路
７はＳ１２とＳｌとを乗算する構成である。

上述の乗算回路７によって、ガロア体上の２つの元Ａ、
Ｂの積Ｃを乗算できることを以下に説明する。

Ａ＝ａ４　ａ　　＋ａ３　ａ　　＋ａ２　α２十ａ１　
α１十ａ（Ｉ Ｂ＝ｂ４α　十ｂ３α３＋ｂ２α２＋ｂ１α１＋ｂ（。

と表す。この両者の積は、下記に示すものとなる。

Ｃ＝ＡＸＢ ＝　（Ｃ４ａ　　＋ａ３　ａ　　＋ａ２　α２十ａ１　
ａ１十ａ□　）　Ｘ　（ｂ４　ａ　　＋ｂ３　α３十ｂ
２　ａ２＋ｂｉα１＋ｂｏ） （Ｃ４ｂ４　ａ　　＋ａ３　ｂ４　ａ３＋Ｃ２ｂ４　ａ
　　＋ａ１　ｂ４　ａ’　十ａｏ　ｂ＋　）　ａ　　＋
（ａｔ　ｂ３　ａ’　＋Ｃ３ｂ３　ａ　　十ａ２　ｂ３
　ａ２十ａ１ｂ３　ａ　　＋ａ（１ｂ３　）ａ３＋（Ｃ
４ｂ２　ａ　　＋ａ３　ｂ２−十 Ｃ２ｂ２　ａ　　＋ａ１ｂ２　ａ１＋ ａｏ　ｂ２）　ａ　　十（Ｃ４ｂ１ａ’　＋Ｃ３ｂｌ　
ａ　　十ａ２　ｂ１ａ２十 ａ１ｂ１α　十ａｏｂ１）α１十 Ｃ４ｂＯａ　　＋ａ３　ｂＯａ３＋ Ｃ２ｂＯａ　　＋ａ１ｂＯａ’　＋ａＯｂ（１Ｃ４ａ　
　＋ｃＢ　ａ　　十ｃ２　α２十ｃ、ａ’　＋Ｏ となる。

ＡＮＤ回路５２．加算回路５７．５８．５９の出力はα
乗算回路６１．６２．６３．６４によってαが乗算され
る。

ＡＮＤ回路５２の出力Ｃ４は、 Ｃ４＝Ｃ４ α乗算回路６１による乗算により加算回路５７の出力Ｃ
３は、 Ｃ３＝Ｃ４α　＋Ｃ３ α乗算回路６２による乗算により加算回路５８の出力Ｃ
２は、 Ｃ２＝　（Ｃ４ａ　　＋ｃ３　）　ａ’　＋ｃ２Ｃ２＝
Ｃ４α２十ｃ３　ａ１＋ｃ２ α乗算回路６３による乗算により加算回路５９の出力Ｃ
１は、 Ｃ＋　−（Ｃ４α２＋Ｃ３α’　＋ｃ２　）α１十ｃ１ Ｃ１＝Ｃ４ａ　　＋Ｃ３α２十Ｃ２ａ’　＋ｃ１α乗算
回路６４による乗算により加算回路６０の出力Ｃｏは、 ＣＯ＝　（Ｃ４ａ　　＋ｃ３　ａ　　＋ｃ２　ａ１＋。

Ｉ）（２１＋Ｃ３ ＣＯ＝Ｃ４α　＋Ｃ３α３＋Ｃ２α２＋。、ａ１＋。。

となり演算が完了する。

第６図は、シンドロームＳ１　（ａＯ，ａｌ。

Ｃ２、Ｃ３、Ｃ４）とｂ４とを乗算するＡＮＤ回路５２
の一例を示す。ＡＮＤ回路５２は、ａＯ及びｂ４が入力
されるＡＮＤゲート７１とａｌ及びｂ４が入力されるＡ
ＮＤゲート７２とＣ２及びｂ４が入力されるＡＮＤゲー
ト７３とＣ３及びｂ４が入力されるＡＮＤゲート７４と
Ｃ４及びｂ４が入力されるＡＮＤゲート７５とから構成
される。出力Ｓｔ　ｂ４を（ｅ（１、ｅ＋　、Ｃ２、Ｃ
９，Ｃ４）とすると、ＡＮＤゲート７１．７２．７３．
７４．７５から、それぞれｅＯ、ｅｌ　、Ｃ２、Ｃ３、
Ｃ４が出力される。

上述のＡＮＤ回路５２によって、シンドロームＳ１　（
ａｏ、ａｌ、Ｃ２，Ｃ３，Ｃ４）とｂ４とを乗算し、（
ｅｏ　、ｅｌ、Ｃ２＊　Ｃ３，ｅ＊　）（ａｏ　　　ｂ
＋　　、　　　ａｔ　　　ｂ＋　　、　　　ａ　　２　
　ｂ＋　　、　　　ａ　　３　　ｂ　　４ａ＊　１）４
　）を出力できることは明らかである。尚、他のＡＮＤ
回路５３．５４．５５．５６もＡＮＤ回路５２と同様の
構成となっている。

第７図は、ＡＮＤ回路５２の出力にαを乗算するα乗算
回路６１の一例を示す、α乗算回路６１は、ｅｌ及びＣ
４が入力されるＥＸ−ＯＲゲート７６により構成される
。出力ｓ、ｂ４αを（ｆｏ、ｆａ、。

ｆ２．ｆａ、ｆａ）とすると、ＥＸ−ＯＲゲート７６か
らｆ２が出力され、ｅＱ、Ｃ２，Ｃ３，Ｃ４がそれぞれ
ｆｌ　、ｆａ　、ｆ４．ｆ、として出力される。

即ち、α（ｅｏ十ｅ１α十ｅ２α２＋ｅ３α３＋ｅ４α
４） ｅＯα十ｅ１α２＋ｅ２α３＋ｅ３α４＋Ｃ４α５ ＝ｅＯα十ｅ１α２＋ｅ２α３＋ｅ３α４＋ｅ４　（α
２＋α０） ＝Ｃ４＋ｅｏａ＋　（ｅｌ十ｅ４　）Ｃ２＋ｅ２　α３
十ｃ３　Ｃ４ ＝ｆＯ＋ｆ１α＋ｆ２　Ｃ２＋ｆ３　Ｃ３＋ｆ４　Ｃ４
となる。

上述のα乗算回路６１によって、ＡＮＤ回路５２の出力
（ｅｏ、ｅｌ、Ｃ２，Ｃ３，ｅ＊）とαとを乗算して、
（ｆｏ　、ｆａ　、ｆ２．ｆａ　、ｆａ　）を出力でき
ることは明らかである。尚、他のα乗算回路６２．６３
．６４．６５もα乗算回路６１と同様の構成となってい
る。

第８図は、α乗算回路６１の出力（ｆｏ、ｆ１ｆ２．ｆ
ａ、ｆａ）とＡＮＤ回路５３の出力（ｇｏ　。

ｇｌ、Ｃ２，Ｃ３，ｇ＊　）とを加算するする加算回路
５７の一例を示す、加算回路５゛７は、ｆＯ及びｇｏ、
ｆｌ及びｇｌ　、ｆ２及びＣ２，ｆａ及びＣ３，ｆａ及
びＣ４がそれぞれ入力されるＥＸＯＲゲート７７、７８
．７９．８０．８Ｈ：１ｍより構成される。

出力ｓｔ　ｂ４α＋Ｓｌ　ｂ３を（ｈｏ　、　ｈｔ　、
　ｈ２ｈ３　、　ｈ４　）とすると、ＥＸ−ＯＲゲート
７７、７８゜７９、８０．８１からそれぞれｈａ　、　
ｈｉ　、　ｈ２　、　ｈ３　。

ｈ４が出力される。なお、他の加算回路５８．５９６０
も加算回路５７と同様の構成となっている。また、（Ｓ
１３＋Ｓ３）を算出する加算回路８も加算回路５７と同
様の構成となっている。

第９図は、ゲート回路９の一例の構成を示す。

ゲート伺路９は、加算回路８の出力（Ｓ１３＋５ａ）＝
（ｔｏ、ｔｌ、ｉ２．ｉ３．ｉ＋）と選択信号ｕＱとを
乗算する乗算回路になっている。

さらに詳しく説明すると、グー１−回路９は、ｉｏおよ
びｕＱが入力されるＡＮＤゲート８１と１１およびｕＱ
が入力されるＡＮＤゲート８２と１２およびｕＱが入力
されるＡＮＤゲート８２と＋３およびｕＱが入力される
ＡＮＤゲート８２と＋４およびｕＱが入力されるＡＮＤ
ゲート８２ととがら構成される。ゲート回路９の出力（
Ｓｌ　３＋Ｓ３　）ｕ。

を（ｊｏ、ｊｏ、＋２．＋３．ｊｏ）とすると、ＡＮＤ
ゲート７１．７２．７３．７４．７５から、それぞれｊ
ｏ、ｊｏ　、＋２．ｊａ、ｊｏが出力される。

上述の回路によって出力（Ｓｚ　３＋３３　）　−（ｉ
ｏ、ｉｌ、＋２．ｉヨ、＋４）と選択信号ｕＱとを乗算
し、（ｊｏ、ｊｌ、＋２．＋３ｊ＋　　）−（ｊｏ　　
ｕｏ　　、ｊｏ　　ｕｏ　　、＋２　ｕｏ　　・　＋３
ｕｏ、＋４ｕｏ）を出力できることは明らかである。こ
のｕＱは、１誤り訂正可能なＢＣＨ符号の誤り訂正を行
う場合は論理値“０”となり、２誤り訂正可能なＢＣＨ
符号の誤り訂正を行う場合は論理値“１”となる。この
ことは、ゲート回路９が２誤り訂正可能なＢＣＨ符号の
誤り訂正を行う場合、ｓ、”　＋３３をそのまま通過さ
せ、１誤り訂正可能なＢＣＨ符号の誤り訂正を行う場合
、出力が°゛０”となることを示している。

誤り位置演算回路１１は、誤り位置多項式σ（Ｘ＞ｓ、
αＸ　　＋Ｓ＋　”　Ｘ＋　（Ｓ１２　＋Ｓ３　）＝０
の根を求める回路である。ここで、ガロア拡大体■ ＧＦ（２）の元の数は２１個である。このうち、元Ｏを
除いた２”−１個の元はαにと表される。

とすると指数にの値はＯ〜（２”−１＞の範囲の値をと
る。受信符号の先頭ビットから誤りの有無を調べるため
に、Ｘにα　、　　　、・・と代入する。

α もしσ（α−ｋ）−〇となったとすると、受信符号の（
２−１−ｋ）次すなわち、符号長２−１の先頭からに番
目に誤りがあったことがわかる。

第１０図は誤り位置演算回路１１の一例を示す。誤り位
置演算回路１１は、１クロツクの遅延量の遅延回路１０
１　、１０２　、１０３とα−２乗算回路１０４とα−
１乗算回路１０５とスイッチ回路１０６　、１０７と加
算回路１０８とゼロ検出回路１０９とから構成される。

加算回路１０８は、加算回路１１０　、１１１がら構成
される。スイッチ回路１０６　、１０７は、受信系列の
先頭ビットのタイミングの時のみ、即ち、係数８１、Ｓ
ｌ　をそれぞれ取り込んだ時のみ、シンドロームＳ１演
算回路２がらの８１及び二乗回路６がらのＳ１２を各々
選択し、残りのビットのタイミングでは、α　乗算回路
１０５とα−１乗算回路１０４をそれぞれ選択する。

スイッチ回路１０６及び１０７の出力が遅延回路１０１
　、１０２にそれぞれ供給され、遅延回路１０１１０２
の出力がα　乗算回路１０４及びα−１乗算回路１０５
にそれぞれ供給され、巡回構成とされる。

α−２乗算回路１０４は、α−２を乗じるもので、α−
１乗算回路１０５はα　を乗じるものである。αは、Ｇ
Ｆ（２）の生成多項式の根である。αの符号長をｎとす
ると、α−２乗算回路１０４により、Ｓ１２α−２°の
項が得られ、α　乗算回路１０５により、Ｓ１２α−０
の項が得られ演算される。これらのα　乗算回路１０４
及びα−１乗算回路１０５の出力が（ｍｏｄ・２）の加
算を行う加算回路１１０に供給され、加算回路１１０の
出力は、加算回路１１１に一方の入力として供給される
。また、ゲート回路９の出力は遅延回路１０３に供給さ
れ、遅延回路１０３の出力は、加算回路１１１に他方の
入力として供給される。加算回路１１０　、１１１から
構成される加算回路１０８は、選択信号ｕＱが“１”の
場合ａ　（Ｘ）＝Ｓｔ　Ｘ　　＋ＳＩ　　Ｘ十（Ｓｔ　
３＋Ｓ３）、選択信号ｕＱが“Ｏ°″の場合σ（Ｘ＞ｓ
、ｘ２＋ｓ、　２ｘ十ｏ、の演算を行うもので、この加
算回路１０８（加算回路１１１）の出力が、ゼロ検出回
路１０９に供給される。ゼロ検出回路１０９の出力はＡ
ＮＤゲート１３に供給される。

第１１図は、遅延回路１０１の出方にα−１を乗算する
α−１乗算回路１０５の一例を示す。遅延回路１０２の
出力Ｋを（ｋｏ　、ｋＩ、に２　、に３　、にヰ）とす
ると、α　１乗算回路１０５は、ｋ、及びに３が入力さ
れるＥＸ−ＯＲゲート１１２により構成される。

出力Ｋ　ａ　”をＬ（ｌｏ、＋１．１２．１３．１４）
とすると、ＥＸ−ＯＲゲート１１２がら１２が出力され
、ｋｌ　、に２　、に４　、に、、がそれぞれＩ。

１１．１３．１４として出力される。

即ち、ａ　　（ｋ□　＋に１ａ１＋に２　ａ２＋に３α
　十に４α４） ＝に□　ａ　　＋ｋｌ　＋に２　ａ　　＋に３　ａ２＋
に４ａ３ ＝ｋ（１（（Ｚ　　＋ａ　　）＋に１＋に２　ａ’　＋
に３α２＋に４α３ に１＋　（ｋ（１＋に２　）ａ　　＋に３　ａ２＋に４
α３＋ｋｏα４ １０＋ＩＩ（Ｚ　　＋１２（２＋１３（Ｚ３＋１牛α４
となる。

第１２図は、遅延回路１０１の出力にα−２を乗算する
α−２乗算回路１０４の一例を示す。遅延回路１０２の
出力Ｍを（ｍｏ　、ｍｌ、　ｍ２．ｍ３　、ｍ４　）と
すると、α−２乗算回路１０４は、ｍＱ及びｍ３が入力
されるＥＸ−ＯＲゲート１１３とｍｌ及びｍ４が入力さ
れるＥＸ−ＯＲゲート１１４により構成される。

出力Ｋ　ａ　’＝　Ｎを（ｎｏ　、ｎｔ　、ｎ２．ｎ３
ｎ４）とすると、ＥＸ−ＯＲゲート１１３からｎｌが出
力され、ＥＸ−ＯＲゲート１１４からｏ２が出力され、
ｍ２　、ｍＯ，ｒｔＢがそれぞれｎＱ　、　ｎ３ｎ４と
して出力される。

即ち、ａ−２（ｍｏ＋ｍ１ａ１＋ｍ２ａ２十ｍ３ａ３＋
ｍ４ａ４） ｍＱ　ａ　十ｍ１　ａ−１＋ｍ２　＋ｒｒＢ　ａ’　　
＋４ａ２ ｍｏ　（α　＋α　）＋ｒｒｚ（α１＋α４）＋ｍ２＋
ｍ３α　十ｍ４α２ ＝ｍＯ＋ｍ２　＋　（ｍ＋　＋ｍ３）α　十ｍ４α２＋
ｍＯａ　　十ｍ１　α ｎｏ＋ｎ１ａ１±ｎ２ａ２＋ｎ３ａ３＋ｎ４α４となる
。

第１３図は、加算回路１１１の出力０　（ｏＯ、ｏ１ｏ
２．ｏ３．Ｏ牛）のゼロ検出を行うゼロ検出回路１０９
を示している。ゼロ検出回路１０９は、ＯＱ。

Ｏｔ　、０２　＋　０３．０４が入力されるＮＯＲゲー
ト１１５から構成される。ＮＯＲゲート１１５は、００
・０】・ｏ２　、ｏ３　、ｏ４の全てが“Ｏ”のとき、
σ（Ｘ）　−〇を示す出力“１”を出力する。

第１４図は、シンドロームＳ１演算回路２により計算さ
れたシンドロームＳｓ　　（ａｏ、ａｔ　、ａ２゜ａ３
．ａ４）のゼロ検出を行う５ｌ＝Ｏ検出回路４を示して
いる。Ｓｔ　＝Ｏ検出回路４は、ａＱ。

ａｌ　、ａ２　、ａ３　、ａ４が入力されるＮＯＲゲー
ト１１６とこのＮＯＲゲート１１６の出力を誤り訂正の
間保持しておくレジスタ１１７とから構成される。

ＮＯＲゲート１１６は、ａＯ、ａｌ、ａ２　、ａ３　。

ａ４の全てが“０”のとき、受信系列に誤りが無かった
ことを示す出力“１パを出力する。また、ａＯ・ａｌ　
、ａ２　、ａ３　、ａ４のうち少なくとも１つが“１”
のとき、誤りが有ったことを示す出力“０”を出力する
。

つぎに、誤り訂正動作について説明する。２誤り訂正可
能なＢＣＨ符号の誤り訂正を行う場合は、入力端子１０
からの訂正信号が“１”となり、誤り位置演算回路１１
には、加算回路８からの８１３＋Ｓ３が供給され、誤り
位置演算回路１１は、誤り位置多項式σ（Ｘ）＝ＳＩＸ
２＋Ｓ＋　２Ｘ＋（Ｓｒ　　＋Ｓ３）のＸにα　、α　
、・・・と順次式人する。これは、等価的にα　、α　
、・・・を代入したことになり、受信符号ｒ３０．ｒ２
９．・・・の誤りについて順次調べることになる。

１誤り訂正可能なＢＣＨ符号の誤り訂正を行う場合は、
入力端子１０からの訂正信号が“ＯＩ＋となり、誤り位
置演算回路１１には、０が供給され、誤り位置演算回路
１１は、誤り位置多項式σ（Ｘ）　−ＳＩ　Ｘ　　＋Ｓ
＋　Ｘ＋０ｆ）Ｘにα、α、−・と順次代入する。これ
により、受信符号ｒ３０．ｒ２９゜・・・の誤りについ
て順次調べることになる。ここで、この場合、シンドロ
ームＳ３は不正確な値になるが、ａ　（Ｘ）＝ＳＩ　Ｘ
２＋Ｓ１　ｘ＋ｏｃ：ｓ、ｔ、シンドロームＳ３は含ま
れないので問題がない。

このような実施例によれば、１誤り訂正可能なＢＣＨ符
号の１誤り訂正と、２誤り訂正可能なＢＣＨ符号の２誤
り訂正とを、１つの誤り位置演算回路１１で行うことが
できるので、回路の削減が行え、装置の製造コストを低
減できる。

尚、上記実施例において、誤り位置演算回路１１は、１
誤り訂正可能なＢＣＨ符号の誤り訂正を行う場合に、σ
（Ｘ）＝Ｓｔ　＋Ｓ１２ｘ−’＋ｏのチェーンサーチを
行い、２誤り訂正可能なＢＣＨ符号の誤り訂正を行う場
合に、σ（Ｘ）＝Ｓｌ　＋Ｓｌ　　　Ｘ　　＋　（Ｓｌ
　　　＋３３　）Ｘ−２のチェーンサーチを行うように
構成してもよい。

他の実施例として、誤り位置演算回路が、１誤り訂正可
能なＢＣＨ符号の誤り訂正を行う場合に、σ（Ｘ）−α
Ｘ２＋ＳＩＸ＋ｏのチェーンサーチを行い、１誤り訂正
可能なＢＣＨ符号の誤り訂正を行う場合に、６　（Ｘ）
＝ａＸ２＋ＳＩ　Ｘ＋Ｓ１”＋Ｓ３／Ｓｔのチェーンサ
ーチを行うように構成してもよい。この場合Ｓ３　／Ｓ
、を得る回路は、Ｓ３／ＳｌのＲＯＭテーブルを用いる
もの、１／Ｓ１のＲＯＭテーブルを用いるもの等がある
。

また、これらの実施例ではＢＣＨ（３１，２１）を短縮
化した例を示したが、この次数によらず、他の次数のＢ
ＣＨ符号にも適応できる。

［発明の効果］ 以上述べた様にこの発明によれば、１誤り訂正可能なＢ
ＣＨ符号の１誤り訂正と、２誤り訂正可能なり　Ｃ−Ｈ
符号の２誤り訂正とを、１つの誤り位置演算回路で行う
ことができるので、回路の削減が行え、装置の製造コス
トを低減できる。

【図面の簡単な説明】

第１図は本発明に係るＢＣＨ符号誤り訂正装置の一実施
例を示すブロック図、第２図は第１図のシンドロームＳ
１演算回路を示すブロック図、第３図は第１図のシンド
ロームＳ３演算回路を示すブロック図、第４図は第１図
の二乗回路を示す回路図、第５図は第１図の乗算回路を
示す回路図、第６図は第５図のＡＮＤ回路を示す回路図
、第７図は第５図のα乗算回路を示す回路図、第８図は
第５図の加算乗算回路を示す回路図、第９図は第１図の
ゲート回路を示すブロック図、第１０図は第１図の誤り
位置演算回路を示すブロック図、第１１図は第１０図の
α−２乗算回路を示す回路図、第１２図は第１０図のα
−１乗算回路を示す回路図、第１３図は第１０図のゼロ
検出回路を示す回路図、第１４図は第１図のｓｌ　＝ｏ
検出回路を示す回路図である。 ２・・・シンドロームＳ１演算回路、 ３・・・シンドロームＳ３演算回路、 ４・・・Ｓｌ−〇検出回路、６・・・二乗回路、７・・
・乗算回路、８・・・加算回路、９・・・ゲート回路、
１１・・・誤り位置演算回路、１５・・・バッファ回路
。 第２面 ｄｌ、　　　　　ｄ２ 第３図 第４図 第６図 ｅＱ 第７面 第８図 第９ 図 第１１ 図 第１２図 第１４図

Claims (2)

【特許請求の範囲】
1. （１）２誤り訂正可能なＢＣＨ符号の誤り訂正装置であ
   つて、 ＢＣＨ符号の受信系列からシンドロームＳ＿１及びＳ＿
   ３を計算するシンドローム演算回路と、Ｓ＿１＾２を計
   算する回路と、 Ｓ＿１＾３を計算する回路と、 （Ｓ＿１＾３＋Ｓ＿３）を計算する回路と、誤り位置多
   項式σ（Ｘ）＝Ｓ＿１Ｘ＾２＋Ｓ＿１＾２Ｘ＋（Ｓ＿１
   ＾３＋Ｓ＿３）のにガロア体の元を順次代入して誤り位
   置を求める誤り位置演算回路と、１誤り訂正可能なＢＣ
   Ｈ符号を受信する場合に、前記誤り位置演算回路の誤り
   位置多項式σ（Ｘ）の係数（Ｓ＿１＾３＋Ｓ＿３）を０
   に切り換える回路と、前記誤り位置演算回路が求めた誤
   り位置のビットを反転させることにより、ＢＣＨ符号の
   誤りを訂正する回路手段とを具備したことを特徴とする
   ＢＣＨ符号の誤り訂正装置。
2. （２）２誤り訂正可能なＢＣＨ符号の誤り訂正装置であ
   って、 ＢＣＨ符号の受信系列からシンドロームＳ＿１及びＳ＿
   ３を計算するシンドローム演算回路と、Ｓ＿１＾２を計
   算する回路と、 Ｓ＿３／Ｓ＿１を計算する回路と、 （Ｓ＿１＾２＋Ｓ＿３／Ｓ＿１）を計算する回路と、誤
   り位置多項式σ（Ｘ）＝Ｘ＾２＋Ｓ＿１Ｘ＋（Ｓ＿１＾
   ２＋Ｓ＿３／Ｓ＿１）にガロア体の元を順次代入して誤
   り位置を求める誤り位置演算回路と、１誤り訂正可能な
   ＢＣＨ符号を受信する場合に、前記誤り位置演算回路の
   誤り位置多項式σ（Ｘ）の係数（Ｓ＿１＾２＋Ｓ＿３／
   Ｓ＿１）を０に切り換える回路と、 前記誤り位置演算回路が求めた誤り位置のビットを反転
   させることにより、ＢＣＨ符号の誤りを訂正する回路手
   段とを具備したことを特徴とするＢＣＨ符号の誤り訂正
   装置。