JPS60217735A - リ−ドソロモン符号・復号方式の誤り位置決定回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、ディジタルオーディオなどに用いる２シンボ
ル誤シ訂正可能なリードソロモン符号の、復号の一環で
ある誤シ位置の決定回路に関する。

従来の技術 ディジタルオーディオテープなどのディジタルオーディ
オでは２シンボル誤り訂正可能なリードソロモン符号が
使われている。リードソロモン符号の符号化は比較的簡
単であるが、その復号化は複雑である。ディジタルオー
ディオではＣＩ　（３２，２８）　リードソロモン符号
、Ｃ２（２８，２４）　リードソロモン符号をインタリ
ープを介して組合わす。括弧内の数字は、それぞれ符号
ブロック長でリードソロモン符号を形成するシンボル数
および情報シンボル数を示すものである。３−従ってＣ
１符号、Ｃ２符号ともに検量シンボル数は４個であシ、
リードソロモン符号の最小間隔ｄｍｉｎは５であシ、２
シンボルの訂正が可能である。このシンボルは通常１バ
イトで構成する。

以下、ＣＩ符号の復号を例にとって復号方式を説明する
。先ずシンドロームＳｏ＋　Ｓｌ＋　Ｓ！ｅ　ｓ、は次
式でめられる。

こ＼でＡｏ、・・・ｌ　ＡＩＩは各シンボルであル、α
は８次の原始多項式の根すなわち原始元である。そして
αｊはＧＦ（２＠）を構成する。符号誤シのない場合に
は、Ｓ０〜Ｓｓは零となる。いま、符号ブロックの最先
の桁（ＩＩＱＩＩ桁）から算えて第１桁の誤シを表わす
数をγ１とし、γｉ＝α　とおく。そして第０１桁、第
ｎ２桁の２つの誤°シが生じたときの誤り位置多項式と
して次式を考えるχはＧＦ（２”）の元である。

σ（χ）＝（１−αｎ１χ）（１−αｎ２χ）（２）上
式は展開されて、通常、次式で表わす。

σ（χ）＝１＋σ、χ＋σ２χ２（８］σ８．Ｃ２の訪
導方法は省略するが、（１）式のシンドローム８０〜Ｓ
、からめられるものである。

（８）式にＧＦ（２”）の元を次々に代入して行けば誤
シ位置ｎ１．ｎ２に対応するα−ｎ１．α−ｎ８でσ（
χ）＝０となることが（２）式よシわかる。

上記は、チェーンのアルゴリズムといわれるものである
が、従来、この方法による具体的回路構成は周知でない
。

発明の解決しようとする問題点 本発明の目的は％２シンボル誤９訂正リードンロモン符
号の復号に際し、チェーンの方法による誤シ位置決定の
具体的回路を提供することにある。

問題点を解決するだめの手段 本発明による誤り位置決定回路は、誤り位置多項式χ２
＋σ、χ＋σ２の変数χとして、原始多項式の根αのべ
き乗αｊ（ｊ：整数）をｊの昇順に順次投入して、前記
誤シ位置多項式が零になることを検知して誤シ位置を決
定する方式であって、 共通のクロックにょシ駆動される３つのシフトレジスタ
を有し、第１のシフトレジスタはＣ０（＝１）をプリセ
ットした後、その出力をα８倍する定数を有するＲＯＭ
メモリを介して入力側に帰還するシフト回路を、第２の
シフトレジスタ蝶σ、をプリセットした後、その出力を
α倍する定数を有するＲＯＭメモリを介して入力側に帰
還するシフト回路を、および第３のシフトレジスタは入
力が常にＣ２であるシフト回路を、それぞれ構成し、前
記３つのシフト回路の出力を合成して１合成出力が零に
なるときに出力する零判定回路に導き、該零判定回路の
出力パルスによって、前記シフトレジスタの共通のクロ
ックと同位相のクロックをカウントするカウンタの数値
をラッチすることで誤シ位置を決定することを特徴とす
るものである。

前記の手段においては、誤ル位置多項式の変数χに、原
始多項式の根αのべき乗αｊをｊの昇順に順次投入した
が、これけｊの降順に順次投入することでも同様に実施
可能である。すなわち、Ｍ個のシンボルからなるリード
ンロモン符号の復号において、αｊ１ｒ：ｊの降順にα
ト１より順次に投入する。このとき第１のシフトレジス
タはＣ２（トリをプリセットした後、その出方をα−３
倍する定数を有するＲＯＭメモリを介して入力側に帰還
するシフト回路を、第２のシフトレジスタはσ１α　を
プリセットした後、その出力をα−１倍する定数を有す
るＲＯＭメモリを介して入力側に帰還するシフト回路を
、および第３ノシフトレジスタは入力が常にσ、である
シフト回路を、それぞれ構成し、前記３つのシフト回路
の出力を合成して、合成出力が零になるときに出力する
零判定回路に導く。該零判定回路の出力パルスによって
、前記シフトレジスタの共通のクロックと同位相のクロ
ックをカウントするカウンタの数値をラッチすることで
誤シ位置を決定する。

なお、以下の説明および実施例はすべて、αｊをｊの昇
順に投入する場合について述べる。

本発明の主要部は、原始多項式の原始光αのべき乗αｊ
の発生と、誤ｐ位置多項式へのαｊの投入と、誤シ位置
多項式の零判定と、零判定のシンボル位置決定との４つ
の部分である。このうち前２者は一体の回路で行なう。

第１図は、このことを説明するために示した原理図であ
る。

誤シ位置多項式σ（χ）は通常（２１（ｓ＋の形式をと
るが、本発明では、次の相反多項式を用いる。

σ（χ）＝χ２＋σ、χ＋σ２　（４）この多項式では
、χ＝αｎ１．αｎ８でσ（χ）＝０となる。さて、χ
に投入するαのべき乗をＣ０（−’　）＋α、α２．・
・・Ｃ８とする。Ｃ１符号ではＮ＝３１．　Ｃ２符号で
はＮ＝２７である。従って各αｊを順次σ（χ）のχに
投入するということは、（４）式の第１項についていえ
ば、（Ｃ０）２．Ｃ２，Ｃ４，Ｃ６・・・とすることで
ある。つ−１９、α６＝１にグの乗算を続ければよい。

第２項についていえばσ１α０．σ１α、。

よい。従って、第１図に示すように、シフトレジスタ１
に最初α０をプリセットしておいて、その出力側をα３
倍して入力側に帰還する回路を構成し、シフトレジスタ
１を順次シフトすれば、シフトレジスタ１の出力はＭ１
項の各シンボルによる値を順次に出力する。同様にσ、
でプリセットしたシフトレジスタ２の出力をα倍して帰
還する回路を構成すれば、順次シフトすることで、第２
項の各シンボルによる値をシフトレジスタ２は順次に出
力する。シフトレジスタ３の出力はシフトごとに定数σ
、を出力し、第３項を示す。そして１合成回路４で、第
１項、第２項。

第３項の排他的論理和をとればσα）が得られる。

以上の説明でわかるよりに、σ（４は最初にプリセット
した状態で（Ｃ０）２＋σ、（Ｃ０）十〇、となり、次
にシフト回路１〜３を１回シフトすると（α）！＋σ□
α＋σ２９次のシフトで（Ｃ２）２＋σ、α２＋σ３．
。

となる。以下同様でＣ１符号ではχ＝αＳ′まで、Ｃ２
符号ではχ＝α１７になるまでシフトする。

ａ　ｔｙ）＝　ＯＶ　３スｎ　Ｊ　＞　１　、　イｉ　
ノ紡Ｊ（ＩＦ　ｈ　１１”＊　ｆ−Ｚ　ｓｉンボルの桁
数になる。

次に本発明の４つの主要部の後半の零判定と、零判定の
シンボル位置決定について述べる。零判定回路は、公知
の回路１例えば各ビットととＫ”１　＋＋とＥＸ−ＯＲ
をとり、すべてのＥＸ−ＯＲ回路の出力が１°“ならば
零と判定できる。シンボル位置決定には、シフトレジス
タ１〜５のシフトクロックと同一のクロックあるいは同
位相のクロックをカウントするカウンタを設ける。この
カウンタのカウント値はσ（χ）の変数χのαｊとして
のｊの値に等しいから、零判定回路の出力によって、カ
ウント値をラッチすればよい。

次に、先に記した（×α）回路、（ＸＣ２）回路につい
て説明する。Ｃ１符号、Ｃ２符号では、１シンボルが１
バイトであり、原始多項式は８次の多数式ｆ（χ）−χ
８＋χ４＋χ３＋χ２＋１　である。αはこの原始元で
、ベクトル表示では（０１００００００）となる。いま
、Ａ、＝（χ。χ、χ２χ３χ、χ、χ６χ７）とする
と、×αは、２つの多項式の積になる。

すなわち（χ。＋χ１χ＋χ２χ２＋χ、χ３＋・・・
＋χ、χ７）ｘ（０＋χ＋０・χ２＋・・・＋０・χ７
）従って χ。χ＋χ、χ２＋χ２χ３＋・・・＋χ６χ７＋χ、
χ８となる。最後の項χ８は原始多項式よりわかるよう
にχ４＋χ３＋χ２＋１に等しいから、上記の積をベク
トル表示で示すと、 （χ７χ。χ、＋χ７　χ２＋χ７　χ４　χ、χ６）
となる。これは次の８行８列のマトリクスｄをベクトル
（χ０χ１・・・χ７）Ｔに乗することに等しい。

同じように　Ｘα２も、省略するが８行８列のマトリク
スα２を考えればよい。これらのマトリクスα、α２に
よる積はＲＯＭメモリによって実現できる。ＲＯＭメモ
リを利用するので、高速な演算ができる。

実施例 第２図は、ＣＩ符号、Ｃ２符号について、本発明を実施
する具体的回路のブロック図を示し、第３図はそのタイ
ムチャートを示す。なお第２図の回路では、誤シ数をカ
ウントする回路を附加している。マルチプレクサ１１．
シフトレジスタ（１段）　１２．　ＲＯＭ　１３によっ
て、σ（χ）の７２項を、マルチプレクサ１４．シフト
レジスタ（１８）１５゜ＲＯＭ１６によってσ（χ）の
χ項を形成する。シフトレジスタ（１段）１７はＣ２項
を供給する。合成回路１８．１９は排他的論理和として
、前記３項を合成して゛零判定回路２０に入力する。上
記のシフト回路の動作は、先ず第３図に示すように信号
Ｂ１１か１０′になってマルチプレクサ１１．１４をＩ
Ｉ　ＯＩＩ側に切換え、同時に信号Ｂ１６を°°０゛に
することで、シフトレジスタ１２．１５．１７にそれぞ
れＣ０，σ１．σ２がプリセットされ、合成回路１９の
出力１９ａとしてσ（α０人　すなわち　（Ｃ０）２＋
σ１α０＋σ２　が表われる。また、このとき、信号Ｂ
１２　（ｉ−”０°°にして、誤り数ケカウントするカ
ウンタ２２．誤９位置数をカウントするカウンタ２１ヲ
クリアしておく。次に信号Ｂ１５．Ｂ１０にクロック信
号ケ印加して、シフトレジスタ１２．１５．１７　およ
びカウンタ２１ヲ動作させる。信号Ｂ１１はパ１“°と
なっているので、マルチプレクサ１１．１４は°′１“
側に切換わり、出力帰還回路が構成され、最初のシフト
で、シフトレジスタ１２の出力はＣ２，シフトレジスタ
１５の出力はσ１α、シフトレジスタ１７の出力はＣ２
となり、信号１９ａとしてσ（中が表われる。そしてシ
フトごとにσ（Ｃ２）、σ（Ｃ３）、・・・と変化して
ゆく。

なおこのとき信号Ｂ１５は１６号Ｂ１６と同位相のクロ
ック信号が印加されるから、カウンタ２１は前記シフト
回数をカウントしてゆく。

零“判定回路２０１Ｃは信号１９ａか入カレ、その値が
変化してゆき、信号誤り位置ｎｉ、　ｎ２　（図では４
．１５）に相当するαｎ１．αｎ２で、°“１°′を簡
易Ｂ２０として出力する０こ＼で、信号Ｂ１９は、信方
間６のクロックと同ル」するクロックで、＋＋　１　＋
＋判定出力の信号Ｂ２０全確実にフェッチするための信
号である〇 信号Ｂ２０がＣ４で“１°°になると、ラッチ回路２３
は、カウンタ２１のそのときのカウント値４をラッチす
る。このときラッチ回路２４の出力は零である。そして
信号Ｂ２０がα１３で再ひ°°１“′になると、ラッチ
回路２３はカウント値１３をラッチし、ラッチ回路２４
は前回のカウント値４全ラッチする。すなわち、２つの
誤り位置がそれぞれ、ラッチ回路２へ２４の出力として
表われることになる。第３図に、Ｂ２５の信号値として
ラッチ回路２５の出力値の変化を示しである。

第２図の回路は、Ｃ１符号、Ｃ２符号共用に用いられる
もので、Ｃ１テコーダとして動作しり後、信号Ｐにより
ラッチ回路２３．２４の出力ｔラッチ回％　２Ｅ４２７
で一旦ラッチした後、さらに、Ｃ２デコーダとして動作
させる前にラッチ回ｋｔ２６．２８にテークを待避して
保持しておく。図に下すようにラッチ回に７−６２８に
は０１符号の１．ラッチ回路２６ＶＣばＣ１符号のｊ　
Ｃｊ）Ｉ）　が保持される。こ＼でＬ　Ｊは符号誤り位
置、前の説ゆ」では１＝＝４．ｊ＝１６である。次の０
２ＦＪ１号で図示の如＜Ｃ２符号の１゜Ｊ値が得られる
。

第２図の回路では、さらに誤り回数を針側する回路全附
加している。カウンタ２２は信号Ｂ２０が１１１°１に
なるたびにカウントしてゆき、出力信号Ｂ２２を比較回
路２９で°“２°゛と比較する。カウント値が°１２１
１のとき出力は°°１°“となる。信号ＰｖＣよって、
誤り位置数全ラッチ回路、２．Ｅｔ、　２７にラッチす
るとともに、ラッチ回路３０によって誤り回数全ラッチ
して出力する。

以上で、本発明の２バイト訂正の場合について説明をし
てきた。１バイト訂正の揚会Ｖこは誤９位置多項式はσ
（χ）＝χ＋σ、（但しＣ１は２バイト訂正の場合と異
なる）となり第２図の回路で、シフトレジスタ＋２．Ｒ
ＯＭ１３で構成するシフト回路か不要になる。筐た、誤
ジ位１ａ数のラッチ２４２４なども１つに省略できる。

発明の効果 以上、説明したようＶこ、本発明では、誤り位置多項式
σ（χンの変数χにα」をｊ＝ｏ　よシ昇順にあるいは
ｊ−４１−１（Ｍは符号ブロック長）より降順に投入す
ることが、シフトレジスタとＲＯＭメモリによる乗算を
利用して、簡単でしかも高速になすことができる。また
、Ｃｊのｊの進行はシフトレジスタのクロックによるも
のであるから、このクロック数ケカウントするカウンタ
を別に設けておいて、σ（χ）−〇の検出パルスにより
、仁のカウンタのカウント値ゲラツチするようにすれば
、容易Ｋ　６１　Ｄ位１Ｍｊ＝ｎ１．　Ｂ２　ｆ知るこ
とができる。

４　図面の＋＋０単な、況明 図面は本＠明の実施例全示し、第１図は誤り位置多項式
σ（χ）の回路構成の原８！説明図、２３１’！　２図
は全回路の具体的回船ブロック図、第６図は第２図の回
路のタイムチャートである。

１．２．３　・・・シフトレジスタ、４・・・合成回路
、ｉｌ、１４　・・・マルチブレフサ、　１２，１５．
１７・・・シフトレジスタ、１５．１６・・・１４０Ｍ
メモリ、　１ａ１９・・・合成回路−２０・・・零判定
回路、２１．２２・・・カウンタ、２３〜２８．３０　
・・・ラッチ回路、２９・・・比較回路、１９ａ・・・
σ（χ）。

特許請求人　日本電気ホームエレクトロニクス株式会社
代理人　弁」」士　佐藤秋比古

Claims (1)

1. 【特許請求の範囲】 （１）２シンボル誤り訂正能力をもつリードンロモン符
   号の復号において、誤シ位置多項式χ２＋σ□χ＋σ２
   の変数χとして、原始多項式の根αのべき乗αｊ（ｊ：
   整数）を」の昇順に順次に投入し、前記誤シ位置多項式
   が零になることを検知して、誤シ位置を決定する方式で
   あって、 共通のクロックにより駆動される３つのシフトレジスタ
   を有し、第１のシフトレジスタはα０（＝１）ｅプリセ
   ットした後、その出力をα２倍する定数を亜するＲ　Ｏ
   Ｒｉメモリを介して入力側に帰還するシフト回路を、第
   ２のシフトレジスタは。をプリセットした後、その出力
   をα倍する定数を有するＲＯＭメモリを介して入力側に
   帰還するシフト回路を、および第３のシフトレジスタは
   入力が常にσ、であるシフト回路を、それぞれ構成し、
   前記６つのシフト回路の出力を合成して、合成出力が零
   になるときに出力する零判定回路に導き、該零判定回路
   の出力パルスによって、前記シフトレジスタの共通のク
   ロックと同位相のクロックをカウントするカウンタの数
   値をラッチすることで誤シ位置を決定することを特徴と
   するリードンロモン符号・復号方式の誤り位置決定回路
   、 （２）第１項記載の零判定回路の出力パルスをカウント
   して誤り回数をめるカウンタを附加した特許請求の範囲
   の第１項記載のリードンロモン符号・復号方式の誤り位
   置決足回路。 （８）２シンボル誤シ訂正能力をもち、Ｍ個のシンボル
   からなるリードンロモン符号の復号において、誤シ位置
   多項式χ２＋σ、χ＋σ２の変数χとして原始多項式の
   根αのべき乗αｊ（ｊ：整数）をｊの降順にα　よシ順
   次に投入し、前記誤シ位置多項式が零になることを検知
   して、誤シ位置を決定する方式であって、共通のクロッ
   クによ逆駆動される６つのシフトレジスタを有し、第１
   のシフトレジスタはα＝（Ｍ−１）をプリセットした後
   、その出力をα−２倍する定数を有するＭＯＭメモリを
   介して入力側に帰還するシフト回路を、第２のシフトレ
   ジスタはσαＭ−１をプリセットした後、その出力をα
   −１倍する定数を有するＲＯＭメモリを介して入力側に
   帰還するシフト回路を。 および第３のシフトレジスタは入力が常にσ。 であるシフト回路を、それぞれ楊成し、前記３つのシフ
   ト回路の出力を合成して、合成出力が零になるときに出
   力する零判定回路に導き、該零判定回路の出力パルスに
   よって、前記シフトレジスタの共通のクロックと同位相
   のクロックをカウントするカウンタの数値をラッチする
   ことで誤シ位置を決定することを特徴とするリードンロ
   モン符号φ復号方式の誤シ位置決定回路。 （４）　第３項記載の零判定回路の出力パルスをカウン
   トして誤シ回数をめるカウンタを附加した特許請求の範
   囲の第６項記載のリードソロモン符号・復号方式の誤シ
   位置決定回路。