JPS6355815B2

JPS6355815B2 -

Info

Publication number: JPS6355815B2
Application number: JP573882A
Authority: JP
Inventors: Yasuo Sugyama
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1982-01-18
Filing date: 1982-01-18
Publication date: 1988-11-04
Also published as: JPS58123252A

Description

【発明の詳細な説明】この発明は、データ伝送において伝送路に生じ
た誤りを訂正するための誤り訂正符号の一種であ
る短縮巡回符号の符号化回路に関するものであ
る。

従来技術の構成を記述するに先立つて、従来の
短縮巡回符号について、簡単に説明する。

従来のガロア体GF（ｑ）上の符号長ｎ、情報記
号数ｋの短縮巡回符号（以後、ｑ元（ｎ、ｋ）短
縮巡回符号と略す）の符号語（Ｘ）の構成を、
第１図に示す。第１図に示すように、情報記号部
ｍ（Ｘ）が、符号語（Ｘ）の高次の部分を、検
査記号部（Ｘ）が、符号語（Ｘ）の低次の部
分を占めている。すなわち、（Ｘ）＝（Ｘ）X^m＋（Ｘ） …(1) である。ここで、ｍは検査シンボル数であり、即
ち符号長ｎ、情報記号数ｋであるとき、ｍ＝ｎ−
ｋであたえられる。また、この発明において表わ
れる数式演算（加算、乗算）は、すべてガロア体
GF（ｑ）でおこなわれる。

そして、符号語（Ｘ）は、生成多項式ｇ（Ｘ）
によつて割り切れなければならない。すなわち、（Ｘ）≡０ mod ｇ（Ｘ） …(2) ここで、記号≡は、合同式を示し、mod ｇ
（Ｘ）は、ｇ（Ｘ）によつて法をとることを示す。
また、ｇ（Ｘ）の次数はｍである。

このようなｑ元（ｎ、ｋ）短縮巡回符号の符号
語（Ｘ）は、情報記号部（Ｘ）を与えて、（Ｘ）≡−（Ｘ）X^m mod ｇ（Ｘ）
…(3) を満足するような検査記号部（Ｘ）を求めるこ
とによつて、生成できる。そして、式(3)は多項式
ｍ（Ｘ）X^mを生成多項式ｇ（Ｘ）で割算したとき
の剰余が（Ｘ）であることを意味している。

このような検査記号部（Ｘ）を求めるための
符号化回路のうち、フイードバツクシフトレジス
タを用いた形式のものが、第２図に示されてい
る。図において、１は入力端子、２は出力端子、
３は減算器、４は乗算器、５はスイツチ、M_1,1，
M_1,2，………，M_1,n-1，M_1,nは乗算器、R_1,1，
R_1,2，………，R_1,n-1，R_1,nはレジスタ、A_1,1，…
……，A_1,n-2，A_1,n-1は加算器である。

次に動作について説明する。まず最初に、スイ
ツチ５を閉にし、かつレジスタR_1,1、レジスタ
R_1,2，………、レジスタR_1,n-1、レジスタR_1,nの
値を０にする。次に入力端子１に、情報記号部
Ｘ（Ｘ）＝_K-1 〓ⁱ⁼⁰ _i Xⁱ …(4) の最高次の係数_k-1を入力する。従つて、レジ
スタR_1,nの内容がスイツチ５を通して、減算器３
に与えられているから、減算器３によつて入力
_ｋ−１からレジスタR_1,nの内容が減算される。減算
器３の出力は剰算器４によつて係数g_n ^-1をかけら
れる。乗算器４の出力は、乗算器M_1,1、乗算器
M_1,2，………、乗算器M_1,n-1、乗算器M_1,nに与え
られる。乗算器４の出力は、乗算器M_1,nによつ
て係数g_n-1をかけられ、さらに加算器A_1,n-1によ
つて、レジスタR_1,n-1の内容を加えられ、レジス
タR_1,nに納められる。乗算器４の出力は、乗算器
M_1,n-1によつて係数g_n-2をかけられ、さらに加算
器A_1,n-2によつて、レジスタR_1,n-2の内容を加え
られ、レジスタR_1,n-1に納められる。乗算器４の
出力は、乗算器M_1,2によつて係数g₁をかけられ、
さらに加算器A_1,1によつて、レジスタR_1,1の内容
を加えられ、レジスタR_1,2に納められる。乗算器
４の出力は、乗算器M_1,1によつて係数g₀をかけら
れ、レジスタR_1,1に納められる。ついで、情報記
号部（Ｘ）の最高次の次の係数_k-2を入力す
る。それを入力として、上記の動作を繰り返し、
レジスタR_1,1、レジスタR_1,2，………、レジスタ
R_1,n-1、レジスタR_1,nの内容を更新する。さら
に、つづけて、情報記号部（Ｘ）を高次の係数
の方から順次入力し、上記の動作を繰り返す。

最後に、情報記号部（Ｘ）の最低次の係数
_０を入力し、レジスタR_1,1、レジスタR_1,2，……
…、レジスタR_1,n-1、レジスタR_1,nの内容を更新
する。このとき、得られたレジスタR_1,n、レジス
タR_1,n-1，………、レジスタR_1,2、レジスタR_1,1
の内容が、検査記号部（Ｘ）の係数_n-1，_n
_−２，………，₁，₀にそれぞれ対応している。
ここで（Ｘ）＝_n-1 〓ⁱ⁼⁰ _i Xⁱ …(5) である。

この後、スイツチ５を開にし、入力端子１に０
を与えた上で、レジスタR_1,nの内容を、出力端子
２からとり出す。レジスタR_1,n、レジスタ
R_1,n-1，………、レジスタR_1,2、およびレジスタ
R_1,1の内容は、それぞれ、レジスタR_1,n-1、レジ
スタR_1,n-2，………、レジスタR_1,1の内容、およ
び乗算器M_1,1の出力に置き換えられる。

上記の動作をさらにｍ−１回繰り返すことによ
つて、出力端子２から所望の検査記号部ｒ（Ｘ）
を得ることができる。

このように、入力を情報記号部ｍ（Ｘ）とし、
多項式ｍ（Ｘ）X^mを生成多項式ｇ（Ｘ）によつて
割算した時の剰余多項式を求め、それを検査記号
部としてとり出せばよい。

従来のｑ元（ｎ、ｋ）短縮巡回符号の符号化回
路は、以上のように構成されているので、検査記
号部が低次の部分に固定されており、検査記号部
が低次の部分にないような短縮巡回符号の符号化
回路には使用できないという欠点があつた。

この発明はこれらの欠点を解消するためになさ
れたもので、検査記号部が低次の部分にないよう
なｑ元（ｎ、ｋ）短縮巡回符号の符号化回路を提
供するものである。

この発明の構成を記述するに先立つて、検査記
号部が低次の部分にないような短縮巡回符号につ
いて説明する。検査記号部が低次の部分にないよ
うなｑ元（ｎ、ｋ）短縮巡回符号の符号語Ｖ（Ｘ）
の構成を第３図に示す。第３図に示すように、情
報記号部が符号語Ｖ（Ｘ）の高次の部分と低次の
部分を占め、検査記号部ｒ（Ｘ）がその間の部分
を占めている。ここで、高次の情報記号部をm_u
（Ｘ）、低次の情報記号部をm_L（Ｘ）と表わすと、
符号語Ｖ（Ｘ）は、Ｖ（Ｘ）＝m_u（Ｘ）X^m+L＋ｒ（Ｘ）X^L＋m_L（Ｘ） …(6) と表わされる。そして、符号語Ｖ（Ｘ）は、生成
多項式ｇ（ｘ）によつて割り切れなければならな
い。すなわち、Ｖ（Ｘ）≡０ mod ｇ（Ｘ） …(7) この符号語Ｖ（Ｘ）において、高次の情報記号部
m_u（Ｘ）と低次の情報記号部m_L（Ｘ）とを与え
て、ｒ（Ｘ）X^L≡−m_uX^m+L −m_L（Ｘ） mod ｇ（Ｘ） …(8) を満足するような検査記号部ｒ（Ｘ）を求めたい。
Ｌは符号語Ｖ（ｘ）において、次数が低次の情報
記号部分の長さ（単位はシンボル）。一方、次数
が高次の情報記号の長さはＫ−Ｌ（シンボル）あ
り、両者の合計でＫシンボルの情報が符号語内に
存在する。ｕは次数が高次の情報シンボル部分を
示す添字（サフイクス）であり、例えばm_u（ｘ）
は次数が高次の情報記号部分の多項式を示しr_u
（ｘ）は高次の情報記号部分の多項式m_u（ｘ）に
よる検査記号成分を示す。そのような検査記号部
ｒ（Ｘ）を求めるため、検査記号部ｒ（Ｘ）を高次
の情報記号部m_u（Ｘ）による検査記号部成分r_u
（Ｘ）と低次の情報記号部m_L（Ｘ）による検査記
号成分r_L（Ｘ）とに分解する。すなわち、 r_u（Ｘ）≡−m_u（Ｘ）X^m mod ｇ（Ｘ） …(9) r_L（Ｘ）X^L≡−m_L（Ｘ） mod ｇ（Ｘ） …(10) ｒ（Ｘ）＝r_u（Ｘ）＋r_L（Ｘ） …(11) である。したがつて、入力m_u（Ｘ）に対して出力
r_u（Ｘ）を求め、入力m_L（Ｘ）に対して出力r_L（Ｘ）
を求め、２つの出力r_u（Ｘ）とr_L（Ｘ）を加算し
て、所望の検査記号部ｒ（Ｘ）を得るという手法
をとる。

２つの検査記号成分r_u（Ｘ）とr_L（Ｘ）のうち、
r_u（Ｘ）は容易に求めることができる。すなわち、
式(9)は、多項式m_u（Ｘ）X^mを生成多項式ｇ（Ｘ）
で割算したときの剰余が、r_u（Ｘ）であることを
意味している。このことは、式(3)のもつ意味と全
く同一であり、r_u（Ｘ）を求めるための回路は、
従来の短縮巡回符号の符号化回路と全く同一の形
式となる。

次に、残りの検査記号成分r_L（Ｘ）の求め方を
述べる。まず、ｆ（Ｘ）X^L≡−１ mod ｇ（Ｘ）…(12) なる多項式ｆ（ｘ）ｆ（Ｘ）＝_n-1 〓ⁱ⁼⁰ f_iXⁱ …（13）を、回路設計に先立つて求めておく。式(10)と式(11)
とから、 r_L（Ｘ）≡−m_L（Ｘ）ｆ（Ｘ） mod ｇ（Ｘ）
…（14）が成立する。この式（14）は、入力m_L（Ｘ）を多
項式ｆ（Ｘ）で乗算したのち、多項式ｇ（Ｘ）で割
算すれば、その剰余がr_L（Ｘ）であることを意味
している。

以下第４図に示すこの発明の一実施例について
説明する。第４図において、１は入力端子、２は
出力端子、３は減算器、４は乗算器、５はスイツ
チ、６は入力端子、７は出力端子、８は乗算器、
９はスイツチ、１０は加算器、１１は出力端子、
M_1,1，M_1,2，………，M_1,n-1，M_1,nは乗算器、
R_1,1，R_1,2，………，R_1,n-1，R_1,nはレジスタ、
A_1,1，………，A_1,n-2，A_1,n-1は加算器、M_2,1，
M_2,2，………，M_2,n-1，M_2,nは乗算器、R_2,1，
R_2,2，………，R_2,n-1，R_2,nはレジスタ、A_2,1，
A_2,2，………，A_2,n-1，A_2,nは加算器、M_3,1，
M_3,2，………，M_3,n-1，M_3,nは乗算器である。

第４図の上半分が、入力m_u（Ｘ）に対して出力
r_u（Ｘ）を求める回路であり、第４図の下半分が、
入力m_L（Ｘ）に対して出力r_L（Ｘ）を求める回路
であり、右端の加算器１０が出力r_u（Ｘ）と出力
r_L（Ｘ）を加算して所望の検査記号部ｒ（Ｘ）を求
める回路である。

次に、動作について説明する。第４図の上半分
は、入力m_u（Ｘ）に対して出力r_u（Ｘ）を求める
回路であり、第２図に示された従来の、入力ｍ
（Ｘ）に対して出力ｒ（Ｘ）を求める短縮巡回符号
の、符号化回路の動作と、全く同一の動作をす
る。したがつて、入力m_u（Ｘ）に対して出力r_u
（Ｘ）を求める回路の動作の説明は省略する。

次に、第４図の下半分の入力m_L（Ｘ）に対して
出力r_L（Ｘ）を求める回路の動作を説明する。ま
ず最初に、スイツチ９を閉にし、かつレジスタ
R_2,1、レジスタR_2,2，………、レジスタR_2,n-1、
レジスタR_2,nの値を０にする。次に入力端子６
に、低次の情報記号部m_L（Ｘ） m_L（Ｘ）＝_L-1 〓ⁱ⁼⁰ m_L,iXⁱ …（15）の最高次の係数m_L,L-1を入力する。そして、その
値が、乗算器M_3,1、乗算器M_3,2，………、乗算器
M_3,n-1、乗算器M_3,nに与えられる。乗算器M_3,1
は、入力m_L,L-1と係数f₀との乗算をおこなう。乗
算器M_3,2は、入力m_L,L-1と係数f₁との乗算をおこ
なう。乗算器M_3,n-1は、入力m_L,L-1と係数f_n-2と
の乗算をおこなう。乗算器M_3,nは、入力m_L,L-1と
係数f_n-1との乗算をおこなう。

一方、レジスタR_2,nの内容が、スイツチ９を通
つて乗算器８によつて係数（−g_n ^-1）をかけられ
る。乗算器８の出力は、乗算器M_2,1、乗算器
M_2,2，………、乗算器M_2,n-1、乗算器M_2,nに与え
られる。乗算器M_2,1は、乗算器８の出力と係数g₀
との乗算をおこなう。乗算器M_2,2は、乗算器８の
出力と係数g₁との乗算をおこなう。乗算器M_2,n-1
は、乗算器８の出力と係数g_n-2との乗算をおこな
う。乗算器M_2,nは、乗算器８の出力と係数g_n-1と
の乗算をおこなう。

ついで、加算器A_2,nは乗算器M_2,nの出力と乗算
器M_3,nの出力とレジスタR_2,n-1の内容を加算す
る。その加算器A_2,nの出力がレジスタR_2,nに納め
られる。加算器A_2,n-1は乗算器M_2,n-1の出力と乗
算器M_3,n-1の出力とレジスタM_2,n-2の内容を加算
する。その加算器A_2,n-1の出力がレジスタR_2,n-1
に納められる。加算器A_2,2は乗算器M_2,2の出力と
乗算器M_3,2の出力とレジスタR_2,1の内容を加算す
る。その加算器A_2,2の出力がレジスタR_2,2に納め
られる。加算器A_2,1は、乗算器M_2,1の出力と乗算
器M_3,1の出力を加算する。その加算器A_2,1の出力
がレジスタR_2,1に納められる。

ついで、低次の情報記号部m_L（Ｘ）の最高次の
係数m_L,L-2を入力する。それを入力として上記の
動作を繰り返し、レジスタR_2,1、レジスタR_2,2，
………、レジスタR_2,n-1、レジスタR_2,nの内容を
更新する。

さらにつづけて、低次の情報記号部m_L（Ｘ）を
高次の係数の方から順次入力し、上記の動作を繰
り返す。

最後に、低次の情報記号部m_L（Ｘ）の最低次の
係数m_L,0を入力し、レジスタR_2,1、レジスタR_2,2，
………、レジスタR_2,n-1、レジスタR_2,nの内容を
更新する。このとき得られたレジスタR_2,n、レジ
スタR_2,n-1，………、レジスタR_2,2、レジスタ
R_2,1の内容が、検査記号成分r_L（Ｘ）の係数r_L,n-1，
r_L,n-2，………，r_L,1，r_L,0にそれぞれ対応してい
る。ここで、 r_L（Ｘ）＝_n-1 〓ⁱ⁼⁰ r_L,iXⁱ …（16）である。

この後、スイツチ５とスイツチ９を開にし、入
力端子１と入力端子６とに０を与えた上で、レジ
スタR_1,nの内容とレジスタR_2,nの内容を、加算器
１０で加算し、出力端子１１からとり出す。レジ
スタR_1,n、レジスタR_1,n-1，………、レジスタ
R_1,2、およびレジスタR_1,1の内容は、それぞれ、
レジスタR_1,n-1、レジスタR_1,n-2，………、レジ
スタR_1,1の内容、および乗算器M_1,1の出力に置き
換えられる。レジスタR_2,n、レジスタR_2,n-1，…
……、レジスタR_2,2、およびレジスタR_2,1の内容
は、それぞれ、レジスタR_2,n-1、レジスタR_2,n-2，
………、レジスタR_2,1の内容、および加算器A_2,1
の出力に置き換えられる。

上記の動作をさらにｍ−１回繰り返すことによ
つて、出力端子１１から所望の検査記号部ｒ（Ｘ）
を得ることができる。

このように、第１の入力を高次の情報記号部
m_u（Ｘ）とし、多項式m_u（Ｘ）X^mを生成多項式ｇ
（Ｘ）によつて割算した時の第１の剰余多項式を
求め、かつ、第２の入力を低次の情報記号部m_L
（Ｘ）とし、多項式m_L（Ｘ）に多項式ｆ（Ｘ）を乗
算し、さらに生成多項式ｇ（Ｘ）によつて割算し
た時の第２の剰余多項式を求め、それら２つの順
余多項式を加算することによつて検査記号部ｒ
（Ｘ）を得ることができる。

以上のように、この発明によれば、符号語にお
ける検査記号部の位置が低次に固定されていない
ため、検査記号部が符号語の中でどのような位置
を占めていようとも適用できるという利点があ
る。

【図面の簡単な説明】

第１図は、従来のｑ元（ｎ、ｋ）短縮巡回符号
の符号語の構成図、第２図は、従来のｑ元（ｎ、
ｋ）短縮巡回符号の符号化回路図、第３図は、こ
の発明の対象となる検査記号部が低次の部分にな
いようなｑ元（ｎ、ｋ）短縮巡回符号の符号語の
構成図、第４図は、この発明の検査記号部が低次
の部分にないようなｑ元（ｎ、ｋ）短縮巡回符号
の符号化回路の一実施例の図である。図中、１は、入力端子、２は、出力端子、３
は、減算器、４は、乗算器、５は、スイツチ、６
は、入力端子、７は、出力端子、８は、乗算器、
９は、スイツチ、１０は、加算器、１１は出力端
子、M_1,1は乗算器、M_1,2は乗算器、………，
M_1,n-1は乗算器、M_1,nは乗算器、R_1,1はレジス
タ、R_1,2はレジスタ、………，R_1,n-1はレジスタ、
R_1,nはレジスタ、A_1,1は加算器、A_1,n-1は加算器、
A_1,n-1は加算器、M_2,1は乗算器、M_2,2は乗算器、
………，M_2,n-1は乗算器、M_2,nは乗算器、A_2,1は
加算器、A_2,2は加算器、………，A_2,n-1は加算
器、A_2,nは加算器、R_2,1はレジスタ、R_2,2はレジ
スタ、………，R_2,n-1はレジスタ、R_2,nはレジス
タ、M_3,1は乗算器、M_3,2は乗算器、………，
M_3,n-1は乗算器、M_3,nは乗算器である。なお、図
中、同一あるいは相当部分には同一符号を付して
示してある。

Claims

【特許請求の範囲】１情報記号部が符号語の高次の部分と低次の部
分に分かれていて、検査記号部がその間の次数に
位置しているような短縮巡回符号の符号語を生成
する目的で、第１の入力を高次の情報記号部m_u
（ｘ）とし、多項式m_u（ｘ）x^mを次数ｍの生成多
項式ｇ（ｘ）によつて割算した時の第１の剰余多
項式を求めるための、フイードバツク係数として
生成多項式ｇ（ｘ）の係数をもつフイードバツク
シフトレジスタと、第２の入力を低次のＬ−１シ
ンボルからなる情報記号部m_L（ｘ）とし、多項式
m_L（ｘ）に多項式ｆ（ｘ）を乗算し、かつ、生成
多項式ｇ（ｘ）によつて割算した時の第２の剰余
多項式を求めるための、フイードフオワード係数
としてｆ（ｘ）X^L≡−1mod ｇ（ｘ）を満足する
多項式ｆ（ｘ）の係数をもち、フイードバツク係
数として生成多項式ｇ（ｘ）の係数をもつフイー
ドフオワード／フイードバツクシフトレジスタ
と、上記２つの剰余多項式を加算することによつ
て検査記号部を求めるための加算器とを有するこ
とを特徴とする短縮巡回符号の符号化回路。但し、Ｌは本発明における符号語Ｖ（ｘ）にお
いて次数が低次の情報記号部分の長さ（単位はシ
ンボル）である。一方、次数が高次の情報記号の
長さはＫ−Ｌ（シンボル）あり、両者の合計でＫ
シンボルの情報が符号語内に存在する。ｍは検査
シンボル数であり、即ち符号長ｎ、情報記号数ｋ
とするとき、ｍ＝ｎ−ｋであたえられる。ｕは次
数が高次の情報シンボル部分を示す添字（サフイ
クス）であり、m_u（ｘ）は次数が高次の情報記号
部分の多項式を示しr_u（ｘ）は高次の情報記号部
分の多項式m_u（ｘ）による検査記号成分を示す。