JPS58127445A - 誤り訂正方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は誤り訂正方式に係り、Ｎ個のテーブルより得た
部分シンドロームよりブロック毎のシンドロームを涼め
ることによりテーブルとして使用されるメモリ容量が少
なく、シンドローム作成のための処理時間が短かい誤り
訂正方式を提供することを目的とする。

従来より、伝送される情報がハミング符号等の誤り訂正
可能なものであるとき、伝送さゎた情報の各ブロック毎
に必要なビットを抽、出して演算を行ない、これｔこよ
り誤りビット栓口用のシンドロームを生成すると多大の
処理時間を要する。また、このシンドロームの生成をハ
ードロジックヲ用いて行なうと処理時間は非常に短いが
その回路が複雑かつ膨大なものとなる。このため、従来
より１ブロツクの各ビットがとりつる全ての場合につい
てシンドロームを生成してテーブルを作り、このテーブ
ルを索表（テーブル・ルックアップ）して処理時間を短
縮する方式がある。

第１図は１ブロツク１６ビツトのハミング符号の１例の
構成を示す。同図中、ＭＳＢをビットｂ１８１Ｌ８Ｂを
ビットｂ１とするとビットｂ１〜ｂ１１がデータビット
であり、ビットｂ１２〜ｂ工、がチェックビット、ビッ
トｂＩｌｌがパリティビットである。このハミング符号
のシンドロームＳ、〜Ｓ６は次式１こよす作成される。

ｓ、　＝ｂ１ｏｂ３ｏ＋ｂ、ｏ＋ｂ７■ｂ８０＋ｂ１ｏ
Ｏ＋ｂ１１ｅ）ｂ１２・−・・・＋１）８２＝ｂ、（ｉ
）ｂ２ｅｂ、ｅ）ｂ、Ｏ＋ｂ、（ｉ）ｂ、（Ｅ）ｂｌ、
■ｂ、３・・・・−（２）ｓ３＝ｂ、■ｂ２Φｂ３■ｂ
４■ｂ８Φｂ、■ｂＸｏ■ｂ、４−・・・・（３１ｓ、
＝ｂ１ｏ＋ｂ、■ｂ、ｏ＋　ｂ４Φｂ５Φｂ、ｏ＋　ｂ
、Φｂ１．　　　　−・−＋４１ｓ、　＝　ｂ、ｏｒｂ
、ｏ、＠）４ｏ、ｗ、ｅｂ、ｏ、ｔｂ、ｏ、。ｅｌ、ｓ
ｌ、ｏ、３ｏ、４ｏ、、ｓ１６・・・・・・　（５） ここで■はモジュロ−２の加算を示す。

上記従来の方式では（１）〜（５）式を用いて１ブロツ
クの各ビットｂ１〜ｂ１１８がとりつる全ての場合につ
いてシンドローム８１〜Ｓ５を生成してメモリ内に第２
図に示す如きテーブルを作る。このテーブルのビットｂ
□〜ｂ１６に対応した部分Ｉはメモリのアドレスであり
、部分■にはビットｂ、〜ｂ１＋８より生成されたシン
ドロームＳ□〜Ｓ、が記憶されている。

ここで部分ｎ内の「−」は使用されないビットである。

ここで、伝送された情報の夫々のブロックは各ブロック
を構成するビットｂ１〜ｂ１□をアドレスとして第２図
示のテーブルを索表して夫々のブロックに対応したシン
ドローム８１〜Ｓ、を読み出し、このシンドロームＳよ
〜Ｓｌｌによりブロックを構成するビットｂ１〜ｂ１６
中の多重誤り、１ビット誤りを検出し、誤りビットがビ
ットｂ１〜ｂ１６中のどのビットか分る場合（１ビット
誤りでは誤りビットがどのビットであるか全て分る）は
ブロック中の誤りビットを補正した後伝送された情報を
出力する。この従来の方式ではシンドローム８１〜Ｓ、
を求めるための時間が大幅に短縮され高速の誤り訂正が
可能であるが、ピッ）ｂ□〜ｂ１．（７）１６ビツト全
ての値に対応したテーブルが必要であり、このテーブル
として６４にバイト（６４に＝２”　）のメモリ容量を
専有することになる。このため、この誤り訂正方式をた
とえば文字放送を受信する一般のテレビジョン受傷機に
用いる場合、６４にバイトという大容量を誤り訂正のた
めに専有することは無理であるという欠点があった。

本発明は上記の欠点を除去したものであり、第３図以下
と共にその１実施例につき説明する。

第３図は本発明になる誤り訂正方式の１実施例のブロッ
ク系統図を示す。同図中、ｌは伝送された情報が入来す
る入力端子であり、入来した情報はシフトレジスタ２及
び同期検出器３に供給される。シフトレジスタ２は１６
ビツト構成であり、入力端子１よりの情報をクロック発
生器４より供給されるクロックパルスによりシフトさせ
、その１６ビツト夫々の記憶内容を１６ｅツト構成のラ
ッチ回路５の対ろするビットに常時供給している。

また、同期検出器　３は入力端子１よりの情報を構成す
るブロックの同期を検出してこれをカウンタ６のリセッ
ト端子に供給する。カウンタ６はリセットされた後クロ
ック発生器４よりのクロックパルスを計数し、このクロ
ックパルスを１／１６分周して得たパルスをラッチ回路
５に供給する。ラッチ回路５はカウンタ６よりパルスが
供給される毎にシフトレジスタ２より供給される１ブロ
ツクのビットｂ１〜ｂ１６を記憶して保持する。また、
ラッチ回路５は上位８ビツト（ビットｂ、〜ｂ工、）。

下位８ビツト（ビットｂ１〜ｂ８）に分割されており、
この上位８ビツト、下位８ビツト夫々によりメモリ７に
作成されたテーブル８．９が索表される。

ここで、（１）〜（５）式は以下に示す如く分割される
。

５１ａ＝ｂ１ｏΦｂｏ■ｂ、、　　　−＝−（ｌａ）ｓ
２ａ＝　ｂ、■ｂ１１■ｂ１３・・・・・（２ａ）ｓ３
ａ＝ｂ、ｅｂ□。■ｂｔ４＝＝・・（３ａ）Ｓ＜ａ＝　
ｂｓｓ　　　　　　　・−・（４ａ）ｓ、　＝　ｂ、ｅ
ｂ□。■ｂ１□ｅｂ１□■ｂ１８■ｂ１４■ｂｘｓ■ｂ
、６．、、、、、　　（５ａ）Ｓ□１．　：　ｂ　１■
ｂ３０ｂ、■ｂ７Φｂ８　　・・・・　（１ｂ）ｓ２．
　＝　ｂ□Φｂ２■ｂ５０ｂ６■ｂ８　　・・・・　（
２ｂ）Ｓ３ｂ＝ｂ１■ｂ２Φｂ、■ｂ４Φｂ８　　・・
・・　（３ｂ）ｓ　　＝ｂ■ｂ■ｂΦｂ　ｏｒｂ　Ｏｂ
■ｂ　・・・　（４ｂ）４ｂ　　　　１　　２　　３　
　４　　６　　６　　７Ｓｓｂ　＝　ｂｌｅｂ２ｅｂ３
Φｂ４Φｂ、ｏｒｂ、■ｂ、ｏ＋ｂ、　　・−・（５ｂ
）Ｓｎ＝Ｓｎａ■８．ｂ（ｎは１，２，３，４．５）−
−−（６）（６）式で示す如く、上位８ビツトによる部
分シンドロームと下位８ビツトによる部分シンドローム
により全体（ビットｂ０〜ｂ１６）のシンドロームが求
められる。

テーブル８は第４図（５）に示す如く上位８ビツト（ビ
ットｂ、〜ｂ１．）をアドレスとして、このビットｂ、
〜ｂ１６より（１ａ）〜（５ａ）式を用いて生成された
部分シンドローム５１ａ−８ＩＩａが記憶されている。

またテーブル９は第４図０３）に示す如く下位８ビツト
（ビットｂ１〜ｂ８）をアドレスとして、このビットｂ
１〜ｂ８より（ｔｂ）〜（５ｂ）式を用いて生成された
部分シンドロームＳ１．〜・Ｓ５．が記憶されている。

テーブル８は、たとえばラッチ回路５にビットｂ１６よ
り１１Ｃにビットｂ１までｒｏｌｏｌｌｏｏｌ　０１１
１１００１Ｊが記憶されているとき、上位８ピツ）　ｒ
ｏｌｏｌｌｏｏｌＪをアドレスとして索表されて得られ
る部分シンドローム［−−−０１１０１Ｊを排他的論理
和回路１０の一方の入力端子に供給し、テーブル９は同
様にして下位８ビツトｒ０１１１１００１Ｊをアドレス
として索表さねて得られる部分シンドロームｒ−−−１
１０１１Ｊを排他的論理和回路１０の他方の入力端子に
供給する。排他的論理和回路１０は部分シンドロームＳ
１ａ　−Ｓｓａ　、５ｔｔ）　〜Ｓａｂの夫々で（６）
式の演算を行ないシンドロームＳＸ〜８．を得る。上記
の例では不使用の３ビツトを含めてシンドロームＳ、よ
り順に８１才でｒ−−−１０１１０Ｊが得られ、この得
られたシンドローム［−−−ｘｏｌｌｏＪは判定回路１
１に供給さね、ここで誤りビット（この場合ビットｂ、
）だけ「１」とされた補正用ビット列（この場合ＭＳＢ
より順にＬＳＢまでｒｏｏｏｏ　０００１００００００
００Ｊ　）が発生されて補正回路１２に供給される。補
正回路１２はこの補正用ビット列とシフトレジスタ５よ
り供給される１ブロツクのビットｂ１〜ｂＩＩＩとの夫
々対応するビットの排他的論理和を演算して補正を行な
った後（この場合補正された情報はＭＳＢより順にＬＳ
Ｂまでｒｏｌｏｌ　１００００１１１１００１Ｊである
）出力端子１３より出力する。

このようにテーブル８．９は夫々２５６バイト（２５６
＝２’）で両者で使用するメモリ７の各賞は５１２バイ
トであり、従来の６４にバイトの１／１２８のメモリ容
量を要するだけである。

なお、上記と同様にしてテーブルを４分割してビットｂ
　〜ｂ　　、ｂ　　〜ｂｂ　　〜ｂ　　、ｂ　　〜ｔａ
　　　　　　ｔｍ　　　　　　ｔｔ　　　　　　・　１
　　８　　　　５　　　　４ｂ１夫々の部分シンドロー
ムを作成し、４棟類の部分シンドロームの排他的論理和
を求めるようすれば、メモリ容量は６４バイト（６４＝
２’＋　２’＋　２４＋２４）で良い。しかしシンドロ
ーム８１〜Ｓｇ　ヲ求メるまでの時間が長くなるため、
要望される処理スピード及び許容されるメモリ容１に応
じてテーブルの分割数は決められ、上記実施例の如くテ
ーブル８．９の２分割に限定されない。

なお、シフトレジスタ２．ラッチ回路５を８ビツト構成
とし、カウンタ６を８進としてまず下位８ビツトでテー
ブル９を索表した後、続いて供給さオフる上位８ビツト
によりテーブル゛８を索表するよう時分割しても良く上
記実施例に限定されない。

上述の如く、本発明になる誤り訂正方式は、誤り訂正可
能な形式でブロック毎に符号化された情報を伝送され、
情報をブロック毎に誤り訂正を行なう誤り訂正方式にお
いて、ブロックをＮ（Ｎは正の整数）個の部分に分割し
て夫々の部分を構成するビット列がアドレスでビット列
により生成される部分シンドロームを記憶したＮ個のチ
ーフルを有し、Ｎ個のテーブルより得られるＮ個の部分
シンドロームよりブロック毎のシンドロームを求めて情
報の誤り訂正を行なうため、テーブルとして使用される
メモリ容量が少なく、複雑な論理演算を必要とせず低レ
ベルのマイクロコンピュータ等でも充分処理でき、その
処理時間も短かく、更に符号化におけるビット配列の変
更、検査行列の変更薯こ対してもテーブルの記憶内容を
変更するだけで容易に対応できる等の特長を有するもの
である。

【図面の簡単な説明】

第１図は情報の１ブロツクを模式的に示す図、＠２図は
従来のテーブル構成の１例を模式的に示す図、第３図は
本発明方式の１実施例のブロック系統図、第４図（５）
、（Ｂ）は第３図示のテーブル構成を模式的に示す図で
ある。 １・・・入力端子、２・・・シフトレジスタ、４・拳・
クロック発生器、５・・・ラッチ回路、７・・働メモリ
、８，９・・・テーブル、１０・・・排他的論理和回路
、１１・・拳判定回路、１２・・・補正回路、１３拳・
・出力端子。

Claims (1)

【特許請求の範囲】
1. 誤り訂正可能な形式でブロック毎に符号化された情報を
   伝送され、該情報を該ブロック毎に誤り訂正を行なう誤
   り訂正方式において、該ブロックをＮ（Ｎは正の隻数）
   個の部分に分割して夫々の部分を構成するビット列がア
   ドレスで該ビット列により生成される部分シンドローム
   を記憶したＮ個のテーブルを有し、該Ｎ個のテーブルよ
   り得られるＮ個の部分シンドロームより該ブロック毎の
   シンドロームを求めて該情報の誤り訂正を行なうことを
   峙徴とする誤り訂正方式。