JPH076047A - ２ビット誤りを訂正する誤り訂正特性符号の生成方法。 - Google Patents

Abstract

(57)【要約】 【目的】電子計算機や通信システムに於けるビット処理
で発生する２ビットまでのビット誤りの訂正を高速で行
うために論理演算を主とする方法によりビット列の長さ
が大きくなるほど長さの比率が小さくなる高効率で簡易
な２ビット誤りを訂正する誤り訂正特性符号を生成する
方法。 【構成】２進法の加算、乗算、及び排他的論理和を作る
回路。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】電子計算機に於けるビット列の２
ビットまでの誤りの訂正。

【０００２】

【従来の技術】ビット列の２ビットまでの誤りを訂正す
る簡易な符号と方法がない。

【０００３】

【発明が解決しようとする課題】電子計算機に於けるビ
ット処理で発生する２ビットまでの誤りを訂正する、論
理演算を主とする、ビット列の長さが大きくなるほど長
さの比率が小さくなる高効率で簡易な符号の生成方法。

【０００４】

【課題を解決するための手段】図１に於いて、まず、ビ
ット列（１）の位置符号（２）から配列符号（３）を作
り、その配列符号からビット行列（４）を作る。そし
て、（４）の各列に対するＥＯＲにより第１列特性符号
から順次、最終列特性符号までを作る（５）。そして、
（５）から第１組特性符号（６）、第２組特性符号
（７）、最終組特性符号（８）を作り、それらを連結し
て誤り訂正特性符号（９）を作る。次に、（１）に於い
て２ビット誤りが発生したビット列（１０）の誤り訂正
特性符号（１１）を作り、（９）と（１１）から比較符
号（１２）を作る。

【０００５】

【作用】まず、誤り訂正特性符号について、 １）ビット列の長さに対するその長さの比率はビット列
の長さが大きくなるほど小さくなる。その比率を表１で
示す。 次に、比較符号を使用した２ビットまでの誤りの訂正
は、 ２）ビット列に於ける２ビットまでのビット誤りが発生
すると比較符号のどれかの桁が１で、２ビットまでのビ
ット誤りがなければすべての桁は０であることによりビ
ット誤りを検証する。 ３）そして、比較符号に於ける第１組特性符号から最終
組特性符号の各々に相当する部分でその最高位の桁が１
のものはビット誤りの発生したビット列の２個、又は１
個のビット位置を表す位置符号になり、その位置符号の
示すビット位置のビット符号を補の２進数にすれば２
個、又は１個のビット誤りを訂正できる。 ４）次に、再度、上記３）によってビット誤りを訂正し
たビット列から誤り訂正特性符号を作る。そして、上記
２）、３）を行うことによって、残り１ビットの誤りが
あれば、そのビット誤りを検証し訂正する。

【０００６】

【実施例】図２で、ビット列（１）に於いて、２ビット
誤りが発生してビット列（１０）になった場合の２ビッ
ト誤りの訂正を示す。まず、（１）の誤り訂正特性符号
（９）と（１０）の誤り訂正特性符号（１１）から比較
符号（１２）を作る。次に、その（１２）の第１組特性
符号、及び最終組特性符号に相当する部分の（１３）、
（１４）がビット誤りのビット位置を表す位置符号にな
るから、それらの示す（１０）のビット位置のビット符
号をそれぞれの補の２進数にすれば（１）に訂正され
る。

【０００７】

【発明の効果】電子計算機に於けるビット処理で２ビッ
トまでの誤りの訂正を論理演算を主とする回路構成によ
りビット列の長さが大きくなるほどその長さの比率が小
さくなる高効率で簡易な符号により行うことができる。

【図面の簡単な説明】

【図１】本方法の構成を示すブロック図で、上部が構成
の各要素を示すブロック図で、その下部が１６ビットの
ビット列の例でその各要素を示したブロック図である。

【図２】１６ビットのビット列で２ビット誤りの訂正の
方法を示すブロック図である。

【符号の説明】

（１）はビット列 （２）は位置符号 （３）は配列符号 （４）はビット行列 （５）は列特性符号 （６）は第１組特性符号 （７）は第２組特性符号 （８）は最終組特性符号 （９）は誤り訂正特性符号 （１０）はビット列 （１１）は誤り訂正特性符号 （１２）は比較符号 （１３）は位置符号 （１４）は位置符号

Claims (1)

【特許請求の範囲】
1. 【請求項１】 １）まず、長さが２のｎ乗のビット列に対してそのビッ
   ト位置に一定の方向に順序を定め、起点から順次、各々
   のビット位置に対応する同一桁数で最高位の桁が１で、
   あとの桁は２進法ですべて０の２進数で、ｎ＝３ならば
   １０００のように表示する桁数が（ｎ＋１）桁の２進数
   からビット位置の順序で順次、２進法で１を加算して１
   ００１、１０１０のように表示する同一桁数の（ｎ＋
   １）桁の２進数を作る（位置符号と呼ぶ）。そして、そ
   の位置符号にそのビット位置のビット符号の０、又は１
   を２進法の乗算によって００００、１０１０のように表
   示する、位置符号と同一桁数の（ｎ＋１）桁の２進数を
   作る（配列符号と呼ぶ）。 ２）次に、配列符号を位置符号の順序で桁の位取りを同
   順にして順次、縦に並べて行列にしたものを作る（ビッ
   ト行列と呼ぶ）。 ３）そして、まず、ビット行列の縦の各々の列の２進数
   を各々のビット列としそのビット列に対して上記１）に
   よって位置符号と配列符号を作り、その位置符号の桁の
   位取りと同順にしてすべての配列符号の排他的論理和
   （ＥＯＲ）の（ｎ＋１）桁の２進数を作る（列特性符号
   と呼ぶ）。そして、ビット行列の各々の列に対応する列
   特性符号を最高位の列から順次、下位の列の列特性符号
   を、第１列特性符号、第２列特性符号、第３列特性符号
   と呼び、最終列の列特性符号を最終列特性符号と呼ぶ。 ４）そして、各々の列特性符号の（ｎ＋１）桁の位取り
   を同順にして、第１列特性符号から最終列特性符号まで
   の列特性符号を順次、２個づつの列特性符号の組で分割
   する。そのとき、もし列特性符号の個数が奇数のときは
   最終の組として最終列特性符号と（ｎ＋１）桁がすべて
   ０の符号とにする。そして、その各々の組の２個の列特
   性符号のＥＯＲを作る（組特性符号と呼ぶ）。 ５）このようにして、第１列特性符号と第２列特性符号
   とのＥＯＲ（第１組特性符号と呼ぶ）、第３列特性符号
   と第４列特性符号とのＥＯＲ（第２組特性符号と呼ぶ）
   のように順次、最終の組まで、組特性符号を作る。そし
   て、その第１組特性符号、第２組特性符号、そして順
   次、最終組特性符号までのすべての組特性符号を横に連
   結した符号を作り、誤り訂正特性符号と呼ぶ。 ６）そして、ビット列に於いて２ビットまでの誤りが発
   生する前と発生した後の誤り訂正特性符号を桁の位取り
   を同順にしてＥＯＲを作り（比較符号と呼ぶ）、その比
   較符号を使用して２ビットまでのビット誤りを訂正す
   る。 上記を特徴とする誤り訂正特性符号の生成方法。