JPS6319922A - Ｂｃｈ符号の復号方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （イ）　産業上の利用分野 本発明はディジタルデータの伝送・蓄積等に用いられる
ＢＯＨ符号の符号化或は復号方式ｌこ関するものである
。

（ロ）　従来の技術 一般にディジタルデータを伝送する場合、伝送系のＳＮ
比の劣化・歪等に起因して発生するビット誤りに対処す
るために、誤り訂正能力を持つ穴長ビット（以下、誤り
訂正用ビットと称す）を元の情報ビットに付加して送信
し、受信側でこの訂正用ビ・ソトを基に誤り位置を検出
して誤り訂正を行う方法がよく用いられている。この訂
正符号の中でもＢＣ）（符号（Ｂｏｓｅ　−Ｃｈａｕｉ
ｈｕｒｉ　−ＨＯ（！ｑｕｅｎｇｈｅｍ　）は、訂正用
ビーＪトの長さくビーＪト数）に対する誤り訂正能力が
高い利点があり、衛星放送のＰＣＭ音声伝送、国内や米
国の自動車電話、コードレス電話、ポケットベル等Ｉこ
おける信号伝送などｌこ広く用いられている。

このＢＣＨ符号を用いて誤りを訂正する復号方法として
は、受信信号列Ｖ囚を生成多項式Ｇｔ力で割り、その剰
余項（これをシンドロームと呼ぶ）を求め、このシンド
ロームを基に誤りの有無の判定、誤り位置の算出を行い
、誤り位置に対応するビットの値を反転して訂正すると
いう手順がとられる。

従来、このシンドロームを求める方法としては例えば昭
晃堂より昭和５１年７月２０日に発行された「符号理論
」第１１６頁〜第１１７頁に記載されているように、生
成多項式Ｇ囚に対応させた帰還型のシフトレジスタを用
い、このシフトレジスタ（７）Ｌ　Ｓ　Ｂ　（Ｌｅａｓ
ｔ　５１ｇｎ１ｆｉｃａｎｔ　Ｂｉ、ｔ　　）　ｊＣ対
応するシフトレジスタへ受信信号Ｖ　（ＸＪ　ヲＭ　Ｓ
　Ｅ（Ｍｏ５ｔ　ＳｉｇｒｎｆＪＬｃａｎｔ　８１℃）
側から１ビツトずつ順次入力させる方法が用いられてい
る。

第５図１ｉ従来のシンドローム算出回路を示す図で、米
国のＡ　Ｍ　Ｐ　Ｓ　（Ａｄｖａｎｃｅｄ　Ｍｏｂｉ工
ｅ　ＰｈＯｒｌｅｓｙｓｔｅｍ　）仕様の自動車電話に
用いられているＢＣＨ符号を復号する際に用いられるシ
ンドローム算出回路を示しているうこの自動車電話に用
いられているＢＯＨ符号の場合、生成多項式Ｇ（ｘＪは
ＧｔＸｌ＝Ｘ　＋Ｘ　＋Ｘ　＋Ｘ　＋Ｘ　＋Ｘ　＋１　
（即チ、訂正用ビット長βが１２ビツト）であり、また
情報のビット長Ｋ　１ｉ３６ビツトであるから、受信信
！ｎはｎ＝に＋１＝４Ｊ３ビツトとなる。斯るＢＣＨ符
号はＢＣＨ（４８，３６）と表記される。

また、生成多項式Ｇ（Ｘｌの次数が丘であるため、シン
ドローム算出回路としては１２個の１ビツトシフトレジ
スタ（Ａｌ）〜（Ａ＋ｔ　）　　にて構成されたνビッ
トシフトレジスタが用いられる。尚、図中記号■Ｇｔ　
Ｍ　ＯＤ　２の加算回路を示している。

次に、斯る回路によるシンドロームの算出手順ｊこつい
て説明する。

先ス、初期セットとしてシフトレジスタ（Ａｌ）〜（Ａ
＋□）をリセ＋７　トし、その値を全て０にする。

然る後、１クロヅク毎に受信信号列Ｖ（ＸｌのＭＳＢか
ら順次シフトレジスタ（Ａ１）に、シフトレジスタ（Ａ
ｎ　）の値とＭＯＤ２で加算された後入力される。そし
て、受信信号列Ｖ囚のＬＳＢの信号がＬＳＢに対応する
シフトレジスタへ入力された時点における各シフトレジ
スタ（Ａ１）〜（ＡＸｔ）の値が求めるシンドローム値
となる。

このような従来のシンドローム算出回路の場合受信信号
をＭＳＢ側から１ビツトずつシフトレジスタに入力させ
るので、受信信号Ｖ囚のビット長ｎに相当する手順を要
し、ビット長ｎが多い場合演算に多大の時間を費し、高
速演算には不利である。

［／’ｌ　　発明が解決しようとする問題点本発明は、
このＢＣＨ符号における剰余の算出手順を改良し、算出
時間を短縮することにより高速演算に適応できるＢＣＨ
ｒｆ号の符号化或は復号方式を提供せんとするものであ
る。

に）問題点を解決するための手段 上２目的を達成する本発明の特徴は、ＢＣＨ符号の符号
化回路或は復号回路において、ｎビット長の信号列から
剰余を求める方式であって、前記ｎビット信号列を生成
多項式ＧｆＸｌの次＆Ｎに対して２ｍ≧２≧ｍなる条件
を満足するｍビット長の（Ｎ＋２）Ｍのブロック（Ｎ　
−＝　：小故点は切り上げ）ｌこ分割する第１の過程と
、ＭＳＢ側のｍビット長の第１情報ブロックＢｓ（ｘ）
ｌこ対してｅぶ ビットＯを付加した情報ＣＢＩＩＸＩ−Ｘ、　　’ｌ　
　を生成多項式Ｇ囚で割った剰余項ＥＢ、（Ｘｉを求め
る第２の過程と、該剰余項ＥＢ＋ｔＸ）の上位ｍビット
と次の情報ブロックとを加算することによりｍビットの
加算値Ｆｚ（Ｘｌを求める第３の過程と、該加算値Ｆｘ
ＣＡに対してβピッ）Ｏを付加した情報ＣＦｚｌ”ｆＪ
文 ・Ｘ　〕を生成多項式Ｇ囚で割った剰余項ＥＦ’、（Ｘ
）を求める第４の過程と、該剰余項ＥＦｇ囚の上位ｍビ
ットと前記剰余項Ｅ　Ｂ、　（Ｘｉの下位１’−ｍ）ビ
ット及び情報ブロックＢｓＣＫＪとを加算することによ
りｍビットの加算値Ｆ３（Ｘｌを求める第５の過程と、
第４及び第５の過程と同様の過程を（Ｎ−１）回反復し
て得られたＴ）Ｄ’ＫｖＩＦ　Ｎ　＋　１　（ｘ）及ヒ
Ｆ　Ｎ　＋２囚の内容から＠ｅｎビット信号列の剰余を
求める第６の過程とよりなるＢＣＥＩ符号の符号化或は
復号方式にある。

（ポ作　用 本発明によると、信号列を生成多項式にて直接側ること
により剰余を求めずに、信号列を生成多項式の次ｋｌに
対して２ｍ≧ｌ≧ｍなる条件を満たすｍビットの複数の
ブロックに分割し、先ず分割されたブロックの内ＭＳＢ
側の第１ブロヴクにｇビットｏを付加した情報を生成多
項式にて割り剰余項を求め、次にこの剰余項の上位ｍビ
ットと次のブロックとをｍｓし、この加算された情報に
前述と同様に２ビツト○を付加した後、生成多項式で割
って、剰余項を求める。更に、この剰余項の上位ｍビッ
トと先の剰余項の下位（β−型）ビット及び次の９報ブ
ロックを加算する。

斯る動作をｍ＆回反復することにより得られた加算値情
報の内容から前記信号列の剰余を求める。

（へ）実施例 本発明で（ま先ずｎビ・ソトの信号列の内、（ｎ−りビ
ット長の情報ビットを２ｍ≧ｅ≧ｍなる条ｎ−（１ 件を満たすｍビット長の８個（Ｎ　＝−）のプロツクに
分割する（第１図参照）。このとき、−ｇ □が整数とならなければ、ブロック数Ｎを足して８個の
プローＪりを構成する。また、訂正用ビットはｍビット
長の上位ブロックとｌ？−ｍ）ビット長の下位ブロック
で構成される。尚、下位ブロックではＬＳＢ側に○を補
足してｍビット長きする。

そして、斯るブロック単位で処理を行うのであるが、そ
の際ｍビット情報Ｂ（Ｘｌをアドレスとして、この情報
ＢｔＸｌに２ビツトＯを付加したｍ＋ｚピッ氾 ト情報（ＢＯＱ・Ｘ　〕を生成多項式０［Ｘ）で割った
ときの２ビツト長の剰余項ＨＢ囚が格納されたＲＯＭテ
ーブルを用いる。

斯るＲＯＭテーブルへのデータ格納方法ｔこついて第２
図を参照して説明する。

前述したように生成多項式の次数がｌのとき、この生成
多項式にてｎビットの信号列を割ったときの剰余項は！
ビットとなる。本発明は斯るｅビットの剰余項を上位の
ｍビットと下位の４？−ｍビットに分けてＲＯＭテーブ
ルに格納する。

即ち、情報ビットＢ（ｘｌのＬＳＢ側にＯを付加したビ
ット列をアドレスとし、これに対応するデータとしては
剰余項ＦＪＢ囚の上位ｍビット、ＥＢ（ＸｉＨが格納さ
れる。また、情報ビットＢ（Ｘ）のＬＳＢ側に１を付加
したビット列をアドレスとし、これに対応するデータと
しては剰余項ＥＥＥ（Ｘ）の下位！−ｍビプト、ＥＥＢ
（ＸＪＬが格納される。尚、このＥＢ（ｘ）Ｌについて
は、第２図に示すように剰余項ＥＢｔＸｌの下位ｉ−ｍ
）ビット列のＴ、、ＳＢ側に史に（２ｍ−１ビプト０を
付加し、ｍビットのデータとする。

次に、本発明における剰余の算出手順の原理について第
３図を参照して説明する。尚、第３図において、８個に
分割された各情報ブロックの内容をＢ、　ｆＸｌ　−Ｂ
　Ｎ　（ＸＪ、また２分割された訂正用ビットの各プロ
、ツクの内容を山■、Ｈ２囚と表記する。

先ず、Ｍ　Ｓ　Ｂ側の第１ブロックＢ＋ＧＯに対してＲ
ＯＭテーブルを参照して剰余項ＥＢ、（Ｘｉを求める。

次に、斯る剰余項の上位ｍビットＥＢ４［ＸＩＨの内容
と情報ビットの■２ブロックＢ２（ｘ）のｍビットの内
容とを＋Ａ　ＯＤ　２で加算を行うことにより加算値Ｆ
、ＣＯを求める。

きころで、斯る加算値Ｆ２（ｘ）は情報ビットの第１プ
Ｏ−ｔ　Ｉ　Ｂ＋　（ＸｌからｆＪｓ５プロｑ　りＢｓ
　（Ｘｌテｔｌｂ３サレる３ｍビット列信号に対し、こ
れを生成多項式ＧｔＸｌで割算処理を行う過程で得られ
る値であり、また第３ブロックＢ３（Ｘｌの内容と前記
剰余項ＥＢ、囚の下位（ｇ−ｍ）ビーＪ　トＦＥ　Ｂ　
＋　（Ｘｉ　Ｌ　トラＭ　ＯＤ　２　テ加算した加算値
をＢ’３　ｔＸＩと表記する。尚、！１８３図Ｃａｌ　
ｉこ示す信号列に対する剰余項は第３図ｆｔ）Ｉに示す
信号列（こ対する剰余項とは等しい。

次に、上記加算値ＦｔＯ’Ｊに対する剰余項ＦＦ、（Ｘ
）をＲＯＭテーブルを参照して求め、これの上位ｍビッ
トＥＦｔ（ｘ）ＨとＢ′３（力ＨとＢＦ２囚とを加算し
てＦ２（ｘ）を求める。また、剰余項ＥＦ、（ＸＪの下
位ＥＦ、囚の下位’Ｆ２Ｆ２（ｘ）りと第４ブロックＢ
４閃との加算値をＢ’ａ　（Ｘｉと表記すると、第３図
（ＣＩに対する剰余値は、前述と同様に第３図（旬に示
す符号列に対する剰余値と等しくなる。

このような手順を繰り返すと、（１−１）番目の手順で
は、 Ｆｉ（ｘ）　−Ｂ１０ＩＪｅＦ、Ｆ’ｈ−ｓ　＋）Ｑ）
［）　ＥＦｉ−２ＭＬが得られ、Ｎ−１８目の手順でＦ
Ｎ（ＸＪが得られる。

尚、１ｉ！、号ΦハＭ　ＯＤ　２　）加算ヲ示す。Ｂ’
Ｎ＋１（ｘ）−）ｌ　を囚ΦＥＦＮ−１囚りと表記する
と、元の符号列に対する剰余値は第３図１（１１の符号
列の剰余値と等しい。

次に、ＦＮ囚に対する剰余項１：ＦＮＩＸｌを求め、Ｃ
０ｃ７Ｊ上位Ｅ　Ｆ　Ｎ　（ＫｌトＢ’Ｎ　＋　１　（
ｘ）、及ヒＥＦＮ（ｘ）と！１２囚との加算値を各々求
め、これを各々Ｆ　！Ｊ　＋１（冷、Ｆ’Ｎ＋２（ｘ）
と表記すると、この２ブロックから得られる内容が、元
の符号列に対する剰余値となる。

第４図は本発明を達成する回路の一実施例を示す図であ
る。尚、ＢＣＩ（符号として、従来と同様にＢＣ）ｌ（
４Ｂ、３６）を用いて説明する。従って、各ブロックは
８ビ９トにて構成されており、符号１ｎ＝４１ｔ：’ッ
ト、訂正ヒツト長！−νビヅトである為、情報ビーメト
は、Ｎ−５ブロックで構成され第１ブロックのＭＳＢ側
４ビットに０が補足、又訂正ピリドの下位ブロック（第
７ブロック）ではＬＳＢ側の４ビツトにＯが補足される
。第４図においてＩｌｌは分割された７ブロックの各ブ
ロックのビット列が所定のアドレスに格納されたワード
長Ｗ−８のＲＡＭである。（２）は前記８ビツト情報の
ビット内容に対し、これにＬＳＢ側に１２ビツト０を付
加した１８ビツト情報を生成多項式ＧＯＣＩで割ったと
きの剰余項データが格納されたＲ　Ｏ％Ａ子テーブルあ
り、ワード長は８ビツトのものを用し１ている。

このＲＯＭへのデータの格納方法は前記８ビツト情報の
ＬＳＢ側に０を１ビツト付加した９ビット信号列ヲアド
レスとし、これに対応する剰余項の上位８ビツトの内容
をデータとして格納し、又前１５８ビツト情報のり、Ｓ
Ｂ側に１を１ビーｌト付加した９ピリド信号列をアドレ
スとし、前記剰糸項の下位４ビ、）の内容をデータとし
て格納する。

ここで斯る４ビツトデータの格納方法は、剰余項と情報
ブロックとの加算の便宜を配慮して、該４ピツトデータ
のＬＳＢ側に０を４ビツト付加した８ビツト長のデータ
として格納しておく。

（３−１）（３−２）（３−３）はＲＯＭテーブル（２
１からの出力をラッチするラッチ回路でありラッチ回路
（３−１）は剰余項の上位ブＯ−）りの内容、ラッチ回
路（３−２）Ｇ：を下位ブロックの内容をラッチする。

又ラッチ回路（３−！５　）はラッチ回路（３−２）の
内容をラッチする。

＋４１は、ＲＡ　Ｍ　（１１から読み出されたプロ・Ｉ
り即位の情報（入力１）とラッチ回路（５−２）（入力
璽）及び（５−５）　（入力璽）の出力とをＭ　ＯＤ２
で加算する加算器である。又、＋５１はＲＡ　Ｍ　＋１
１のアドレス並びにうづ子回路（３−１）（３−２＞（
３−３）のラッチタイミングを制御するｔＩＩｍ回路で
ある。又）６１番ま加算器＋４％の内容をラッチする回
路である。次に動作について説明する。

ラッチ回路（５−１）（３−２）（３−３）が初期リセ
ットされ、制御回路（５１にてアドレス１が指定される
と、ＲＡＭ（１０ζ格納された第１プク９りの情報ＢＩ
ｔｘＪが選択され、加算器（４：の入力端子ｌに入力さ
れる。このとき、上述のようにラッチ１纂 回路（３−１）（５−２）（３−３）Ａ初期リセットさ
れているので、加算器１４１の出力はＢ１００となる。

ＲＯＭ　＋　−プル（２１（７Ｊ出力４１、情報Ｂｔ（
ｘ）　ヲｙ　ｌ／レスとする剰余項ｇＢ１０Ｃ１であり
、次に制御回路（５）の値がアドレス１からアドレス２
に歩進するタイミングで、ラッチ回路（３−１）には剰
余項の上位の内容が（３−２）には下位の内容がラッチ
されるように動作する。

このとき、ＲＡＭ１ｌ）ではアドレス２に対応する情報
Ｂ、（ｘ）　が選択され、加算器（４）の入力端子゛１
に印加される。又、入力端子層にはラッチ回路（３−１
）の内容（ＥＢ、囚Ｈ）が印加される。又、入力瑞子議
の入力は、Ｃの時点ではラッチ回路（６−３）はリセッ
トされた状態のままであり、Ｏである。従って、加算器
（４）の出力Ｆｚ囚＝Ｂ、（Ｘｔ＋ＥＢＩ囚八へなる。

次に、制御回路（５）の値がアドレス２からアドレス３
に歩進するタイミングでラッチ回路（３−１）ニハ剰余
項Ｅ　Ｆ　２（ｘｌＨｓ　ｙ　”ｔ　９回路（３−２）
に＋−！ＥＦ、（ｘ）Ｌがラッチされる。又、ラッチ回
路（３−３）にはラッチ回路（３−２）の前内容である
剰余項ＥＢ、（ｘ）Ｌがラッチされる。従って、加算器
の出力Ｆ３を力は Ｆ四＝　Ｂ、（Ｘｉ■ＩＩＥＦ２β■ＥＢ包。

となる。

以下、同様の動作を繰り返し、制御回路（５）にてアド
レス６が指定されるタイミングでは加算器の出力として
は Ｆ、（Ｘ＋＝Ｂ、囚ｅＥ　Ｆ　５ｔＸＩ　Ｈ■ＥＦ、（
ｘ）Ｌが得られる。

次に、制御回路（５）にてアドレス７が指定されるタイ
ミングで、加算器（４）の内容をラッチ回路（６１＆こ
ラッチし、又、ラッチ回路（３−１）をリセットする動
作を行う。

このとき加算器の出力は、訂正ビットの下位ブロックＢ
、囚＝Ｈ＋（ｘ）とラッチ回路（３−３）の内容ＥＦ、
囚りの加算値となる。所望の絽ビット什号に対する剰余
ｈ′！ｒ＋？Ｊ記ラヅチ回路（う）の内容を上位ビット
とし、加算器（４）の内容を下位ビットとして得られる
ビット列として求まる。

尚、符号化の場合には、訂正ビットＨ１囚及びＨ，（Ｘ
ｌ　の値を全てＯとして、上記処理を行い、斯る方法に
て得られる剰余値を訂正ピリド列として（ｎ−４’　）
の情報ビット列に付加すればよい。

（ト）　　発明の効果 本発明に依れば、ＢＣＨ符号の符号化回路（ま復号回路
において、ｎビット長の信号列から剰余を求める方式で
あって、前ｇｎビット信号列を生成多項式Ｇ（Ｘｉの次
数ｅに対して２ｍ≧ｇ≧ｍなる条件を満足するｍビット
長の（Ｎ＋２）個のプロツ第１の過程と、ＭＳＢ側のｍ
ビーＩト長の第１情報ブロックＢｓ１ＸＩ　に対してｅ
ビットＯを付加した情り 報ＣＢ＋１ＸＩＸ　　〕を生成多項式ＧｃＫＪで割った
剰余項ＥＢＩ（Ｘｌ　を求める第２の過程と、該剰余項
ＥＢ１囚の上位ｍビットと次の情報ブロックとを加算す
ることによりｍビットの加算値Ｆ２（ｘ）　を求める第
３の過程と、該加算値ｘｉ”、ｃＸＪ　に対して４ビツ
ト０Ω を付加した情報ＣＦ！（Ｘｌ・Ｘ　〕を生成多項式Ｇ（
Ｘｉで割った剰余項ＥＦ、囚を求める第４の過程と、該
剰余項ＥＦ、（Ｘｌ　の上位ｍビットと前記剰余項ＥＢ
ｓ（ＸＪ　の下位１ｉ−ｍ）ビット及び情報ブロックＢ
ｍ（ｘ）　　とを加算することによりｍビットの加算値
Ｆ３囚を求める第５の過程と、第４及び第５の過程と同
様の過程を（Ｎ−１）回反復して得られた加算値ＦＮ＋
１囚及びＦＮ＋２囚の内容から前記ｎビット信号列の剰
余を求める第６の過程とを有するので、従来の符号化或
は復号時における剰余算出と比較して演算時間を大幅に
短縮することが出来る。

【図面の簡単な説明】

第１図は信号列をＮ＋２ＩＩｌｉＩのブロックに分割す
る過程を説明するのに供する図で、同図［ａｌはｎビッ
ト信号列を示す図、同図ｔｂ１は分割後の信号列を示す
図、第２図はＲＯＭへのデータ格納方法を説明するのに
供する図、第３図は本発明の原理を示す図、第４図は本
発明の一実施例を示す図、第５図は従来例を示す図であ
る。 （１）・・・ＲＡＭ、＋２１・・・ＲＯＭ、（３−１）
（３−２）（３−３）ｆ６）・・・ラッチ回路、（４）
・・・加算器、（５）・・・制御回路。

Claims (1)

【特許請求の範囲】
1. （１）ＢＣＨ符号の符号化回路或は復号回路において、
   ｎビット長の信号列から剰余を求める方式であって、前
   記ｎビット信号列を生成多項式Ｇ（ｘ）の次数ｌに対し
   て２ｍ≧ｌ≧ｍなる条件を満足するｍビット長の（Ｎ＋
   ２）個のブロック（Ｎ＝（ｎ−ｌ）／ｍ：小数点は切り
   上げ）に分割する第１の過程と、ＭＳＢ側のｍビット長
   の第１情報ブロックＢ＿１（ｘ）に対してｌビットＯを
   付加した情報〔Ｂ＿１（ｘ）・ｘ＾ｌ〕を生成多項式Ｇ
   （ｘ）で割った剰余項ＥＢ＿１（ｘ）を求める第２の過
   程と、該剰余項ＥＢ＿１（ｘ）の上位ｍビットと次の情
   報ブロックとを加算することによりｍビットの加算値Ｆ
   ＿２（ｘ）を求める第３の過程と、該加算値Ｆ＿２（ｘ
   ）に対してｌビットＯを付加した情報〔Ｆ＿２（ｘ）・
   ｘ＾ｌ〕を生成多項式Ｇ（ｘ）で割った剰余項ＥＦ＿２
   （ｘ）を求める第４の過程と、該剰余項ＥＦ＿２（ｘ）
   の上位ｍビットと前記剰余項ＥＢ＿１（ｘ）の下位（ｌ
   −ｍ）ビット及び情報ブロックＢ＿３（ｘ）とを加算す
   ることによりｍビットの加算値Ｆ＿３（ｘ）を求める第
   ５の過程と、第４及び第５の過程と同様の過程を（Ｎ−
   １）回反復して得られた加算値ＦＮ＋１（ｘ）及びＦＮ
   ＋２（ｘ）の内容から前記ｎビット信号列の剰余を求め
   る第６の過程とよりなるＢＣＨ符号の符号化或は復号方
   式。