JP6046403B2

JP6046403B2 - 誤り訂正符号の符号化方法及び復号方法

Info

Publication number: JP6046403B2
Application number: JP2012158060A
Authority: JP
Inventors: 淳江角; 凱李
Original assignee: SIGLEAD Inc
Current assignee: SIGLEAD Inc
Priority date: 2012-07-13
Filing date: 2012-07-13
Publication date: 2016-12-14
Anticipated expiration: 2032-07-13
Also published as: JP2014022848A; US9548761B2; US20140019822A1

Description

本発明は、データの誤り訂正に用いる誤り訂正符号の符号化方法及び復号方法、さらに、それに対応する符号化装置及び復号装置に関する。

現在、情報処理と情報通信の分野において、文章、静止画、動画、音声等の伝達したい情報をバイナリ化した情報記号系列すなわちデータの送受信や保存に伴って発生する誤りを発見し、訂正することは必須となっている。ネットワークにおける通信や、ＤＶＤ、フラッシュメモリなどの記憶メディアへのデータの書き込みと、それらからのデータの読み出しなどの際に、ノイズの混入やメディアの不完全性などによるデータの誤りが生じる。このような誤りの発生に対処するため、あらかじめデータに加えておいた冗長符号を用いて、誤りが生じたかどうかを発見し、誤りがあれば元のデータを再現することが行われる。つまりもとのデータに冗長符号を追加して符号語系列に変換することが行われている。このような冗長化された符号語系列を誤り訂正符号と言う。

例えば、フラッシュメモリと呼ばれる不揮発性半導体メモリは、小型化、大容量化が進んでいる。このようなフラッシュメモリの記憶領域は、一定のサイズの複数のブロックから構成されており、各ブロックは一定のサイズの複数のページから構成されている。そして、データの消去はブロック単位で行われ、データの読み込み及び書き込みはページ単位で行われる。このフラッシュメモリのセルの微細化と多値化により、記憶容量が大きくなっている。その副作用として、誤りビットも増加する。この誤りを訂正するために、誤り訂正符号（ECC, Error Correcting Code）を用いて誤り訂正を行うことが一般的である。誤り訂正符号の例としては、ＢＣＨ符号、リード・ソロモン符号（Reed-Solomon Code）、低密度パリティ検査符号（LDPC Code, Low-Density Parity-Check Code）が挙げられる。

フラッシュメモリにおいて、ある１つのページは例えば４つに分割されている。つまり、領域が４つ並んで１つのページが構成されることになる。そして、このような領域の一つ一つに一個の誤り訂正符号を格納する。この誤り訂正符号は、情報記号（元のデータ）に加えて、ある誤り訂正符号化方式に対応するパリティ検査記号（冗長ビット）を有している。符号化方式が同じであれば冗長ビットの数が大きければ大きいほど、誤り訂正能力は向上する。メモリセルの多値化や微細化に対応して、あるいは信頼性の向上を目的として、冗長ビット数は増大する傾向にある。その一方で、冗長ビットの数またはそれに対応して決まる訂正可能な誤りビットの数が増加すると、誤り訂正回路の規模も増大する。このような回路規模の増大は、メモリの実装面積の減少を招き、記憶容量の減少をもたらす。また、ユーザデータを読み取って再生するのに要する時間の増加にもつながる。したがって、冗長ビット数を増加させずに、誤り訂正能力を向上させることが求められている。

誤り訂正能力の向上は、通信分野においても同様に重要である。通信回線速度の向上などに伴い、より高い誤り訂正能力が限定的な物理的リソースの中で求められている。本願明細書及び特許請求の範囲においては主に記憶媒体の分野で用いられる「ページ」という言葉を主に使用するが、これは、一単位のデータというほどの意味であって、送信データブロックとかトランスポートブロックと呼ばれている通信の分野で用いられる概念をも包含するものである。例えば、Long Term Evolution（LTE）規格、または標準化団体である3GPPにおけるE-UTRA (Evolved Universal Terrestrial Radio Access)規格における「トランスポートブロック」がそれに相当する。

特許文献１には、誤り率の高い部分と低い部分を一つのＥＣＣフレームに混在させることで、各ＥＣＣフレーム間で誤り率の場所依存によるバラツキが均一化されて、誤り訂正の効率が向上する不揮発性半導体記憶装置が記載されている。

特許文献２には、トランスポートブロックを、各コードブロックが他のコードブロックの一部を含むように複数のコードブロックに分割し、複数のコードブロックの各々に対して誤り訂正符号化処理を行ってコードブロックコードワードを生成し、コードブロックコードワードを結合してトランスポートブロックコードワードを生成する技術が開示されている。図示された全ての例において、最左端と最右端のコードブロックの間で重複部分を設けている。

特開２００８−１０８２９７号公報特開２０１１−００３９７５号公報

このような課題に鑑み、本発明は、新たな誤り訂正符号の作成方法を提供するものである。

本発明の第１の実施態様によれば、一つのページを構成する符号化する前のデータを該一つのページの一端にある第１データブロックから該一つのページの他端にある第Ｍデータブロックに分割するステップと、ここで、Ｍは３以上の整数であり、第１データブロックを符号化して第１誤り訂正符号を得るステップと、第１誤り訂正符号または第１データブロックの一部と第２データブロックを合わせて符号化して第２誤り訂正符号を得るステップと、第２データブロックに対して行った処理を合わせる誤り訂正符号またはデータブロックを一つずらしながら第３データブロック以降第Ｍ−１データブロックまで行うステップと、第Ｍ−１誤り訂正符号または第Ｍ−１データブロックの一部と第Ｍデータブロックを合わせて符号化して第Ｍ誤り訂正符号を得るステップとを含み、第１誤り訂正符号を得るステップから第Ｍ誤り訂正符号を得るステップを順次または同時に行うものである、符号化方法が提供される。

また、本発明の第２の実施態様によれば、一つのページを構成する符号化する前のデータを該一つのページの一端にある第１データブロックから該一つのページの他端にある第Ｍデータブロックに分割するステップと、ここで、Ｍは３以上の整数であり、第１データブロックと第２データブロックの一部を合わせて符号化して第１誤り訂正符号を得るステップと、第１誤り訂正符号または第１データブロックの一部と第２データブロックと第３データブロックの一部を合わせて符号化して第２誤り訂正符号を得るステップと、第２データブロックに対して行った処理を合わせる誤り訂正符号またはデータブロックを一つずらしながら第３データブロック以降第Ｍ−１データブロックまで行うステップと、第Ｍ−１誤り訂正符号または第Ｍ−１データブロックの一部と第Ｍデータブロックと合わせて符号化して第Ｍ誤り訂正符号を得るステップとを含み、第１誤り訂正符号を得るステップから第Ｍ誤り訂正符号を得るステップを順次または同時に行うものである、誤り訂正符号化方法が提供される。

ここで、合わせて符号化する部分が元のデータブロックの大きさに比べて小さい、あるいは、重複して符号化されない部分が比較的大きいデータブロックに対して、そうでないデータブロックに対するより強力な誤り訂正能力を適用して、全体的な性能を向上させることができる。

本発明の第３の実施態様によれば、上記のいずれかの誤り訂正符号化方法により符号化された第ｋ誤り訂正符号を復号して、誤りの訂正が可能であったか否かを判断するステップと、訂正ができなかった場合には、第ｋ誤り訂正符号と合わせて符号化された部分がある第ｋ＋１誤り訂正符号または第ｋ−１誤り訂正符号あるいはそれらの両方が訂正できるかを判断して、訂正できた誤り訂正符号を利用して第ｋ誤り訂正符号の対応する部分を置換するステップと、置換された第ｋ誤り訂正符号を復号するステップとを含んでなる誤り訂正復号方法が提供される。

また、上記の符号化方法においてＭ＝２の場合を考えると、本発明の第４の実施態様によれば、一つのページを構成する符号化する前のデータを第１データブロックと第２データブロックの二つのデータブロックに分割するステップと、第１データブロックを符号化して第１誤り訂正符号を得るステップと、第１誤り訂正符号または第１データブロックの一部と第２データブロックを合わせて符号化して第２誤り訂正符号を得るステップとを含んでなる符号化方法が提供される。

また、変形例として、第１データブロックと第２データブロックの一部を合わせて符号化して第１誤り訂正符号を得て、第１誤り訂正符号または第１データブロックの一部と第２データブロックを合わせて符号化して第２誤り訂正符号を得る符号化方法が提供される。

上記の第４の実施態様とその変形例により符号化された第１誤り訂正符号を復号して、誤りの訂正が可能であったか否かを判断するステップと、訂正ができなかった場合には、第２誤り訂正符号が訂正できるかを判断して、訂正できた誤り訂正符号を利用して第１誤り訂正符号の一部分を置換するステップと、第１誤り訂正符号の訂正ができた場合には、第２誤り訂正符号の第１誤り訂正符号と合わせて符号化された部分を置換して、第２誤り訂正符号の復号を行うステップとを含んでなる誤り訂正復号方法が提供される。

さらに、本発明の装置にかかる第５の実施態様として、一つのページを構成する符号化する前のデータを該一つのページの一端にある第１データブロックから該一つのページの他端にある第Ｍデータブロックに分割するページデータ分割部と、元のデータブロックに、一定のルールに従って、隣接するデータブロックまたは誤り訂正符号の一部のデータを付加して、符号化の対象となるデータを作成する符号化準備部と、作成されたデータに対する符号化を行って各データブロックに対応する誤り訂正符号を生成する誤り訂正符号化部と、生成された誤り訂正符号を結合して、符号化ページデータを作成する結合部とを備える符号化装置が提供される。

そして、本発明の第６の実施態様として、符号化の際に使ったルールに基づいて符号化ページデータをそれを構成する個々の誤り訂正符号に分離する符号分離部と、分離された誤り訂正符号を復号する復号部と、復号されたデータが誤りを含むか否かをチェックする誤り検出部と、もし、ある誤り訂正符号を復号して得られたデータに誤りがあった場合に、当該誤り訂正符号と合わせて符号化された部分がある１または２の誤り訂正符号が誤りなく訂正できるかを誤り検出部により判断して、誤りなく訂正できた誤り訂正符号を利用して当該誤り訂正符号の部分を置換して、置換誤り訂正符号を作成して、前記バッファに戻す置換符号作成部と、誤りなく訂正されたページデータを出力するページデータ再構成部とを備える復号装置が提供される。

本発明の符号化方法の１例を従来技術との対比で示す概念的なダイアグラムである。本発明の符号化方法の別の一例を示す概念的なダイアグラムである。本発明の動作原理を説明するための概念的なダイアグラムである。本発明による復号方法の一例を示すフローチャートである。本発明の符号化方法の第２例と第３例を示す概念的なダイアグラムである。別の符号化の例を示す概念的なダイアグラムである。図６の符号化の問題点を示すための概念的なダイアグラムである。図７（Ａ）の誤りの分布例が図１（Ｂ）に示した符号化方法の例により訂正可能であることを示す概念的なダイアグラムである。本発明に係る重複のさせ方の一例を示す概念的なダイアグラムである。本発明に係る重複のさせ方の一例を示す概念的なダイアグラムである。本発明に係る重複のさせ方の一例を示す概念的なダイアグラムである。本発明に係る重複のさせ方の一例を示す概念的なダイアグラムである。本発明に係る重複のさせ方の一例を示す概念的なダイアグラムである。本発明の別の態様の効果を示すためのシミュレーション結果を示すグラフである。本発明にかかる符号化装置の一例のブロックダイアグラムを示す。本発明にかかる復号装置の一例のブロックダイアグラムを示す。

以下に本発明の実施形態を説明する。ここでは、例としてＢＣＨ符号を用いてフラッシュメモリの誤り訂正を行う場合について説明するが、本発明は、組織符号(systematic code)であれば、ＢＣＨ符号以外にも、ＲＳ符号、ＬＤＰＣ符号などを利用して、全く同様に実施できる。組織符号は、符号語に元のデータ（「情報記号」(information symbols)とも呼ばれるが、ここでは単に「データ」という）がそのままの形で表れる符号をいう。一つの符号語はデータと検査記号からなり、含まれるパリティ検査記号（parity check symbols; 以下、「パリティ」という）は、データに隣接して並べておいたり、データの中に置いたり、あるいは別の場所に保存したりすることがある。また、データの誤り訂正であれば、フラッシュメモリに限らず、通信、ＤＶＤ、ハードディスクなどに求められるいずれの情報処理にあっても実施することができる。

図１に本発明による符号化方法の一例を示す。一般に、組織符号（ＢＣＨ符号、ＲＳ符号、ＬＤＰＣ符号など）により符号化する場合、データとそれに付加するパリティが作成される。図１（Ａ）に示すように、符号化の対象となる４つのデータブロックがあるものとする。通常のＢＣＨ符号化であれば、このうちのデータブロック１に対してまず、所定の処理を行って、パリティ１を作成する。データブロック１とパリティ１とは関連づけられていて、復号の際には読み取られたデータブロック１とパリティ１とを利用して、誤り訂正後のデータブロック１を得る。もちろん誤りがデータブロック１とパリティ１に多く含まれていれば、誤り訂正に失敗することになる。

図１（Ａ）では、BCH(t-bit/N-Byte)は、訂正可能な誤りの最大ビット数がｔであって、ＢＣＨ符号長がＮであることを表す。ここで、Ｎの単位はバイトであるが、バイトに固定されるものではないことはいうまでもない。フラッシュメモリを例に取ると、ある符号化前のデータをいくつかに分割して得られたデータブロックのそれぞれを符号化してＢＣＨ符号語を得る。そして、誤り訂正は、データブロック１からデータブロック４のそれぞれに適用されており、隣のＢＣＨ符号の復号の結果が、そのＢＣＨ符号の復号の作業又は結果に影響を与えることはない。

図１（Ａ）に示した態様では、このＢＣＨ符号とパリティとは分けて１ページ内に保存されている。ＢＣＨ符号は組織符号であるので、元のデータとパリティがあって、データブロック１からデータブロック４のあとにパリティ１からパリティ４までをまとめて保存する場合を図示している。ここでは、パリティが以下に説明する重ねて読み取る部分にない。このデータブロックとそれに対応するパリティの保存位置の物理的な関係はまったく任意である。これをデータブロック２、データブロック３と繰り返して符号化する。

次に、本発明による符号化構造の第１例による処理プロセスを図１（Ｂ）を参照して説明する。まず、図１（Ａ）のデータブロック１をＢＣＨ符号化して、そのパリティをパリティ１として右側に保存する。その後、データブロック２については、データブロック１の一部、図１（Ｂ）において、データブロック１の斜線で示してある部分をデータブロック２に合わせて得られるＮ_２バイトのデータブロックに対してＢＣＨ符号化の処理を行い、パリティ２を得る。ここでの符号化はＮ_２バイトに対して、ｔビットの訂正能力を有するものとなる。同様の符号化を、データブロック２の右端の一部（斜線部）のデータをデータブロック３と合わせたものに対して行い、パリティ３を得る。データブロック４については、データブロック３の右端の一部（斜線部）のデータと合わせて符号化を行い、パリティ４を得る。つまり、斜線をした部分については、２回重ねて符号化の対象となるので、以下において「重複部分」あるいは「重複する部分」と呼ぶことがある。図示したパリティの保存位置は一例に過ぎない。パリティの保存位置は、任意であることは上述のとおりである。なお、上の説明では、わかりやすさを優先して、左端のデータブロックから右のデータブロックへと順次符号化をしていったように記載したが、実際には、全てのデータブロックに対する符号化を同時に行うことができ、その方が実行速度は当然速くなる。

言い方を変えると、図１（Ｂ）では、１ページを構成する４つのデータブロックのうち左端のデータブロック１についてはそのまま符号化を行い、それ以外の３つのデータブロックに対しては、ＢＣＨ符号の長さを幾分増大させるように符号化している。つまり、増大させた部分のデータは次の右隣の符号の左端のデータ（斜線部）と同じになるように符号化を行う。逆に言えば、符号化されたデータブロックの右端にある符号化前のデータをそのまま用いて、次の領域のつまり、右隣の符号を作成する。その結果、対象となる４つのＢＣＨ符号が互いに「重複」する部分があるように符号化している。ここで「重複」とは、隣り合うデータブロックの一部を次のデータを符号化するときに再度用いることをいう。この「重複」のさせ方には、いろいろな態様が考えられるが、ここでは、ＢＣＨ符号化の対象となったデータブロックの端が左隣のデータブロックの右端と同じになるようにしており、左端のＢＣＨ符号は左端のデータブロック１をそのまま符号化したものになる。ここで、データブロック２〜４のＢＣＨ符号の長さをＮ_２とするが、このＮ_２は上述のＮより大きな整数である。左端のＢＣＨ符号されたデータブロックの大きさはもとのままＮである。他方、ＢＣＨ符号化されたデータブロック２〜４の大きさはＮより大きいＮ_２であるので、これをBCH(t-bit/N₂-Byte)と表現することにする。ここで、重複部分のバイト数をＬとし、重複していない部分のバイト数をＭとすると、Ｎ_２＝２Ｌ＋Ｍとなる。なお、本願明細書においては、本願発明の実施態様と区別するために、このような重複を設けない符号化の例を「通常のＢＣＨ符号化」と呼んでいる。

整理すると、図１（Ｂ）に示した符号化においては、通常のＢＣＨ符号化と同じ訂正能力を有するデータブロックが必ず存在する。それは、図示した例では左端のデータブロック１である。このデータブロックは、通常のＢＣＨ符号化と同じ符号化がなされるので、通常のＢＣＨ符号で訂正できるのであれば、必ず訂正できる。それ以外のデータブロックについては、重複する部分については、重なり合っている２つのＢＣＨ符号の一方が訂正を実行することが可能であれば、ＢＣＨ符号のもつｔビットの訂正能力を使って、Ｎバイトより短いＭバイトの訂正を担当することになるので、訂正できる確率が高くなる。したがって、通常のＢＣＨ符号化よりも本発明の図１（Ｂ）に示した符号化は高い訂正能力を必ず示すことが分かる。

図１（Ｃ）に、本発明の第２の符号化の例を示す。符号化の対象となるデータブロックの右隣にパリティを置いて、次のデータブロックを符号化する際の重複部分に含める態様である。より具体的には、まずデータブロック１を符号化して、パリティ１を得る。その後、その右隣にパリティ１を置いて、データブロック１の右端とパリティ１を重複部分としてデータブロック２を符号化する。そして、その結果得られたパリティ２をその符号化の対象となった重複部分を含んだデータブロックの右隣に置く。これを順次繰り返し、最後のデータブロック４と重複部分からなるデータの右隣にパリティ４を置いて符号化を終了する。この例であると、データブロック１から順次符号化していくことになり、全てのデータブロックに対して同時に符号化を行うことはできない。

なお、図１の（Ｂ）と（Ｃ）の符号化構造においては、符号化の様子をより分かり易くするために、符号化するデータブロックを階段状に並べて表示しているが、別に上のデータを下のデータにコピーしているわけではなく、上のデータの一部を下のデータの一部を符号化する際に含めているという意味である。実際のデータの保存状況は、図１（Ａ）の場合と何ら異なることはない。図２以下においても、同様である。また、図２以下の符号化構造を示す図においてはパリティを格納する物理的な位置は特に明示していないが、図１（Ｂ）の態様と図１（Ｃ）の態様の両方を包含しているものと解すべきである。

ここで、注意しておきたいのは、図１（Ｂ）と（Ｃ）のように、左から２番目以降のデータブロックの大きさを増大させることは必ずしも必要ないことである。左隣のデータブロックから重複して読み取った部分さえ設ければ、ＢＣＨ符号の大きさはＮのままでもかまわない。そのような場合には、重複部分の存在に対応してＢＣＨ符号の数が大きくなることになる。極端な例であるが、図２に示すように、ＬをＮ／３として、同じページから読み取るＮバイトのＢＣＨ符号の数を３から４にすることもできる。この場合には復号のための回路の数も３から４に増える。また、隣接するＢＣＨ符号の間で重複部分を設けているが、隣接している必要は必ずしも無く、一つおきなどの種々の態様で重複部分を設けることができる。なお、図２以降においては、パリティの位置を図示していない。上述のようにパリティをどの物理的位置に保存するかは、本発明の文脈ではさほど重要でないからである。

本発明の原理を理解するために、図３に示すような簡単な例を考えてみる。図３では、図１（Ａ）の４つのデータブロックｋ−１、データブロックｋ、データブロックｋ＋１、データブロックｋ＋２などを互いに重なり合うように読み取って、符号化する。図３のそれぞれのデータブロックが一つ一つのＢＣＨ符号に対応しているのは上述の通りである。×印は、誤りビットの存在位置を意味している。データブロックｋ−１を見ると３個の誤りビットが存在している。このデータブロックｋ−１をそのまま符号化したものが符号ｋ−１になる。ここで、訂正可能な誤りビット数ｔ＝４であると仮定すると、４以下である３個の誤りビットはうまく訂正できることになる。しかし、データブロックｋとデータブロックｋに隣接するデータブロックｋ−１との重複部分(斜線部)を符号化した符号ｋには６個の誤りビットがあるので想定しているＢＣＨ符号化方式では訂正ができない(つまり、５個以上の誤りビットは訂正できない)。通常であれば、この領域の訂正はあきらめるしかない。しかし、データブロックｋ＋１とそれに隣接するデータブロックｋとの重複部分を符号化した符号ｋ＋１を見ると、ここには４個の誤りビットしかないので、この符号ｋ＋１は正しく訂正できる。すると、符号ｋ−１と符号ｋ＋１とが正しく復号できるので、正しいデータによって重複部分(斜線部)のデータを置換することによって、符号ｋのうちデータブロックｋ−１とデータブロックｋ＋１とが重複する部分にある３個の誤りビットは訂正可能である。すると、符号ｋの残りの誤りビットは３個となり、両側の領域からの訂正を加味することによって符号ｋの誤りビットを訂正できることになる。ただ、重複していない部分に５個の誤りビットがある場合には、本実施態様によっては訂正ができない。

他方、ここでは、１つの訂正不可能な符号の隣の符号が両方とも訂正可能である場合を例に取ったが、２つの隣接する符号が共に訂正不可能であっても、さらにその外側に隣接する２つの符号が訂正可能であれば、２つの訂正不可能な隣接符号の訂正が可能になって、真ん中の符号が訂正可能になる場合もありうる。

本発明の原理から次のような特徴のうちの少なくとも１つがいえることが分かっている。すなわち、（１）まず、原理的に見て、通常の誤り訂正符号化法より、誤り訂正能力が下がることはない。言い換えれば、通常の誤り訂正符号化法により訂正できる場合は、本発明の重複の原理を利用した方法あるいは符号化構造でも必ず訂正できる一方、通常の誤り訂正によって訂正できない場合でも、本発明の重複の原理を利用した符号化構造または符号化方法によれば訂正できる可能性がある。（２）次に、誤りの状態が同じであれば（誤り率が同じであれば）、同じ冗長ビット数に対して、本発明のデータの重複を用いた符号化方法と復号方法によれば、必ず通常の誤り訂正より性能が向上する。（３）さらに、同じガロア域(Galois field)(例えば、２の１４乗のガロア域)に対して本発明の符号の重複を用いる場合、通常の誤り訂正方法と比べて、必要とする訂正回路の物理的な規模はあまり変わらない。

このような本願発明の一実施態様にかかる復号のための情報処理のフローの一例を図４に示す。まずｎ個のＢＣＨ符号が各ページにあるとして、それらの符号をC(1)、C(2)、C(3)、…、C(n)とする。これは符号化のときに用いたルールを参照しつつページデータを各符号に切り分けることで作成されるものである。 L(k,0)とL(k,1)は、ＢＣＨ符号C(k)におけるそれぞれC(k-1)とC(k+1)とのオーバーラップ領域を表すものとする。ここで、各符号についてその符号が訂正可能であるかどうかを表すフラグの数値列F=｛F(1), F(2),…, F(n)｝を定義する。すなわちFはベクトル値を表すが、F(1), F(2)などはスカラ量である。C(k)が復号によって訂正可能であればF(k)=0とし、訂正不可能であればF(k)=1とする。その上で、図４のフローを実行する。

まず、kを初期値にセットする(k=1)（ステップＳ１)。C(k)を復号して、訂正が可能であったか不可能であったかを示すフラグ値F(k)を得る(ステップＳ２)。C(k)に含まれる誤りが訂正可能であればF(k)=0であるので、ステップＳ４に進むが、F(k)=1であればステップ５に進む（ステップＳ３）。F(k)=0であれば、復号されたビットの対応部分を用いてL(k+1,0)を置換する（ステップＳ４）。これをk=1からk=nまで繰り返す（ステップＳ５、Ｓ６）。k=nまで繰り返されると数値列Fの数値が全てゼロであるかをチェックする（ステップＳ７）。もし全てゼロであれば、復号の結果を出力して、処理を終了する（ステップＳ２０）。数値列Fに一つでも１があれば、kを１にリセットして、FをF’として保存して(ステップＳ８)、隣接する符号の復号値を利用して、訂正できなかった符号が訂正できるかを試みる。

まず、F(k)=1であるかを調べて、訂正できなかった符号を特定する（ステップＳ９）。F(k)=1であって、訂正できなかった場合には、F(k-1)がゼロであるか、つまりC(k-1)が訂正できているかを調べて(ステップＳ１０)、もし訂正できていれば、C(k)の重複部分の一つであるL(k,0)をC(k-1)の復号結果を使って置換する（ステップＳ１１）。C(k-1)が訂正できていなければ、何もせずに次のステップに移る。次に、F(k+1)がゼロであるか、つまりC(k+1)が訂正できているかを調べて(ステップＳ１２)、もし訂正できていれば、C(k)の重複部分の残りの一つであるL(k,1)をC(k+1)の復号結果を使って置換する（ステップＳ１３）。C(k+1)が訂正できていなければ、何もせずに次のステップに移ることになる。改めて、C(k)を復号し、その訂正が可能であったか否かの検証結果を新たなF(k)の値とする（ステップＳ１４）。これをk=1からk=nまで繰り返す(ステップＳ１５、Ｓ１６)。

もし、ステップＳ９においてF(k)=1でなければ、ステップＳ１５に直接進む。

もし新たなFと保存してあったF’が同じでなければ、つまり、訂正できなかった符号が一つでも訂正できていれば（ステップＳ１７）、そして、トライアル回数がＴｍａｘという予め設定した最大値を超えていなければ（ステップＳ１９）、ステップＳ８に戻って、訂正できるようになった符号によって、訂正できなかった隣接する符号が正しく復号できるか試みる。F=F’であれば、それ以上繰り返してももう改善は望めない状態にあることになるので、F=0であれば（ステップＳ１８）、現在までの結果であるC(k)の値を出力し(ステップＳ２０)、数値列Fが一つでも1を含んでいれば（ステップＳ１８）、正しい復号ができなかった旨を宣言して終了する（ステップＳ２１）。この繰り返しは、それが必要な場合でも、１、２回程度行うことになるのが普通である。

図５に本発明のＢＣＨ符号化の第３例と第４例を示す。図５（Ａ）に通常のＢＣＨ符号を参照のために示す。データ長がＮ−ｂｙｔｅであるとし、訂正可能ビット数がｔであるとすると、上と同様にＢＣＨ（t-bit/N-byte）と表現することができる。パリティはあえて図示していない。図５（Ｂ）に、左右対称に重なり部分を作る場合である第３例を示す。ここでは、データブロック１に対応するＥＣＣ１は、右側のみに重なる部分があって、ＢＣＨ（t-bit/N₁-byte）となる。そして、その次のデータブロック２に対応するＥＣＣ２は、左右に重なる部分があるので、ＢＣＨ（t-bit/N₂-byte）となる。ＥＣＣ３はＥＣＣ２と同様であり、ＥＣＣ４は重なり部分が左にあること以外はＥＣＣ１と同じである。ここで、Ｎ＜Ｎ_１＜Ｎ_２であり、重なりがない部分は、ＥＣＣ１からＥＣＣ４間で同じ長さである。

図５（Ｃ）に、本発明の符号化の第４例を示す。図５（Ｃ）の例は、図１（Ｂ）の例と似ているが、ＥＣＣ４についてのみ訂正能力が高い符号化ＢＣＨ（(t+a)-bit/N₂-byte）を採用している。図５（Ｃ）においては、４つのＥＣＣブロックは、非対称に配列される。つまり、ＥＣＣ１の長さは通常のＢＣＨ符号と同じＮである一方、ＥＣＣ２とＥＣＣ３は左右に重なり部分があって、その長さが大きくなっている。ＥＣＣ２とＥＣＣ３は、ＢＣＨ（t-bit/N₂-byte）と表現できる。ここで、Ｎ＜Ｎ_２である。そして、ＥＣＣ４は、その長さがＥＣＣ２とＥＣＣ３と同じＮ_２である一方、重なり部分が一つしかないので誤り訂正能力は弱くなる。言い換えれば、重なりのない部分のデータの長さがＥＣＣ４だけ大きくなっている。この符号化構造では、通常のＢＣＨ符号化の場合に訂正可能な誤りは、必ず訂正でき、通常のＢＣＨ符号化よりも性能がよいことが分かっているが、ここでは、さらに、ＥＣＣ４の訂正能力を補強するために、ａバイトの誤り訂正能力を付加する。ａは任意の整数であるが、例えば、ｔ＝４であるとき、２バイト３バイト程度でも十分な効果があるものである。これにより全体的な訂正能力を一段と向上させることができる。ＥＣＣ４だけ訂正能力を増やしても、誤り訂正回路の全体的な規模やパリティのサイズに対する影響はほんのわずかである。

図６（Ｂ）に、図６（Ａ）の通常のＢＣＨ符号化と対比して、左右対称な符号化構造を採用したリング構成の符号化の場合を示す。実は、この構成は余り好ましくないことが分かっている。これは、基本的に図５（Ｃ）の構成において、ＥＣＣ４の右端に重なり部分を設け、これをＥＣＣ１の左に付加する形で、ＥＣＣ１の長さも他と同じＮ_２にした構造である。このような構造では、全体的な確率を考えると図７（Ａ）の通常の符号化の場合よりも性能はよいが、通常の符号化により補正できる場合であっても、図６（Ｂ）の符号化では補正できない場合があることが分かっている。これを、図７を使って説明する。

図７（Ａ）に示す通常のＢＣＨ符号化の場合において、ｘで示す誤りビットが含まれているとする。すると、この誤りビットの数はそれぞれのデータブロックにおいて４個か３個であるので、４ビットの訂正能力のあるＢＣＨ符号を用いれば、全て訂正できるはずである。ところが、図７（Ｂ）に示すように、図６（Ｂ）に関連して上に説明した符号化構造を採用すると、全てのＥＣＣに５以上の誤りがあるので、４ビットの訂正能力では、いずれのＥＣＣにおいても誤りを訂正できないことになる。現在、訂正能力のビット数に基づいてコントローラを設計しているので、通常の符号化で訂正できるものが新しい符号化構造を採用することによって訂正できなくなるのは好ましくない。

図８（Ｂ）に示すように、図１（Ａ）に示した符号化を採用すれば、図７（Ａ）に示したような誤りの分布がある例であって、ＥＣＣ４に特段強化された誤り訂正を掛けることがなくても、全ての誤りを４ビットの誤り訂正能力があれば訂正することができる。つまり、通常の符号化により訂正できるものは、本発明の符号化構造においても必ず訂正できることが分かっている。このことは、図５（Ｂ）に示した符号化構造を採用した場合でも同じである。また、図５（Ｃ）について説明したように、ＥＣＣ４についてのみより訂正能力の高い、例えば、６ビットの訂正能力のある誤り訂正回路を採用することもできる。これにより全体的な誤り訂正回路の物理的な大きさはさほど増大させることなく、全体的な性能をさらに向上させることができる。

図９〜図１３に、本発明の符号化方法によるデータの重複のさらなる実施形態を示す。ここでは、パリティの記載を省略している。図９においては、第１の誤り訂正符号ＥＣＣ１のデータ部分の領域Ａのデータを隣接する第２の誤り訂正符号の領域Ｂに重複させて誤り訂正符号ＥＣＣ２とする。重複部分のビットサイズは対応するもの同士同じであるが、重複部分のそれぞれの誤り訂正符号の中での位置が異なっている。図１０は、第１の誤り訂正符号ＥＣＣ１と第２の誤り訂正符号ＥＣＣ２との間の重複部分が二つある例を示す。ＥＣＣ１の領域Ａと領域Ｂとが、ＥＣＣ２の領域Ｄと領域Ｃとでそれぞれ重複している。図１１は、同じデータＡとデータＢとを４つの誤り訂正符号ＥＣＣ１、ＥＣＣ２、ＥＣＣ３、ＥＣＣ４の間で共通になっている例を示す。ＥＣＣ４は、他の誤り訂正符号より長さが短い。図１２は、誤り訂正符号の大きさが全て異なる場合を示している。同じデータＡとデータＢが３つの誤り訂正符号ＥＣＣ１、ＥＣＣ２、ＥＣＣ３の間で共通になっている。図１３にある例では、第２の誤り訂正符号ＥＣＣ２が第１の誤り訂正符号ＥＣＣ１より短く、ＥＣＣ２のすべてのデータが、第１の誤り訂正符号の一部と共通であるような例も可能である。このように重複部分の位置あるいは大きさを変えることによって、個々の領域のうちのエラーが起きやすい部分を重複部分として、復号の成功率を高めることができる。

図１４は、図１（Ｂ）と図５（Ｃ）の符号化の例の効果を、通常のＢＣＨ符号化方法と対比するためのシミュレーションの結果を示すグラフである。条件としては、ページサイズが８ｋＢで、これを８つの領域に分けたので、各領域の大きさは１ｋＢである。２元対称通信路 (Binary Symmetric Channel, BSC)においてランダムに誤りが発生するモデルを採用した。符号化率(code rate)は0.9609であるとした。比較のための通常のＢＣＨ符号としてはBCH(24bits/1024Bytes)を用い、本発明によるオーバーラップモデルとしてはBCH(24bits/1336Bytes)を採用した。つまり、基本的に、上記８つの領域のうちの左端にある領域にはBCH(24bits/1024Bytes)を用い、残りの領域については左隣の領域内の右端の312バイトのデータをそのまま用いて元のデータを符号化することにより全ての領域についてBCH(24bits/1336Bytes)とした。ただし、「通常のＢＣＨ符号２」と「重複ＢＣＨ符号２」については、図５（Ｃ）に示したように、右端のＥＣＣの訂正能力を３ビット向上させたものとしてBCH(27bits/1336Bytes)を採用した。重複部分が少なくなるＥＣＣについてのみ、より強力な誤り訂正回路を適用することにより、通常のＢＣＨ符号化ではたいした性能の向上は見られないが（当然ではある）、本発明の重複符号化法においては、相当な性能の向上が見られた。通常の符号化と図１(Ｂ)の符号化で誤り率は５分の１程度に減少していることが分かる。本発明の誤り訂正前の誤り率と訂正できなかったビット誤り率とをそれぞれ対数スケールでｘ軸とｙ軸とにプロットした。ここで、「訂正できないビット誤り率」は、「訂正できないページのカウント」を「全ページ数」と「ビットで表したページの大きさ」で除したものであると定義する。

図１５に本願発明にかかる符号化装置の一例のブロックダイアグラムを示す。符号化装置１０は、符号化前のページデータを受け付けて、それを符号化ページデータとして出力するものである。符号化装置１０は、ページデータ分割部１２と、符号化準備部１４と、誤り訂正符号化部１６と、結合部１８とを含んでいる。ページデータ分割部１２は、一つのページを構成する符号化する前のデータを該一つのページの一端にある第１データブロックから該一つのページの他端にある第Ｍデータブロックに分割する（Ｍは２または３以上の整数）。そして、符号化準備部１４は、元のデータブロックに、一定のルールに従って、隣接するデータブロックの一部のデータを付加して、符号化の対象となるデータを読み出す。そして、誤り訂正符号化部１６によって、読み出されたデータに対する符号化が行われ、その結果、各データブロックに対応する誤り訂正符号が生成される。結合部１８において、これらの誤り訂正符号が結合されて、符号化ページデータとなって、出力される。この時、符号化は、通常、全てのデータブロックに対して同時に実行されるが、一つ一つのデータブロックに対して順次符号化を行うこともできる。図１５には、全てのデータブロックに対して同時に符号化を行う場合が示されているが、この例に限定されないことは言うまでもない。

なお、この符号化装置１０によって作成された符号化ページデータが記憶媒体に格納されたり、通信の対象となる。

図１６に本願発明にかかる復号装置の一例のブロックダイアグラムを示す。この復号装置２０は、図１５の符号化装置により作成された符号化ページデータを復号するためのものである。まず、符号分離部２２により、符号化の際に使ったルールに基づいて符号化ページデータをそれを構成する個々の誤り訂正符号に分離する。分離された誤り訂正符号は、バッファ部２４に格納される。なお、バッファ部２４は、条件が合えば、省略することも可能である。次に、バッファ部２４から取り出した、第ｋ誤り訂正符号を復号部２６により復号する。そして、復号されたデータが誤りを含むか否かを誤り検出部２８でチェックする。

もし、第ｋ誤り訂正符号を復号して得られたデータに誤りがあった場合には、置換符号作成部３０により、第ｋ誤り訂正符号との合わせて符号化された部分がある第ｋ＋１誤り訂正符号または第ｋ−１誤り訂正符号あるいはそれらの両方が訂正できるかを誤り検出部２８により判断して、訂正できた誤り訂正符号を利用して第ｋ誤り訂正符号の合わせて符号化された部分を置換して、置換第ｋ誤り訂正符号を作成する。作成された置換第ｋ誤り訂正符号は、バッファ部２４を介してまたは直接に復号部２６に送られる。復号部２６は、置換第ｋ誤り訂正符号を再度復号する。

もし、第ｋ誤り訂正符号を復号して得られたデータに誤りがない場合には、そのデータをページデータ再構成部３２に送って、ここで出力されるページデータが再現される。

Claims

一つのページを構成する符号化する前のデータを該一つのページの一端にある第１データブロックから該一つのページの他端にある第Ｍデータブロックに分割するステップと、ここで、Ｍは３以上の整数であり、
第１データブロックを符号化して第１誤り訂正符号を得るステップと、
第１誤り訂正符号または第１データブロックの一部と第２データブロックを合わせて符号化して第２誤り訂正符号を得るステップと、
第２データブロックに対して行った処理を合わせる誤り訂正符号またはデータブロックを一つずらしながら第３データブロック以降第Ｍ−１データブロックまで行うステップと、
第Ｍ−１誤り訂正符号または第Ｍ−１データブロックの一部と第Ｍデータブロックを合わせて符号化して第Ｍ誤り訂正符号を得るステップと
を含み、第１誤り訂正符号を得るステップから第Ｍ誤り訂正符号を得るステップを順次または同時に行うものである、符号化方法。
一つのページを構成する符号化する前のデータを該一つのページの一端にある第１データブロックから該一つのページの他端にある第Ｍデータブロックに分割するステップと、ここで、Ｍは３以上の整数であり、
第１データブロックと第２データブロックの一部を合わせて符号化して第１誤り訂正符号を得るステップと、
第１誤り訂正符号または第１データブロックの一部と第２データブロックと第３データブロックの一部を合わせて符号化して第２誤り訂正符号を得るステップと、
第２データブロックに対して行った処理を合わせる誤り訂正符号またはデータブロックを一つずらしながら第３データブロック以降第Ｍ−１データブロックまで行うステップと、
第Ｍ−１誤り訂正符号または第Ｍ−１データブロックの一部と第Ｍデータブロックと合わせて符号化して第Ｍ誤り訂正符号を得るステップと
を含み、第１誤り訂正符号を得るステップから第Ｍ誤り訂正符号を得るステップを順次または同時に行うものである、誤り訂正符号化方法。
合わせて符号化される部分が符号化の対象となるデータの大きさに比して小さいデータブロックに対して、そうでないデータブロックに対するより強力な誤り訂正能力を適用することを含む請求項１又は２に記載の誤り訂正符号化方法。
請求項１ないし３のいずれかの誤り訂正符号化方法により符号化された第ｋ誤り訂正符号を復号して、誤りの訂正が可能であったか否かを判断するステップと、
訂正ができなかった場合には、第ｋ誤り訂正符号と合わせて符号化された部分がある第ｋ＋１誤り訂正符号または第ｋ−１誤り訂正符号あるいはそれらの両方が訂正できるかを判断して、訂正できた誤り訂正符号を利用して第ｋ誤り訂正符号の対応する部分を置換するステップと、
置換された第ｋ誤り訂正符号を復号するステップと
を含んでなる誤り訂正復号方法。
一つのページを構成する符号化する前のデータを第１データブロックと第２データブロックの二つのデータブロックに分割するステップと、
第１データブロックを符号化して第１誤り訂正符号を得るステップと、
第１誤り訂正符号または第１データブロックの一部と第２データブロックを合わせて符号化して第２誤り訂正符号を得るステップと
を含んでなる符号化方法。
一つのページを構成する符号化する前のデータを第１データブロックと第２データブロックの二つのデータブロックに分割するステップと、
第１データブロックと第２データブロックの一部を合わせて符号化して第１誤り訂正符号を得るステップと、
第１誤り訂正符号または第１データブロックの一部と第２データブロックを合わせて符号化して第２誤り訂正符号を得るステップと
を含んでなる符号化方法。
請求項５または６のいずれかの誤り訂正符号化方法により符号化された第１誤り訂正符号を復号して、誤りの訂正が可能であったか否かを判断するステップと、
訂正ができなかった場合には、第２誤り訂正符号が訂正できるかを判断して、訂正できた誤り訂正符号を利用して第１誤り訂正符号の一部分を置換するステップと、
第１誤り訂正符号の訂正ができた場合には、第２誤り訂正符号の第１誤り訂正符号と合わせて符号化された部分を置換して、第２誤り訂正符号の復号を行うステップと
を含んでなる誤り訂正復号方法。
一つのページを構成する符号化する前のデータを該一つのページの一端にある第１データブロックから該一つのページの他端にある第Ｍデータブロックに分割するページデータ分割部と、元のデータブロックに、一定のルールに従って、隣接するデータブロックまたは誤り訂正符号の一部のデータを付加して、符号化の対象となるデータを作成する符号化準備部と、作成されたデータに対する符号化を行って各データブロックに対応する誤り訂正符号を生成する誤り訂正符号化部と、生成された誤り訂正符号を結合して、符号化ページデータを作成する結合部とを備える符号化装置。
符号化の際に使ったルールに基づいて符号化ページデータをそれを構成する個々の誤り訂正符号に分離する符号分離部と、分離された誤り訂正符号を復号する復号部と、復号されたデータが誤りを含むか否かをチェックする誤り検出部と、もし、ある誤り訂正符号を復号して得られたデータに誤りがあった場合に、当該誤り訂正符号と合わせて符号化された部分がある１または２の誤り訂正符号が誤りなく訂正できるかを誤り検出部により判断して、誤りなく訂正できた誤り訂正符号を利用して当該誤り訂正符号の部分を置換して、置換誤り訂正符号を作成して、前記バッファに戻す置換符号作成部と、誤りなく訂正されたページデータを出力するページデータ再構成部とを備える復号装置。