米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 株式会社日立製作所

発明の名称 エラー訂正システム
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平6−12272
公開日 平成6年(1994)1月21日
出願番号 特願平4−167257
出願日 平成4年(1992)6月25日
代理人 【弁理士】
【氏名又は名称】小川 勝男
発明者 山形 学
要約 目的
エラーフラグの付与に関係なく、正しくエラー訂正を実行することが可能なエラー訂正システムを提供する。

構成
データとともに与えられる外部エラーフラグ11を保持する外部エラーフラグ保持回路2,シンドローム値14に基づいて内部エラーフラグ17を生成するシンドローム処理器4および内部エラーフラグ発生回路5,外部エラーフラグ11を計数し、その個数12の大小に応じて、シンドローム処理器4および内部エラーフラグ発生回路5の動作を制御する外部エラーフラグ計数回路3,外部エラーフラグ11(15)と、内部エラーフラグ17を編集してエラーフラグ18を出力するエラーフラグ編集回路6,シンドローム値14とエラーフラグ18から誤りパターン19を生成する誤りパターン生成回路8,誤り訂正実行回路9を備えている。
特許請求の範囲
【請求項1】 リード・ソロモン符号を用いて入力データのエラー訂正を行うエラー訂正システムであって、入力されたデータからシンドローム値を演算するシンドローム演算回路と、前記データの入力と同時に当該データの誤りを示す第1のエラーフラグを取込んで保持するエラーフラグ保持回路と、前記シンドローム値から第2のエラーフラグを生成するエラーフラグ生成手段と、前記エラーフラグ保持回路に取り込まれた前記第1のエラーフラグを計数し、計数結果に応じて前記エラーフラグ生成手段の起動の有無を制御するエラーフラグ計数回路と、前記第1および第2のエラーフラグを編集して第3のエラーフラグを生成するエラーフラグ編集回路と、前記第3のエラーフラグおよび前記シンドローム値から誤りパターンを生成する誤りパターン生成回路と、前記誤りパターンを用いて前記データの誤りを訂正する誤り訂正実行回路とからなることを特徴とするエラー訂正システム。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、エラー訂正技術に関し、特に、ディジタルデータの読み取り装置におけるリード・ソロモン符号を用いたエラー訂正処理などに適用して有効な技術に関する。
【0002】
【従来の技術】従来、ディジタルデータのエラー訂正技術としては、たとえば、特開昭58−66159号公報の「リード・ソロモン符号・復号方式」に開示された技術のように、リード・ソロモン符号を用いる場合に、読み取りデータに対して当該読み取りデータが誤りであることを示すエラーフラグを使用する復号処理方式が提案されていた。また、特公昭63−8494号公報の「多数バイトエラー訂正システム」に記載されているように、リード・ソロモン符号を用いた復号方式として、前述のようなエラーフラグを使用することなく、シンドローム値からエラーフラグを求めてエラー訂正を実行する方式が提案されていた。
【0003】
【発明が解決しようとする課題】ところが、上記の前者の従来技術のように、エラーフラグを使用する方式では、読み取ったデータに誤りがあるにも関わらず、なんらかの原因でエラーフラグが検出できなかった場合にはエラー訂正を行うことができないという問題がある。また、後者の従来技術のようにシンドローム値からエラーフラグを求める方式では、データとともに与えられるエラーフラグを使用する場合に比較してエラー訂正能力が低くなるという問題があった。たとえば、磁気テープ装置などにおいては、読み取ったデータの振幅を検出することにより、エラーフラグの検出は可能であるが、100%確実に検出できる訳ではない。
【0004】本発明の目的は、入力されたデータが誤っていることを示すエラーフラグが与えられた場合も、与えられなかった場合も、エラー訂正能力を低下させることなく、正しくエラー訂正を実行することが可能なエラー訂正システムを提供することにある。
【0005】本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【0006】
【課題を解決するための手段】本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記のとおりである。
【0007】本発明は、リード・ソロモン符号を用いて入力データのエラー訂正を行うエラー訂正システムにおいて、入力されたデータからシンドローム値を演算するシンドローム演算回路と、データの入力と同時に当該データの誤りを示す第1のエラーフラグを取込んで保持するエラーフラグ保持回路と、シンドローム値から第2のエラーフラグを検出するエラーフラグ検出手段と、エラーフラグ保持回路に取り込まれた第1のエラーフラグを計数し、計数結果に応じてエラーフラグ検出手段の起動の有無を制御するエラーフラグ計数回路と、第1および第2のエラーフラグを編集して第3のエラーフラグを生成するエラーフラグ編集回路と、第3のエラーフラグおよびシンドローム値から誤りパターンを生成する誤りパターン生成回路と、誤りパターンを用いてデータの誤りを訂正する誤り訂正実行回路とを備えるようにしたものである。
【0008】
【作用】上記した本発明のエラー訂正システムによれば、データの入力と同時に当該データが誤っていることを示す第1のエラーフラグを取込んで計数し、計数結果がある一定数以下の場合には入力されたデータのシンドローム値より第2のエラーフラグを生成するエラーフラグ生成手段を起動し、得られた第2のエラーフラグとデータとともに取り込んだ第1のエラーフラグを編集して第3のエラーフラグとし、この第3のエラーフラグとシンドローム値とから誤りパターンを発生させてエラー訂正を行う。また、第1のエラーフラグの計数値が一定値よりも大きい場合には、当該第1のエラーフラグとシンドローム値とにより誤りパターンを発生させてエラー訂正を行う。
【0009】これにより、エラーフラグが与えられた場合も、与えられない場合も、エラー訂正能力を低下させることなく、入力データを正しく修正することができる。
【0010】
【実施例】以下、本発明の一実施例であるエラー訂正システムを図面を参照しながら詳細に説明する。
【0011】図1は本実施例のエラー訂正システムを、たとえば磁気テープ装置におけるリード・ソロモン符号を用いたエラー訂正処理に適用した場合のブロック図であり、図2はエラー訂正システムを構成するシンドローム処理器の構成の一例を示すブロック図である。
【0012】まず、エラー訂正システムの説明に先立って、リード・ソロモン符号の符号化方式および復号方式について簡単に説明する。リード・ソロモン符号自体については良く知られているので説明を省略する。
【0013】最初に、符号化方式については、磁気テープ装置に適用した例として、ANSI(American Standard Extended magnetic Tape Format for Information Interchange 36-Track,parallel Serpentine)規格に提案されており、ガロア体GFT(256)において、その原始多項式を g(X)=X8 +X4 +X3 +X2 +1 ・・・(1)
とし、g(α)=0とした時、生成多項式を G(X)=(X+1)(X+α)(X+α2 )(X+α3
=X4 +α753 +α249 2 + α78X+α6 ・・・(2)
とする符号化方程式が提案されている。これによると、14バイトのデータに対して4バイトのチェックデータが生成される。(2)式で符号化されるため、14バイトのデータを、D17,D16,・・・D4 ,チェックデータをC3 ,C2 ,C1 ,C0 とすると【0014】
【数1】

【0015】をみたすようにチェックデータC3 ,C2 ,C1 ,C0 を符号化することになる。符号化の詳細な説明は、特開昭62−73336号公報において説明されている内容より容易に推測されるため、説明を省略する。
【0016】次に復号方式について説明する。
【0017】〔エラーフラグを用いた誤り訂正〕読み取られたデータに対して、そのデータが誤っていることを示すエラーフラグが与えられた場合は、特開昭58−66159号公報の技術において詳細に示されているように、エラーフラグをi,j,k,l(i>j>k>l)とすれば、誤りパターンEi ,Ej ,Ek ,El は次の(7)〜(10)式で求まる。
【0018】
【数2】

【0019】(7)〜(10)式において、S0 ,S1 ,S2 ,S3 はシンドローム値であり、次のように求まる。すなわち、読みだされたデータは誤りを含んでおり、そのデータをD17′,D16′,・・・D4 ′,チェックデータをC3 ′,C2 ′,C1 ′,C0 ′とすると、シンドローム値S0 ,S1 ,S2 ,S3 は次の(11)〜(14)式で求まる。
【0020】
【数3】

【0021】S0 =S1 =S2 =S3 のとき、読みだされたデータに誤りがなかったことになる。
【0022】以上より、エラーフラグi,j,k,lが与えられた場合は、(11)〜(14)式のシンドローム値を求め、(7)〜(10)式より誤りパターンを求めることにより、正しく修正することができる。しかし、エラーフラグが正しく与えられなかった場合(例えば、データに誤りがあるがエラーフラグが与えられなかった場合)は、(7)〜(10)式により正しく誤りパターンを求めることができない。この場合は、何らかの方法でエラーフラグを求めなければならない。
【0023】以上、この方式では、最大4バイトまでの修正が可能となる。
【0024】〔エラーフラグを使用しない誤り訂正〕読み取られたデータに対するエラーフラグを使用しないでシンドローム値だけから誤り訂正を行う方法としては、たとえば、特公昭63−8494号公報に開示された「多数バイトエラー訂正システム」に詳細に説明されている。簡単に説明すると、シンドローム値をS0 ,S1 ,S2 ,S3 (式(11)〜(14)で求まる)とすると、次の関係式をみたすi(i=0〜17)の値が存在するとき、その位置に誤りがあることがわかる。
【0025】
【数4】

【0026】(15)式より、最大2個までの誤り位置が検出でき、その時の誤りパターンEi は(17)式より求めることができる。
【0027】
【数5】

【0028】以上、この方式では、最大2バイトまでの修正が可能となる。
【0029】「エラーフラグを用いた誤り訂正」と「エラーフラグを使用しない誤り訂正」について説明したが、前者の場合には、エラーフラグをなんらかの方法で正確に与えないと正しく修正できず、また後者の場合には、最大2バイトまでしか修正できず、前者に比較して修正能力が劣ることがわかる。そこで、一般に、両者の回路を併設し、それぞれの場合に応じて修正方式を変えることが考えられるが、論理の物量が増えるという欠点がある。
【0030】そこで、本実施例のエラー訂正システムの場合には、以下のようにして、上述の問題を解決する。
【0031】図1に例示されるように、本実施例のエラー訂正システムは、シンドローム演算回路1,外部エラーフラグ保持回路2,外部エラーフラグ計数回路3,シンドローム処理器4,内部エラーフラグ発生回路5,エラーフラグ編集回路6,読み取りデータ保持回路7,誤りパターン生成回路8,誤り訂正実行回路9より構成されている。
【0032】まず、磁気テープ装置で読み取られた18バイトのデータ11(D17′,D16′,・・・D4 ′,C3 ′,C2 ′,C1 ′,C0 ′)は、読み取りデータ保持回路7に格納されると同時に、シンドローム演算回路1に入力され、このシンドローム演算回路1において、(11)〜(14)式の値を計算する。シンドロームの計算については、特開昭62−73336号公報に説明されているので説明を省略する。
【0033】また、データの読み取りと同時に、当該データ10の誤りを示す外部エラーフラグ11を、外部エラーフラグ保持回路2に取り込む。この情報は、読み取りデータの振幅などをチェックすることにより得ることができる。18バイトのデータ10を読み取った後、その外部エラーフラグ11の個数12を外部エラーフラグ計数回路3が計数し、当該外部エラーフラグ計数回路3は計数結果に応じて、シンドローム処理器4および内部エラーフラグ発生回路5の動作を制御する。
【0034】外部エラーフラグ11は、常に正確に与えられるとは限らない。つまりデータ10が誤っているのに与えられない場合もあり、また、逆に、データ10は正しいのに、誤って外部エラーフラグ11が与えられる場合も考えられる。
【0035】〔外部エラーフラグが2以下の場合〕外部エラーフラグ11が2以下の場合は、シンドローム値14よりエラーフラグを生成する。つまり、外部エラーフラグ計数回路3の制御線13により、シンドローム処理器4および内部エラーフラグ発生回路5を起動する。シンドローム処理器4により、(16)式で示した値をシンドローム演算回路1から出力されるシンドローム値14を用いて計算し、中間出力16として内部エラーフラグ発生回路5に伝達する。
【0036】本実施例の場合、シンドローム処理器4は、(16)式におけるΔ22の論理状態を反転するNOT回路22,Δ22と、Δ21およびΔ20の各々との論理積をとるAND回路23およびAND回路25,NOT回路22の出力と、Δ11およびΔ10の各々との論理積をとるAND回路24およびAND回路26,AND回路23とAND回路24の出力の論理和をとってΔ1 として出力するOR回路27,AND回路25とAND回路26の出力の論理和をとってΔ0 として出力するOR回路28で構成されている。
【0037】すなわち、Δ22の値が“0”か否かによってシンドローム値14の処理を分ける。Δ22≠0の時、Δ2 ,Δ1 ,Δ0 の値として、Δ22,Δ21,Δ20を出力し、Δ22=0の時、Δ2 =Δ22=0,Δ1 =Δ11,Δ0 =Δ10を出力するように動作する。
【0038】また、これらΔ2 ,Δ1 ,Δ0 の値を用いて、内部エラーフラグ発生回路5において(15)式を満足するiの値(i=0〜17)を求める。iの値が求まったら、その値を内部エラーフラグ17としてエラーフラグ編集回路6に入力し、当該エラーフラグ編集回路6は、外部エラーフラグ保持回路2に保持されていた外部エラーフラグ15の値の両方により、エラーフラグ18(i,j,k,l)を編集する。例えば、外部エラーフラグ保持回路2の出力と、内部エラーフラグ発生回路5の出力が同一であった場合には、その値をi,jと編集する(i>j,k=l=0)。
【0039】また、外部エラーフラグ保持回路2の出力と、内部エラーフラグ発生回路5の出力が異なった場合、各々の出力が二つづつの場合には、i,j,k,lを、i>j>k>lとなるように編集する。次に、エラーフラグ編集回路6のi,j,k,lの値と、シンドローム演算回路1のS0 ,S1 ,S2 ,S3 の値を用いて、(7)〜(10)式で示した誤りパターン19を誤りパターン生成回路8で生成する。誤りパターン生成回路8の動作は、特開昭58−66159号公報に詳しく説明されているので説明は省略する。最後に、誤りパターン生成回路8の出力である誤りパターン19と、読み取りデータ保持回路7に保持されていたデータ20との排他的論理和を誤り訂正実行回路9においてとることにより、誤り訂正が実行され、誤り訂正済出力21を得る。
【0040】〔外部エラーフラグが3以上の場合〕外部エラーフラグが3以上の場合は、シンドローム値14よりエラーフラグを見いだすシンドローム処理器4および内部エラーフラグ発生回路5などを動作させると誤動作する可能性があるため(最大2バイトまでしか検出できない)、外部エラーフラグ計数回路3は制御線13により、当該シンドローム処理器4および内部エラーフラグ発生回路5をリセット状態とする。エラーフラグ編集回路6は、外部エラーフラグ保持回路2の値だけを用いて、i>j>k>lとなるようにエラーフラグの編集を行う。その後の動作は、外部エラーフラグが2以下の場合と同一である。
【0041】以上本発明者によってなされた発明を実施例に基づき具体的に説明したが、本発明は前記実施例に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【0042】
【発明の効果】本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば、以下のとおりである。
【0043】すなわち、本発明のエラー訂正システムによれば、エラー訂正能力を低下させることなく、入力されたデータが誤っていることを示すエラーフラグが与えられた場合も、与えられなかった場合も、正しくエラー訂正を実行することができるという効果が得られる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013