JPH0345020A

JPH0345020A - 巡回符号処理回路

Info

Publication number: JPH0345020A
Application number: JP1181162A
Authority: JP
Inventors: Shingo Ikeda; 信吾池田; Motoichi Kashida; 樫田　素一
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1989-07-13
Filing date: 1989-07-13
Publication date: 1991-02-26
Also published as: US5715258A; EP0408362A3; EP0408362A2

Abstract

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

Description

【発明の詳細な説明】［産業上の利用分野］本発明はデータ伝送誤りの検出訂正用の巡回符号を高速
処理する巡回符号処理回路に関する。

［従来の技術］従来、ディジタル信号伝送システムでは、情報データに
適当な冗長ビットを付加することによって、伝送誤りを
検出訂正する誤り検出訂正方式が使用されている。その
符号化方式の１つに、巡回符号によるＣ　ＲＣＣ（ｃｙ
ｃｌｉｃ　ｒｅｄｕｎｄａｎｃｙ　ｃｈｅｃｋ　ｃｏｄ
ｅ）がある。以下、ＣＲＣＣの符号化・復号化装置の従
来例を説明する。但し、以下の演算は全て、ガロア体に
基づくものとする。

巡回符号化する場合、情報多項式１（ｘ）を１（ｘ）＝
ｉ、＋ｉ、ｘ＋Ｌｘ”＋ｉ、ｘ”＋−・−＋ｉｈ−、ｘ
ｋ−’　　　（Ｌ）とし、生成多項式Ｇ（ｘ）を、Ｇ（ｘ）：ｇｏ＋ｇ＋ｘ＋ｇ＊ｘ”＋ｇｌｘ”＋−・−
＋ｇ、ｘ”　　　　　（２）とすると、組織符号として
の符号語Ａ（ｘ）は、Ａ（ｘ）＝Ｒ（ｘ）　＋Ｉ（ｘ）
ｘ”　　　　　　　　　　　　（３）で求められる。但
し、Ｒ（ｘ）＝Ｉ（ｘ）ｘ”　ｍｏｄ　Ｇ（ｘ）　　　　　
　　　　　（４）である。

第３図はこの符号化を行なう符号化回路の構成ブロック
図を示す。１０，１２．１４は１単位時間の遅延回路、
１６，１８．２０は定数ｇｏ＋　ｇ＋＋ｇ、−１を乗算
する乗算器、２２，２４．２６は２つの入力の排他的論
理和をとる演算回路、２８．３０はスイッチ、３２は遅
延回路１０，１２．１４及びスイッチ２８．３０の動作
タイミングを規定するタイミング回路、３４は符号化し
ようとする情報の入力端子、３６は符号語の出力端子で
ある。

第３図の動作を説明する。先ず遅延回路１０゜１２．１
４をリセットしてから、スイッチ２８゜３０をａ接点側
に接続し、入力端子３４から情報を１ｋ−１＋１ｋ−１
＋・・・＋　１１　＋　ｉ　ｏの順に人力する。スイッ
チ２８がａ接点に接続しているので、入力端子３４の入
力情報はそのまま、出力端子３６から出力されるが、同
時に、演算回路２６及び乗算器１６゜１８．２０を介し
て遅延回路１０，１２．１４に印加され、１０が出力端
子３６から出力される時点では、遅延回路１０，１２．
１４には剰余Ｒ（ｘ）が残っている。そこで、スイッチ
２８．３０をｂ接点側に接続し、剰余ｒ＋ｍ−ｘ、ｒｍ
−＊＋・・・、ｒｌ　、Ｔｏを出力端子３６から取り出
す。このようにして、出力端子３６から符号語Ａ　（ｘ
）を得ることができる。

このような符号語Ａ　（ｘ）を復号化する場合、受信語
Ｙ（ｘ）をＹ（ｘ）＝ｙｏ÷Ｙ１Ｘ＋ｙｔＸ”　＋　・・・＋ｙ　
＠−ＩＸ’−”　　　　　（５）とし、誤りパターンＥ
（ｘ）を、Ｅ（ｘ）＝ｅ、÷６＋Ｘ＋ｅ＊Ｘ’＋”’＋ａｌｌ−＋
Ｘ″−１　　　　　　　　　　（６）とすると、Ｙ（ｘ
）は、Ｙ（ｘ）＝Ａ（ｘ）＋Ｅ（ｘ）　　　　　　　　　　　
　　　（７）で表わされる。シンドローム多項式５（ｘ
）は、５（ｘ）二Ｙ（ｘ）　ｍｏｄ　Ｇ（ｘ）　　　　
　　　　　　　（８）で表わされ、５（ｘ）＝０のとき
、誤りがないと判定される。

第４図は、この復号化処理を行なう復号化回路の概略構
成ブロック図を示す。３８，３９．４０は単位遅延量の
遅延回路、４２，４３，４４，４５．４６はそれぞれ定
数ｇｏ、　ｇ＋＋　ｇｔ、　ｇ−ｓ、　ｇ−を乗算する
乗算器、４８，４９，５０．５１は２つの入力の排他的
論理和をとる演算回路、５２は遅延回路３８．３９．４
０の動作を規定するタイミング回路、５４は伝送路を伝
送してきた符号語の入力端子、５６は復号化された情報
の出力端子である。入力端子５４に５４に受信語Ｙ（ｘ
）がｙｎ−１，ｙｎ−２，・・・ｙ２．ｙｌの順で入力
すると、遅延素子３８゜３９．４０に５（ｘ）の係数が
得られる。

［発明が解決しようとする課題］上記従来例では、符号化回路又は復号化回路はデータの
ビット・レートと同じクロックで動作するので、高いビ
ット・レートのデータには不向きである。

本発明は、より高速に処理できる巡回符号処理回路を提
示することを目的とする。

［課題を解決するための手段］本発明に係る巡回符号処理回路は、データ伝送誤り検出
・訂正用の巡回符号の符号化又は復号化を行なう回路に
おいて、１符号語を構成する情報ビットのパラレル・デ
ータに対して、対応する検査ビットに関する所定データ
を出力する１個以上のデータ発生手段を具備することを
特徴とする。

［作用］上記データ発生手段は、情報ビットに対してパラレル処
理により、対応する検査ビット又はそれの基になるデー
タを発生するので、情報ビットのビット・レートとは無
関係に、しかも高速に検査ビットを得ることができる。

即ち、高いビット・レートのデータを高速に処理できる
。

［実施例］以下、図面を参照して本発明の詳細な説明する。

第１Ａ図及び第１Ｂ図は本発明の一実施例の構成ブロッ
ク図であり、第１Ａ図は符号化回路を、第１Ｂ図は復号
化回路を示す。第１Ａ図において、６０は入力データｔ
、、ｉ、、・・・＋’に−１，１ｋに対する巡回符号の
データをテーブルとして記憶するメモリであり、そのア
ドレスＡ’ｏ、Ａｔ、・・・Ａｋ−１にデータｉ。。

ｉｌ、・・・、１ｋ−１，ｉｋを人力すると、データ出
力Ｄｏ、ｌ）＋、・・・、Ｄ、−□から対応する検査ビ
ットｒＯ＋　’　＋　＋・・・＋　ｒｌＩ−１を出力す
る。６２はラッチ回路であり、入力データ１Ｇ＋１１＋
・・・、１ｈ−１＋ｉｋと、それに対するメモリ６０の
出力、即ち検査ビットｒ、、ｒ、、・・・−ｒｍ−１と
をラッチし、符号語として出力するためのものである。

第１Ｂ図において、６４はメモリ６０と同じ内容のメモ
リであり、受信した誤りパターンを含む符号語の情報ビ
ットが入力されると、対応する検査ビットを出力する。

６６はビット単位の比較器であり、受信した誤りパター
ンを含む符号語の検査ビットと、メモリ６４からの検査
ビットとをビット単位で比較し、誤りの有無及び位置を
示す誤り検出信号を出力する。゛比較器６６でのビット
比較が全部一致する場合には、誤りなしということにな
る。

第２Ａ図は情報ビット数及びそれに対する検査ビット数
が多い場合の、本発明の第２の実施例である処理回路の
要部の概略構成ブロック図である。

即ち、第２Ａ図は第１Ａ図の符号化回路、第１Ｂ図の復
号化回路のメモリ６０．６４の部分の変更例を示す。７
０，７１，７２．７３はアドレス人力に対して後述する
検査ビットを出力するメモリ、７６．７７．７８．７９
は排他的論理和をとる演算回路である。図示例では、２
０ビツトの人力ＬＯ＋ｉ１．・・・ｉｌ、に対して８ビ
ツトの検査ビットｒ　Ｏ＋　ｒ　１　＊・・・、ｒ、を
発生させている。演算はガロア体に基づくとして、その
理論背景を説明する。

入力データｉと検査ビットｒとの間には次式の関係があ
る。

（ｒｏ＋ｒｌ＋・・・、ｒ７）＝（ｉｏ、ｌｔ、・・・１１１１１）式（９）を４つに分解し、（ｒ。

、ｒｌ、ｒ＊’、ｒ＊’）＝（１０＋１１＋・・・、ｉ、）（ｒ４　’　、　ｒｅ、ｒｏ、ｒ７°）＝（ｔｏ、ｉ、、・・・、ｉ、）（ｒｏ　　、ｒ、’、ｒ畳ｒｅ”）＝（１１゜＋ｌＩＩ＋・・・＋ｌ！９）（ｒ４　、ｒｅ
−、ｒｅ”、ｒｔ”）＝（１１゜＋１１１＋・・・、ＬＪとする。但し、ｒ、＝ｒ、’＋ｒ、’　　　　　　（ｍ＝０〜７）　　
　　　　（１４）である。式（１０）の係数（ｇ＋、　
＋ｌは予め分かっているので、（ｔｏ、１＋、・・・、
ｉ、）に対する（ｒｏ”　＋ｒ＋　’　、ｒ２°２ｒ、
゛）の関係を予め求め、アドレスに（ｉｏ、Ｌ、・・・
、ｉ、）を入力した場合に、出力データとして式（ｌＯ
）の（ｒ。’、ｒ＋’、ｒｚ’、ｒ＊’）を得ることが
できるようなデータ・テーブルをメモリ７０に格納して
おく。同様に、式（１１）、（１２）、（１３）の関係
になるデータ・テーブルをそれぞれメモリ７１，７２．
７３に格納する。

そして、演算回路７６．７７；　　７８，７９により式
（１４）の演算を行ない、最終的な目的値である検査ビ
ット（ｒｅ、ｒ’＋、・・・、ｒ７）を得る。

第２Ｂ図は、第２Ａ図の場合より更に情報ビット数及び
検査ビット数が増した場合で、情報ビット数が（ａ−１
）ｎ、検査ビット数がｂｍの場合の実施例の要部の概略
構成ブロック図であるり、第２Ａ図と同様に第１Ａ図、
第１Ｂ図のメモリ６０．６４の部分の変更例を示してい
る。図示のごとく、第２Ｂ図の構成では第２Ａ図のメモ
リ７０〜７３と同様のメモリ８０〜８８をマトリック構
成で配置し、入力の情報ビット１０＋・・・、ｌ　（ａ
−Ｎ　＋＋−１をａ組に分割し、各組の情報ビットを同
じ行のメモリのアドレス入力に人力する。各メモリ８０
〜８８は第２Ａ図と同様に、対応する検査ビットに関連
するデータを出力する。そして、同じ列のメモリからの
出力を排他的論理和回路９０〜９５で演算すれば、目的
の検査ビットｒｏ＋・・・ｒニー、を得ることができる
。

第２Ａ図及び第２Ｂ図の回路を用いた復号化回路は、第
１図の場合と同様に、第２Ａ図及び第２Ｂ図に図示した
構成で受信符号語中の情報ビットに対する検査ビットを
求め、この検査ビットと受信符号語中の検査ビットとを
ビット比較器によりビット比較すればよい。

上記のように構成すると、データをパラレル処理するこ
とになり、非常に高速に目的の出力を得ることができる
。また、ビット・レートに依存しないので、高いビット
・レートの信号でも同様に高速に処理できる。

［発明の効果］以上の説明から容易に理解できるように、本発明によれ
ば、情報ビットに対する検査ビットを高速に、しかもビ
ット・レートに依存せずに得ることができる。従って、
高いビット・レートのデータ伝送を容易に実現できる。

【図面の簡単な説明】

第１Ａ図は本発明の第１実施例の符号化回路の概略構成
ブロック図、第１Ｂ図は第１Ａ図に対応する復号化回路
の構成ブロック図、第２Ａ図及び第２Ｂ図は情報ビット
数及び検査ビット数が増した場合の本発明の別の実施例
の概略構成ブロック図、第３図は従来例の符号化回路の
構成ブロック図、第４図は従来例の復号化回路の構成ブ
ロック図である。

Claims

【特許請求の範囲】

データ伝送誤り検出・訂正用の巡回符号の符号化又は復
号化を行なう回路であって、１符号語を構成する情報ビ
ットのパラレル・データに対して、対応する検査ビット
に関する所定データを出力する１個以上のデータ発生手
段を設けたことを特徴とする巡回符号処理回路。