JPS6245570B2 - - Google Patents

Description

【発明の詳細な説明】 発明の技術分野 本発明は、ｋビツトからなる情報点に対してｍ
ビツトの検査点を付加して、ｎ（ｎ＝ｋ＋ｍ）ビ
ツトの線形符号を生成するための符号化演算回路
に関するものである。

従来技術と問題点 端末間あるいはコンピユータ間のデータ通信等
の場合において、伝送された符号に誤りが生じた
とき受信側でこれを検出することができるように
するため、誤り訂正符号が用いられている。誤り
訂正符号は、ｋビツトからなる送るべき情報すな
わち情報点に対し、ｍビツトの剰余すなわち検査
点を付加して、ｎ（ｎ＝ｋ＋ｍ）ビツトからなる
線形符号を構成したものである。すなわちここに
いう符号とは送るべき情報ビツトに剰余を付加し
たものを言い、線形符号とはそれが四則線形演算
のみによつて構成されたものであることを意味し
ている。線形符号の最も簡単な例はパリテイ符号
である。例えば奇数パリテイの場合は１ビツトの
パリテイビツトを剰余として付加することによつ
て、１ビツトの誤り検出を行うことができるもの
である。

このような線形符号を生成するための符号化演
算の方法としては、第１の方法として、ｋビツト
の情報点数に対応するｍビツトの付加検査点のす
べてを記憶したメモリテーブルを用いる方法があ
る。これはｍビツトの組合わせからなるそれぞれ
の情報点に対して、付加すべき検査点のビツトパ
ターンが１：１に対応することから、ｋビツトの
情報点数に対応したｍビツトの付加検査点をテー
ブル化し、これを参照することによつて付加すべ
き検査点を求めて符号化するものであるが、情報
点数ｋが大きい場合作成すべきテーブルのメモリ
量が増大する欠点がある。

また第２の方法としてｋビツトの情報をＰ
（ｘ）なる多項式の係数におきかえ、多項式Ｐ
（ｘ）にｍ次の項ｘ^mを乗じたのち剰余を求めるた
めの多項式（生成多項式）Ｇ（ｘ）で割算を行つ
て、剰余ｋ（ｘ）を求める演習を行う方法があ
る。しかしながらこの方法によつた場合は、剰余
を求めるためにデータの１ビツトシフトと加算と
をｋ回繰り返して行う必要があり、演算に時間が
かゝる欠点があつた。

発明の目的 本発明はこのような従来技術の問題点を解決し
ようとするものであつて、その目的、ｋビツトの
情報点を一定のビツト数k′ごとに区切り、k′ビツ
ト単位に予め作成されているテーブルの参照と加
算との演習を繰り返えすことによつて、符号化に
必要なテーブルにおけるメモリ容量を減少させる
とともに、演習回数を減少させることによつて演
算速度を向上することが可能な、符号化演算回路
を提供することにある。

発明の実施例 第１図は本発明の符号化演算回路の原理を説明
するための図である。同図においては情報点数ｋ
が11ビツト、検査点数ｍが４ビツトで生成多項式
Ｇ（ｘ）がＧ（ｘ）＝x⁴＋x⁸＋１である場合に、
演算単位k′を４ビツトとして情報点を４ビツト単
位に３区分に分割した演算を通常の計算方法によ
つて行つた場合を例示しており、前述の第２の従
来方法に対応するものである。すなわち同図にお
いては11ビツトの情報を（11010010110）とし、
これに４ビツトの０を付加した情報
（0110100101100000）を生成多項式（11001）で割
算を行つて、剰余として（1101）を得ることが示
されている。

また第２図は第１図に示された演算を、４ビツ
トごとに分割して各区分ごとに演算を行う場合の
計算方法を説明するための図である。同図におい
てａは、第１区分（0110）を生成多項式
（11001）で割算を行つて、剰余（0100）を得るこ
とを示している。また(b)においては、第２区分に
対応する割算における被除数（1101）（第１図に
おいてで示す）は第２区分（1001）と第１区分
における剰余（0100）とを加算して得られたもの
であり、これを生成多項式（11001）で割算を行
つて剰余（0001）を得ることが示されている。さ
らにｃにおいては、第３区分に対応する割算にお
ける被除数（0111）（第１図においてで示す）
は第３区分と第２区分における剰余（0001）とを
加算して得られたものであり、これを生成多項式
（11001）で割算を行つて剰余（1101）を得ること
が示されている。剰余（1101）は前述のように所
要の検査点である。

一般にｋビツトからなる情報点を生成多項式Ｇ
（ｘ）で割算を行つてｍビツトからなる検査点を
得る場合に、情報点をk′（k′＝ｍ）ビツトごとに
区分し、第１区分にｍビツトの０を付加した情報
を生成多項式Ｇ（ｘ）で割算を行つて得られた剰
余と第２区分とを加算して得られた情報にｍビツ
トの０を付加して第２区分に対応する被除数を
得、第２区分に対応する被除数を生成多項式Ｇ
（ｘ）で割算を行つて得られた剰余と第３区分と
を加算して得られた情報にｍビツトの０を付加し
て第３区分に対応する被除数を得、以下同様の手
続きを繰り返して最後に得られた被除数を生成多
項式で割算を行つて得られた剰余として検査点が
得られることは明らかである。

従つて、いまk′ビツトからなるすべての情報点
について、これを生成多項式Ｇ（ｘ）で割算を行
つたときの剰余をテーブルとして予め求めておけ
ば、ｋビツトの情報点をk′ビツトごとに区分し、
k′ビツト単位にテーブルの参照と参照結果と次の
区分の情報との加算とを行つて、次の区分に対応
する被除数を得る手続きを繰り返すことによつて
検査点を求めることができ、このようにすること
によつて、ｋビツトの情報点数に対応するｍビツ
トの付加検査点のすべてを記憶したテーブルを用
いる場合に比べて、テーブルに必要なメモリ容量
を減少することができ、また多項式Ｐ（ｘ）にｍ
次の項ｘ^mを乗じたのち生成多項式Ｇ（ｘ）で割
算を行つて剰余を求める演算方法に比べて演算回
数を減少して演算速度を向上することができる。

第３図は本発明の符号化演算回路の一実施例の
構成を示している。同図においては第１図に例示
された演算を行う場合の構成を示し、１，２，３
はそれぞれk′ビツト（こゝではk′＝４）のレジス
タであつてこれらに11ビツトの情報点
（11010010110）を下位から４ビツトごとに区切つ
てセツトする。上位のレジスタに空位を生じた場
合は、ここに０をセツトするものとする。４，
５，６はテーブル変換回路であつてk′（＝４）ビ
ツトの情報点を生成多項式（11001）で割算した
ときの剰余を各情報点の情報をアドレスとして記
憶するテーブルを具えている。７，８は加算回路
である。

第３図において、上位のレジスタ１から読出さ
れた情報（0110）は、テーブル変換回路４にアド
レスとして入力されることによつて、テーブル変
換回路４から所要の剰余（0100）が出力される。
次に加算回路７は第２位のレジスタ２から読出さ
れた情報（1001）とテーブル変換回路４から出力
された剰余（0100）とを加算して、第２区分に対
応する被除数（1101）を出力する。加算回路７の
出力情報（1101）はテーブル変換回路５にアドレ
スとして入力されることによつて、テーブル変換
回路５から所要の剰余（0001）が出力される。次
に加算回路８は下位のレジスタ３から読出された
情報（0110）とテーブル変換回路５から出力され
た剰余（0001）とを加算して、第３区分に対応す
る被除数（0111）を出力する。加算回路８の出力
情報（0111）はテーブル変換回路６にアドレスと
して入力されることによつて、テーブル変換回路
６から所要の剰余（1101）が出力される。剰余
（1101）は11ビツトの情報点（11010010110）に対
応する検査点である。なお第３図において、テー
ブル変換回路４，５，６におけるテーブルの内容
は同一であり、従つて各区分における割算を順次
行うようにすることによつて、同一のテーブルを
使用することが可能である。

第４図は情報点の区切りビツト数k′＝４に対応
した生成多項式Ｇ（ｘ）＝x⁴＋x³＋１に対する剰
余を求める変換テーブルを示し、左欄の情報をア
ドレスとして入力することによつて、右欄の変換
パターンが出力される。

第４図の変換テーブルは次のようにして作成す
ることができる。いま、k′ビツトからなるあるパ
ターンを多項式の係数におきかえこれをP′（ｘ）
とすると、P′（ｘ）に対応する所要の変換パター
ンは、P′（ｘ）にk′次の項ｘ^k′を乗じた多項式ｘ^k
′・P′（ｘ）を生成多項式Ｇ（ｘ）で割つて得ら
れた剰余R′（ｘ）に対応する。従つてk′＝４とし
て、例えばパターン（1011）に対応する変換パタ
ーンは、次のようにして求められる。すなわち、
パターン（1011）に対応する多項式はP′（ｘ）＝
x³＋ｘ＋１であるから、これにx⁴を乗じた多項式
x⁴・Ｐ（ｘ）＝x⁷＋x⁵＋x⁴を生成多項式Ｇ（ｘ）＝
x⁴＋x³＋１で割ることによつて剰余Ｒ（ｘ）＝x²
＋１が得られ、従つてこれに対応する４ビツトの
パターン（0101）を所要の変換パターンとすれば
よい。

第５図は上述のごとき変換パターンを求める演
算を通常の割算の計算方法に対応させて示したも
のであり、多項式x⁴・Ｐ（ｘ）に対応するパター
ン（10110000）を生成多項式Ｇ（ｘ）に対応する
パターン（11001）で割算することによつて、剰
余Ｒ（ｘ）に対応して変換パターン（0101）が得
られることが示されている。

以上、区切りビツト数k′が検査点のビツト数ｍ
に等しい場合について説明したが、本発明の符号
化演算回路は区切りビツト数k′が検査点のビツト
数ｍに等しくない場合にも適用できる。

第６図は本発明の符号化演算回路の第２の実施
例の構成を示したものである。同図は区切りビツ
ト数k′＝５、検査点ビツト数ｍ＝４、すなわち
k′＞ｍの場合を示している。１１，１２，１３は
それぞれ５ビツトのレジスタ、１４，１５，１６
はそれぞれテーブル変換回路、１７，１８は加算
回路、１９，２０は桁変換回路である。第６図に
おいては、第３図におけると同じ情報点に対し
て、同じ生成多項式によつて検査点を求める場合
が例示されている。

また第７図は第６図の各テーブル変換回路にお
いて用いられる変換テーブルを示したものであ
り、左欄における５ビツトの情報点をアドレスと
して入力することによつて、右欄における４ビツ
トの変換パターンを得ることができる。

第６図において、それぞれ５ビツトからなるレ
ジスタ１１，１２，１３に対して、11ビツトの情
報点（11010010110）を下位から５ビツトごとに
区切つてセツトし、上位レジスタ１１における空
位には０をセツトする。上位レジスタ１１から読
出された情報パターン（00001）は、テーブル変
換回路１４にアドレスとして入力されることによ
つて、第７図の変換テーブルによつてテーブルパ
ターン（1001）が出力される。変換パターン
（1001）は桁変換回路１９を経てその下位に０に
付加され、加算回路１７においてレジスタ１２か
ら読出された第２区分の情報（10100）と加算さ
れて、出力情報（00110）を得る。加算回路１７
の出力情報（00110）はテーブル変換回路１５に
アドレスとして入力されることによつて、変換テ
ーブルによつて変換パターン（0100）が出力され
る。変換パターン（0100）は桁変換回路２０を経
てその下位に０を付加され、加算回路１８におい
てレジスタ１３から読出された第３区分の情報
（10110）と加算されて、出力情報（11110）を得
る。加算回路１８の出力情報（11110）はテーブ
ル変換回路１６にアドレスとして入力されること
によつて、変換テーブルによつて変換パターン
（1101）が出力される。変換パターン（1101）は
所要の検査点である。

第６図の実施例において、テーブル変換回路か
ら出力される変換パターンの下位に０を付加する
のは、加算回路において加算されるべき次位のレ
ジスタの出力パターンと桁数を揃えるためであ
る。なおここで０を付加する代りに変換テーブル
における変換パターンの下位にあらかじめ０を付
加しておいてもよい。なお第７図に示された変換
テーブルの作成方法は、第４図に示された変換テ
ーブルの作成方法と同様である。

第８図は本発明の符号化演算回路の第３の実施
例の構成を示している。同図は区切りビツト数
k′＝３、検査点ビツト数ｍ＝４、すなわちk′＜ｍ
の場合を示している。２１〜２４はそれぞれ３ビ
ツトのレジスタ、２５〜２８はそれぞれ第４図に
示された変換テーブルを有するテーブル変換回
路、２９，３０，３１は桁変換回路、３２〜３５
は加算回路である。第８図においては、第３図に
おけると同じ情報点に対して、同じ生成多項式に
よつて検査点を求める場合が例示されている。

第８図において、それぞれ３ビツトからなるレ
ジスタ２１〜２４に対して11ビツトの情報点
（11010010110）を下位から３ビツトごとに区切つ
てセツトし、上位レジスタ２１における空位には
０をセツトする。上位レジスタ２１から読出され
た情報パターン（011）はパターン変換回路２５
にアドレスとして入力され、第４図に示された変
換テーブルによつて変換パターン（0010）が読出
される。なおこの場合のアドレスは最上位に０を
付加して（0011）としてテーブルを参照するもの
とする。出力された変換パターン（0010）は、桁
変換回路２９を経て上位３ビツトと下位１ビツト
に分割され、上位３ビツト（001）は加算回路３
２において第２区分のレジスタ２２の情報
（010）と加算されて、出力情報（011）を得る。
加算回路３２の出力情報（011）はテーブル変換
回路２６にアドレスとして入力され、変換テーブ
ルによつて、変換パターン（0010）を得る。テー
ブル変換回路２６の出力パターン（0010）は桁変
換回路３０を経て上位３ビツトと下位１ビツトに
分割される。一方、桁変換回路２９における下位
１ビツトの情報はその下位に（00）を付加されて
（000）として出力され、加算回路３３は第３区分
のレジスタ２３の情報（010）と桁変換回路２９
の下位の情報（000）と桁変換回路３０の上位３
ビツト（001）とを加算して出力情報（011）を得
る。加算回路３３の出力情報（011）は、テーブ
ル変換回路２７にアドレスとして入力されること
によつて、変換パターン（0010）が得られるが、
この情報は桁変換回路３１を経て上位３ビツト
（011）と下位１ビツトに対応する情報に分割され
る。加算回路３４は第４区分のレジスタ２４の情
報（110）と桁変換回路３０の下位１ビツトに対
応する情報（000）と桁変換回路３１の上位３ビ
ツト（001）とを加算して出力情報点（111）を得
る。加算回路３４の出力情報（111）はテーブル
変換回路２８にアドレスとして入力されることに
よつて、変換パターン（1101）が得られる。桁変
換回路３１はその下位１ビツトの情報に対し下位
に（000）を付加して（0000）として出力し、加
算回路３５はこれにテーブル変換回路２８の変換
パターン（1101）を加算して所要の検査点情報
（1101）を出力する。

このように区切りビツト数k′が検査点ビツト数
より小さい場合には、変換テーブルから得られる
変換パターンのビツト数が区切りパターンのビツ
ト数より多くなる。この場合の加算は両パターン
を上位側に詰めて桁を揃えるようにし、変換パタ
ーンにおける余分のビツトは下位に０を付加して
次位の区切りパターンと桁を揃えて加算を行えば
よい。

発明の効果 以上説明したように本発明の符号化演算回路に
よれば、ｋビツトの情報点を下位からk′（k′＜
ｋ）ビツトごとに区切つて上位区分から順に、
k′ビツトの情報点を生成多項式Ｇ（ｘ）で割算し
て得られたｍビツトの剰余をk′ビツトの情報点に
対する検査点の変換パターンとして記憶する変換
テーブルによつて変換して変換パターンを求め、
求められた変換パターンを次位区分のパターンに
加算して加算結果のパターンに対応する変換パタ
ーンを再び前記変換テーブルから求める手順を繰
り返すことによつて、最下位の区分のパターンと
前段において求められた変換パターンの加算結果
に対応する変換パターンを所要の検査点として出
力するようにしたので、ｋビツトの情報点に対す
るｍビツトの付加検査点のすべてを記憶したテー
ブルを用いる場合に比べて、符号化に必要なテー
ブルにおけるメモリ容量を減少させることがで
き、また多項式Ｐ（ｘ）にｍ次の項ｘ^mを乗じた
のち生成多項式Ｇ（ｘ）で割算を行つて剰余とし
て検査点を求める場合に比べ、演習回数を減少さ
せ従つて演算速度を向上させることができる。

【図面の簡単な説明】

第１図は本発明の符号化演算回路の原理を説明
するための図、第２図は第１図に示された演算例
を４ビツトごとに区切つて行う場合の計算方法を
説明するための図、第３図は本発明の符号化演算
回路の一実施例の構成を示す図、第４図は情報点
を４ビツトごとに区切つて演算を行う場合の剰余
を求めるための変換テーブルを示す図、第５図は
第４図に示された変換テーブルにおける変換パタ
ーンを求めるための計算方法を説明するための
図、第６図は本発明の符号化演算回路の第２の実
施例の構成を示す図、第７図は第６図の実施例に
おいて用いられる変換テーブルを示す図、第８図
は本発明の符号化演算回路の第３の実施例の構成
を示す図である。 １，２，３……４ビツトレジスタ、４，５，６
……テーブル変換回路、７，８……加算回路、１
１，１２，１３……５ビツトレジスタ、１４，１
５，１６……テーブル変換回路、１７，１８……
加算回路、１９，２０……桁変換回路、２１〜２
４……３ビツトレジスタ、２５〜２８……テーブ
ル変換回路、２９，３０，３１……桁変換回路、
３２〜３５……加算回路。

Claims (1)

【特許請求の範囲】
1. １ ｋビツトの情報点に対して生成多項式Ｇ
   （ｘ）によつてｍビツトの検査点を求めてｎ（＝
   ｋ＋ｍ）ビツトの符号語を生成する符号化演算に
   おいて、k′（k′＜ｋ）ビツトの情報点を生成多項
   式Ｇ（ｘ）で割算して得られたｍビツトの剰余を
   k′ビツトの情報点に対する検査点の変換パターン
   として記憶する変換テーブルを具え、ｋビツトの
   情報点を下位からk′ビツトごとに区切つて上位区
   分から順に該区分のパターンに対応する変換パタ
   ーンを前記変換テーブルから求め、求められた変
   換パターンを次位区分のパターンに加算して加算
   結果のパターンに対応する変換パターンを再び前
   記変換テーブルから求め、以下同様の手順を繰り
   返すことによつて最下位の区分のパターンと前段
   において求められた変換パターンとの加算結果に
   対応する変換パターンを所要の検査点として出力
   することを特徴とする符号化演算回路。