JPH077919B2

JPH077919B2 - ２進情報変換回路

Info

Publication number: JPH077919B2
Application number: JP61042220A
Authority: JP
Inventors: 善則天野; 史郎辻; 信義木原; 宏壮武内
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1986-02-27
Filing date: 1986-02-27
Publication date: 1995-01-30
Anticipated expiration: 2010-01-30
Also published as: JPS62199122A

Description

【発明の詳細な説明】産業上の利用分野本発明なリードソロモン符号を用いた誤り訂正部の２進
情報変換回路に関する。

従来の技術情報列a₀,a₁,……,ak_-1を多項式表現Ｓ（ｘ）を次式で
示す。

Ｓ（ｘ）＝a₀xk^-1＋a₁xk^-2＋……ak_-2x＋ak_-1 ……
（１）リードソロモン符号のｍ次生成多項式Ｇ（ｘ）を用いて
符号語を生成し、それを多項式表現したものをF₁（ｘ）
として次式で示す。

F₁（ｘ）＝a₀xn^-1＋a₁xn^-2＋……ak_-1xn^-k ＋b₀xm^-1＋……＋bm_-2x＋bm_-1 ……（２）ここでｋは情報部の長さ、ｍは検査符号の長さ、ｎは符
号語の長さ（ｎ＝ｍ＋ｋ）を示す。

このように生成される符号語を送信信号とし、伝送して
受信側において、検査符号により伝送中に生じた誤りの
訂正が行なわれる。誤り訂正はシンドロームを生成する
ことにより誤り位置情報と誤りパターンを算出すること
により行なわれる。ここで得らる誤り位置情報は、例え
ば式（２）でa₁が誤った場合、誤り位置情報としてｎ−
２が得られる。ところで、訂正する際、誤り位置情報よ
りa₁が蓄えられているメモリのアドレス値を算出する必
要がある。一般にメモリには式（２）においてa₀がアド
レス０、a₁がアドレス１、……の場所に書込まれてい
る。従って、符号長ｎを28とした時、０→27,1→26,…
…,26→1,27→０というように誤り位置情報から実際の
メモリのアドレス値に変換しなければならない。以上の
ような動作を実現する回路として第４図に示すようなRO
Mを使用したものが考えられる。ROMへの入力としてEL0
〜EL4の５ビットの誤り位置情報からなりROM内で変換を
行った後、アドレス信号としてA₀〜A₄を出力するもので
ある。

発明が解決しようとする問題点上記のようにROMを用いた構成では、符号長さの長さが
変わるとROMのデータを変更しなければならない。従っ
てLSI化を考えた場合、ROMを内蔵してしまうと符号長を
固定しなければならないため汎用性がなくなる。汎用性
を保つにはROMを外付けしなければならないなど問題が
多い。

本発明はこのような問題点を考慮して、ROMを使用せず
に、LSI化に適した２進情報変換回路を提供するもので
ある。

問題点を解決するための手段本発明はシンドロームより得られた誤り位置情報よりメ
モリのアドレス信号を生成するに際し、符号長ｎより１
を引いた２進情報の各ビットを反転する手段と、反転し
た結果と誤り位置情報を加算する手段と、加算した結果
を反転する手段を備え、誤り位置情報から符号語の蓄え
られているメモリのアドレス信号を生成する２進情報変
換回路である。

作用本発明は上記したとおり、インバータと加算器によりア
ドレス信号を生成することにより簡単な回路構成で実現
することができる。

実施例まず、本発明で用いた誤り訂正符号であるリードソロモ
ン符号について説明する。GF（２）上でのｌ次の既約多
項式Ｆ（ｘ）を考えた場合、“0"と“1"の元しか存在し
ないのでGF（２）上ではＦ（ｘ）は根を持たない。そこ
で、Ｆ（ｘ）＝０を満足する根αを考える。このとき零
元を含むαのべき乗で表わされる2n個の相異なる元0,α
⁰,α¹,……，α²l^-2は拡大体のGF（2l）を構成する。GF
（2l）の各元はα^０（＝１），α₁,α²,……，αl^-1の
線形結合として表現することができる。

今、情報別a₀,a₁,……,ak_-1を多項式表現すると、前記
したように（１）式Ｓ（ｘ）＝a₀xk^-1＋a₁xk^-2＋……ak_-2x＋ak_-1 ……
（１）となる。リードソロモン符号のｍ次生成多項式Ｇ（ｘ）
は（３）式として表わされる。この生成多項式Ｇ（ｘ）に
より得られる符号語は検査符号ｍ個、最小距離（ｍ＋
１）となる。符号語を生成するには、まずxm・Ｓ（ｘ）
を生成多項式Ｇ（ｘ）で割り、剰除Ｒ（ｘ）を求める。
このとき商をＱ（Ｘ）とする xmS（ｘ）＝Ｑ（ｘ）Ｇ（ｘ）＋Ｒ（ｘ） ……（４）となる。ここでF₁（ｘ）＝xmS（ｘ）＋Ｒ（ｘ）とする
と F₁（ｘ）＝xmS（ｘ）＋Ｒ（ｘ）＝Ｑ（ｘ）Ｇ（ｘ） …
…（５）となりF₁（ｘ）はＧ（ｘ）で割り切れる。このときのF₁
（ｘ）の各係数列が符号語を表わす。剰除Ｒ（ｘ）をＲ（ｘ）＝b₀xm^-1＋b₁xm^-2＋……bm_-2x＋bm_-1 ……
（６）とすると、符号語の多項式表現F₁（ｘ）は F₁（ｘ）＝a₀xn^-1＋a₁xn^-2＋……＋ak_-1xn^-k＋b₀xm^-1 ＋……＋bm_-2x＋bm_-1 ……（２）となる。ここでｎは符号長を示す。（ｎ＝ｍ＋ｋ）この符号語を送信信号列と考えると、元の情報列a₀,a₁,
…ak_-1に検査符号列b₀,b₁,…,bm_-1を付加して送信する
ことになる。

受信信号系列をF₂（ｘ）、伝送中に生ずる誤り系列をｅ
（ｘ）とすると次式が成立する。

F₂（Ｘ）＝F₁（ｘ）＋ｅ（ｘ） ……（７）受信側では伝送中に発生した誤りの有無を調べるために
シンドロームを生成する。シンドロームは受信信号系列
を生成多項式Ｇ（ｘ）で割った剰除として求めることが
できる。

具体例として（８）式の４次生成多項式を用いた場合、Ｇ（ｘ）＝（ｘ−α^０）（ｘ−α^１）（ｘ−α^２）（ｘ
−α^３） ……（８）このとき、シンドロームS₀,S₁,S₂,S₃は（９）式で表わ
される。

この場合、２箇所までの誤りであれば、その誤りの位置
と誤りパターンを求めることができる。

受信信号の多項式表現F₂（ｘ）を次式で表わす。

ここで、は、元の情報ai,biの受信情報を示す。

今、誤りパターンとしてei,ejとすると F₂（ｘ）＝F₁（ｘ）＋eixi＋ejxj ……（11）が得られる。従って、シンドロームより次式が得られ
る。

（12）式より誤りパターンei,ejと誤り位置i,jを算出す
ることができる。

信号フォーマットとして第２図の場合を考える。Ｎブロ
ックを単位に誤り訂正を完結するとし、１ブロックの長
さは32、２系列のリードソロモン符号C₁,C₂は図中矢印
の方向に生成系列をとるものとし、ともに長さは４とす
る。

受信側では一旦Ｎブロック分の受信信号をメモリに書込
んだ後、C₁,C₂の順に誤り訂正を行なう。その際、生成
系列毎に逐次信号を読み出して行なわれる。第２図の信
号フォーマットを便宜上、そのままメモリ上に配置する
ことにし、下位５ビットのアドレス信号により縦方向の
位置を指定し、６ビット目以上のアドレス信号によりブ
ロック方向（横方向）の位置を指定するものとする。と
ころで、（10）式で示した受信信号において、C₁生成系
列では、第３図（ａ）に示すように下位５ビットのアド
レス信号が0,1,2,……の場所にはd₃₁,d₃₀,d₂₉,…の信号
が書込まれることになる。例えばd₂₉が誤っていたとす
ると誤り位置を算出した結果ｉ＝29が得られるが、誤り
の訂正を行なう際はメモリ上のアドレスに変換しなけれ
ばならない。すなわち、第３図（ａ）の列ではｉ＝29の
かわりに下位５ビットのアドレス２にする必要がある。
同様に０→31,1→30,……,30→1,31→０となるように算
出された誤り位置より、メモリのアドレス値に変換す
る。第３図（ｂ）にはC₂生成系列を示す。C₂の符号語の
長さは28であり、従ってこの場合は求まった誤り位置情
報から、０→27,1→27,2→25,……,26→1,27→０となる
ように変換しなければならない。

第１図に本発明による２進情報変換回路を示す。１はイ
ンバータ、２は５ビットのバイナリ加算器、３はインバ
ータである。インバータ１に符号長ｎから１を引いた２
進情報を入力する。ｎが28であれば、11011を入力す
る。この時インバータ１の出力は00100となる。誤り位
置情報が24、すなわち２進数表現で11000の時、加算器
２により出力として11100が得られる。従ってインバー
タ３によりアドレス信号として00011、10進表現で３が
得られる。これは符号長が28であれば24→３に変換され
ることから正常に動作されていることがわかる。第１図
の回路構成では符号長が32までしか対応できないがそれ
以上必要な時でもビット数を増加させるだけで適応でき
る。例えば符号長が50であれば第１図において６ビット
の構成とすればよい。又、この時、符号長が28であった
としても符号長から１を引いた２進情報値を011011とす
ればよい。

発明の効果以上説明したように、本発明によれば、インバータと加
算器による２進情報変換回路の実現で、ROMを使用する
ことなく回路が簡単となりLSI化に適したものとするこ
とができる。又、符号長を変えた場合にも同一の回路構
成で実現することができ実用的効果は大きい。

【図面の簡単な説明】

第１図は本発明における一実施例の２進情報変換回路の
回路図、第２図は誤り訂正符号の生成系列を示す信号フ
ォーマット図、第３図はアドレス変換の動作の説明図、
第４図は従来の２進情報変換回路を示す説明図である。１……インバータ、２……加算器、３……インバータ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者武内宏壮大阪府門真市大字門真1006番地松下電器産業株式会社内 (56)参考文献特開昭58−66159（ＪＰ，Ａ)

Claims

【特許請求の範囲】

【請求項１】リードソロモン符号を用いて誤り訂正を行
なうに際し、符号語の長さがｎ（ｎは正の整数）の場
合、（ｎ−１）の２進情報を反転する手段と、反転した
結果と誤り位置情報ｉ（ｉは正の整数、かつ０≦ｉ＜
ｎ）の２進情報を加算する手段と、加算結果を反転する
手段を備え、前記誤り位置情報ｉから符号語の蓄えられ
ているメモリのアドレス情報（ｎ−ｉ−１）に変換する
２進情報変換回路。