(57)【要約】【課題】符号化装置へのデータの入力順に自由度を有する符号化装置を得ること。【解決手段】Ｌ（Ｌは２以上の整数）個のデータブロックで構成される符号化対象データを符号化する符号化装置であって、データブロックに対して符号化処理を行う符号化回路と、符号化処理により生成されたパリティに基づいて、データブロックごとに符号化対象データ内の前記データブロックの位置に応じたパリティを生成するＬ個の位置調整回路と、を備える。【選択図】図９
2013201479.tif 000002
【特許請求の範囲】
【請求項１】
Ｌ（Ｌは２以上の整数）個のデータブロックで構成される符号化対象データを符号化する符号化装置であって、
前記データブロックに対して符号化処理を行う符号化回路と、
前記符号化処理により生成されたパリティに基づいて、前記データブロックごとに前記符号化対象データ内の前記データブロックの位置に応じたパリティを生成するＬ個の位置調整回路と、
を備えることを特徴とする符号化装置。
【請求項２】
前記位置調整回路は、前記符号化対象データ内の対応する前記データブロック以外のビット位置に０を入力する処理を行うことを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記位置調整回路は、前記符号化対象データ内の対応する前記データブロックのビット位置より下位のビット位置に０を入力する処理を行うことを特徴とする請求項１または２に記載の符号化装置。
【請求項４】
前記符号化回路を前記データブロックごとに備え、データブロックごとの前記符号化処理を並列に実施する、ことを特徴とする請求項１、２または３に記載の符号化装置。
【請求項５】
符号化対象データを符号化する符号化装置であって、
前記符号化対象データのうちの指定された位置から指定された長さのデータに対して符号化処理を行う符号化回路と、
前記符号化処理により生成されたパリティに基づいて、前記符号化対象データ内の前記データの位置に応じたパリティを生成する位置調整回路と、
を備えることを特徴とする符号化装置。
【請求項６】
前記符号を誤り訂正符号または誤り検出符号とすることを特徴とする請求項１乃至５のいずれか一項に記載の符号化装置。
【請求項７】
前記符号をＢＣＨ符号とすることを特徴とする請求項５に記載の符号化装置。
【請求項８】
前記符号をリードソロモン符号とすることを特徴とする請求項５に記載の符号化装置。
【請求項９】
前記符号をＣＲＣとすることを特徴とする請求項５に記載の符号化装置。
【請求項１０】
メモリ部と、
前記メモリ部に格納する所定のデータ長のデータを符号化対象データとして符号化処理を行うことにより符号語を生成する符号化部と、
前記メモリ部から読み出された符号語に基づいて復号処理を行う復号化部と、
を備え、
前記符号化部は、
前記符号化対象データを構成するＬ（Ｌは２以上の整数）個のデータブロックに対して符号化処理を行う符号化回路と、
前記符号化処理により生成されたパリティに基づいて、前記データブロックごとに前記符号化対象データ内の前記データブロックの位置に応じたパリティを生成するＬ個の位置調整回路と、
を備えることを特徴とする記憶装置。
【請求項１１】
Ｌ（Ｌは２以上の整数）個のデータブロックで構成される符号化対象データを符号化する符号化装置における符号化方法であって、
前記データブロックに対して符号化処理を行うステップと、
前記符号化処理により生成されたパリティに基づいて、Ｌ個の位置調整回路により前記データブロックごとに前記符号化対象データ内の前記データブロックの位置に応じたパリティを生成するステップと、
を含むことを特徴とする符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、符号化装置、記憶装置および符号化方法に関する。
【背景技術】
【０００２】
従来のＢＣＨ符号化等を行う符号化装置では、復号時の復号化装置への入力順と整合させるため、決められた順番にデータを符号化装置へ入力して符号化する。符号化装置へのデータの入力順番を変更すると、復号化装置のデータの入力順と整合しなくなり復号することができない。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−２１２６２３号公報
【特許文献２】特開２００９−２１１７４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の実施形態は、符号化装置へのデータの入力順に自由度を持たせた符号化装置、記憶装置および符号化方法を提供する。
【課題を解決するための手段】
【０００５】
本願発明の一態様によれば、Ｌ（Ｌは２以上の整数）個のデータブロックで構成される符号化対象データを符号化する符号化装置であって、データブロックに対して符号化処理を行う符号化回路と、符号化処理により生成されたパリティに基づいて、データブロックごとに符号化対象データ内の前記データブロックの位置に応じたパリティを生成するＬ個の位置調整回路と、を備える。
【図面の簡単な説明】
【０００６】
【図１】図１は、第１の実施の形態にかかる符号化装置の構成例を示すブロック図である。
【図２】図２は、符号化対象データが複数のデータブロックで構成される場合のデータ構成例を示す図である。
【図３】図３は、比較例の符号化装置を用いた符号化復号化システムにおけるデータ入力順の一例を示す図である。
【図４】図４は、ＥＣＣ復号化回路へのデータの入力順の一例を示す図である。
【図５】図５は、ＥＣＣ符号化処理回路の構成例を示す図である。
【図６】図６は、位置調整回路の構成例を示す図である。
【図７】図７は、位置調整回路の構成例を示す図である。
【図８】図８は、第２の実施の形態にかかる記憶装置の構成例を示すブロック図である。
【図９】図９は、第２の実施の形態の符号化部の構成例を示す図である。
【図１０】図１０は、第２の実施の形態の符号化処理手順の一例を示す図である。
【図１１】図１１は、位置調整回路の構成例を示す図である。
【図１２】図１２は、位置調整回路の構成例を示す図である。
【図１３】図１３は、位置調整回路の構成例を示す図である。
【図１４】図１４は、位置調整回路の構成例を示す図である。
【図１５】図１５は、中間結果（パリティ＃ｉ´）と出力されるパリティ＃ｉの一例を示す図である。
【図１６】図１６は、入力される情報と０の入力の一例を示す図である。
【図１７】図１７は、図１６の情報が入力された場合の中間結果（パリティ＃ｉ´）と位置調整後のパリティ（パリティ＃ｉ）の具体例を示す図である。
【図１８】図１８は、第３の実施の形態の符号化部の構成例を示す図である。
【発明を実施するための形態】
【０００７】
以下に添付図面を参照して、実施形態にかかる符号化装置、記憶装置および符号化方法を詳細に説明する。なお、これらの実施形態により本発明が限定されるものではない。
【０００８】
図１は、第１の実施の形態にかかる符号化装置の構成例を示すブロック図である。図１に示すように、本実施の形態の符号化装置は、ＥＣＣ（Error  Checking  and  Correction）符号化回路（符号化回路）１と、位置調整回路２と、を備える。
【０００９】
なお、本実施の形態では、符号化装置が生成する符号としてＢＣＨ符号を用いる例を説明するが、符号化装置が生成する符号は、リードソロモン符号（ＲＳ符号）等の他の誤り訂正符号であってもよいし、ＣＲＣ（Cyclic  Redundancy  Check）等の誤り検出符号であってもよく、ＢＣＨ符号に限定されない。
【００１０】
比較例の符号化装置では、復号時の復号化装置への入力順と整合させるため、決められた順番にデータを符号化装置へ入力して符号化する。例えば、１つの符号化対象データが複数のデータブロックで構成される場合、決められた順番にデータブロックを入力する必要がある。このため、データブロックの到着順が符号化装置への入力順と異なる場合、到着したデータブロックをバッファに格納しておき、入力順に並べなおして符号化装置へ入力することになる。このため、バッファが必要となるとともに符号化処理の速度も低下する。
【００１１】
図２は、符号化対象データが複数のデータブロックで構成される場合のデータ構成例を示す図である。図２の例では、符号化対象データは、データブロック＃０からデータブロック＃ＮＢ（ＮＢは１以上の整数）までのＮＢ＋１個のデータブロックで構成される。図２に示す符号化対象データに基づいて符号語を生成する場合、復号時のデータ入力順と一致させるため、一般に、データブロック＃０、データブロック＃１、データブロック＃２、…等のようにあらかじめ定められた順に符号化装置へデータが入力される。あらかじめ定められた順に符号化装置へデータを入力しない場合でも、復号化装置ではあらかじめ定められた順にデータを入力するので、符号化と復号化でデータの入力順が異なることになり正しく復号できない。符号化装置へのデータの入力順を管理して、復号化装置が符号化対象データごとに入力順を変更することも考えられるが、この場合、管理データが膨大となりまた処理速度も低下する。
【００１２】
図３は、比較例の符号化装置を用いた符号化復号化システムにおけるデータ入力順の一例を示す図である。図３は、比較例の符号化装置であるＥＣＣ符号化回路１０１におけるデータ入力順の一例を示す図である。図３では、図の簡略化のためＮＢ＝３とし、符号化対象データがＮＢ＋１個のデータブロックで構成される場合のデータ入力順（データブロック＃０、データブロック＃１、データブロック＃２、データブロック＃３の順）の一例を示している。ＥＣＣ復号化回路１０２では、データとＥＣＣ符号化回路１０１により生成されたパリティとに基づいて復号処理を行う。この際、ＥＣＣ復号化回路１０２に入力されるデータの入力順は、ＥＣＣ符号化回路１０１への入力順と同じである。図４は、ＥＣＣ復号化回路１０２へのデータの入力順の一例を示す図である。図４では、符号化処理において図３で示した入力順でデータが入力された場合の、ＥＣＣ復号化回路１０２へのデータの入力順を示している。
【００１３】
例えば、図２のデータ構成例で、データブロック＃０、データブロック＃１、データブロック＃２、データブロック＃３の順に復号化を行うことが定められている場合に、データブロック＃３がデータブロック＃０、＃１、＃２より先に符号化装置へ到着したとする。
【００１４】
図３に示す比較例の構成例において、データブロック＃３がデータブロック＃１、＃２より先にＥＣＣ符号化回路１０１へ到着したとする。この場合、ＥＣＣ符号化回路１０１は、データブロック＃０、＃１、＃２を入力する前にデータブロック＃３を入力することはできないため、データブロック＃０、＃１、＃２が到着するまでデータブロック＃３を保持しつつ待機することになる。
【００１５】
これに対し、データブロック＃３をデータブロック＃０、＃１、＃２より先に入力して符号化を行うことができれば、データブロック＃３を保持する必要はなく、また符号化処理の開始を待機する必要もない。例えば、符号化対象データ内の任意の位置の一部のデータを用いて符号化処理を行うことができれば、データブロック＃３を先に入力することができ、符号化処理の開始を待機する必要もない。ただし、データブロック＃３を用いて単に符号化処理を行っただけでは、データブロック＃３だけデータ内のビットに対応した符号語が生成されるだけである。したがって、データブロック＃３、データブロック＃０、＃１、データブロック＃２を順に符号化するだけでは、符号化対象データ内のＮＢ＋１個のデータブロックにそれぞれ対応するＮＢ＋１個の符号語ができるだけであり、符号化対象データ全体が符号化されたことを前提として復号するＥＣＣ復号化回路１０２では復号することができない。
【００１６】
任意の位置の一部のデータを用いて符号化処理を行う位置調整機能がない場合、実施方法によって以下の２つの問題が生じる。
（１）ＮＢ＋１個のデータブロックに対してそれぞれ符号化を実施する場合は、ＮＢ＋１個のデータブロックにそれぞれ対応するＮＢ＋１個の符号語ができるだけで、１個に符号語に統合することができない。
（２）ＮＢ＋１個のデータブロックをある決まった順番で（符号化回路へ先に入力されたデータブロックのパリティを中間結果として後ろのデータブロックのパリティ計算の初期値にする）符号化を実施する場合は、ＮＢ＋１個のデータブロックのこの順番だけに対応する1個の符号語ができるから、この順番でＮＢ＋１個のデータブロックを複号化回路に入力しなければならない。逆に、複号化回路へのデータの入力順番が決まったら、符号化回路へのデータ入力の順番も決まってしまう、という依存関係がある。
【００１７】
本実施の形態では、ＥＣＣ符号化回路１が符号化対象データ内の任意位置の一部のデータを用いて符号化処理を行う。そして、符号化対象データ全体が符号化されたことを前提として復号した場合に正しく復号することができるように、位置調整回路２がＥＣＣ符号化回路１による符号化処理で生成されたパリティに対して位置調整を行う。位置調整回路２は、符号化対象データ内の一部のデータを入力として符号化を行う場合に、当該データの符号化対象データ内の位置に応じて符号化処理により生成されたパリティに対してビット位置の調整を行う。これにより、例えば、データブロック＃３、データブロック＃０、データブロック＃１、データブロック＃２というように、復号化処理での入力順と異なる順で符号化処理を行ったとしても、位置調整後の各データブロックのパリティを用いて、決められた順序で符号化対象データ全体が符号化されたことを前提とした復号処理により復号可能なパリティを生成することができる。以降、決められた順序で符号化対象データ全体が符号化されたことを前提とした復号処理を、規定復号処理という。
【００１８】
具体的には、位置調整回路２は、例えば、ＥＣＣ符号化回路１が生成する符号語に対して、符号化対象データ内の実際のデータが存在しない部分に０が入力されたことに相当する処理（以下０パディングという）を実施する。
【００１９】
ここで、上記のような位置調整を行うことにより、規定復号処理により復号可能なパリティを生成することが可能なことを説明する。ここでは、ＥＣＣ符号化回路１が巡回符号を生成するとして説明する。ｋビットの情報（図２の符号化対象データに相当）を（ｄ0，ｄ1，…，ｄk-1）とするとき、ｎビットの巡回符号（ｃ0，ｃ1，…，ｃm-1，ｄ0，ｄ1，…，ｄk-1）を生成するとする。（ｃ0，ｃ1，…，ｃm-1）は検査ビット（パリティ）であり、ｎ＝ｍ＋ｋである。
【００２０】
ｎビットの巡回符号（ｃ0，ｃ1，…，ｃm-1，ｄ0，ｄ1，…，ｄk-1）を作成するには、次の式（１）で表されるように、生成多項式Ｇ（ｘ）による割り算を実施する。Ｐ（ｘ）は、情報ビットに対応する多項式であり、Ｆ（ｘ）は、巡回符号（符号語）に対応する多項式である。
【００２１】
【数１】
2013201479.tif 000003
【００２２】
上記の式（１）に示した割り算を行った余りＲ（ｘ）が、検査ビット（ｃ0，ｃ1，…，ｃm-1）に対応する多項式となる。この検査ビットを情報ビット（ｄ0，ｄ1，…，ｄk-1）に付加することにより、ｎビットの巡回符号（ｃ0，ｃ1，…，ｃm-1，ｄ0，ｄ1，…，ｄk-1）が得られる。
【００２３】
Ｆ（ｘ）、Ｇ（ｘ）、Ｒ（ｘ）は、以下の式（２）で表すことができる。
【００２４】
【数２】
2013201479.tif 000004
【００２５】
すなわち、上記（１）の割り算の商をＱ（ｘ）とするとき、Ｆ（ｘ）は、以下の式（３）で表すことができる。
Ｆ（ｘ）＝Ｇ（ｘ）Ｑ（ｘ）＝ｘn-kＰ（ｘ）＋Ｒ（ｘ）          …（３）
【００２６】
ｋビットの情報ビットをｔ個のデータブロックに分け、０次の項に対応するビット位置から順に１番目のデータブロック、２番目のデータブロック、…とするとき、１番目のデータブロックをｉビット、１番目と２番目のデータブロックの合計のビット数をｊビット、１番目からｔ−１番目までのデータブロックの合計のビット数をｌとする。このとき、Ｐ（ｘ）は、下記の式（４）に示すように各データブロックに対応する多項式Ｐ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）を加算したものとなる。
【００２７】
【数３】
2013201479.tif 000005
【００２８】
上記の式（４）に示すように、各データブロックに対応する多項式Ｐ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）では、各データブロックに対応するビット位置に対応する項では情報に対応する値が乗算されているが、それ以外の項では０が乗算されている。
【００２９】
上記式（３）、（４）により、Ｆ（ｘ）は式（５）で表すことができる。
【００３０】
【数４】
2013201479.tif 000006
【００３１】
Ｐ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）に対する検査ビットの多項式をそれぞれＲ1（ｘ），Ｒ2（ｘ），Ｒ3（ｘ），…，Ｒt（ｘ）とすると、以下に示すとおり、｛Ｒ1（ｘ）＋Ｒ2（ｘ）＋Ｒ3（ｘ）＋…＋Ｒt（ｘ）｝／Ｇ（ｘ）の余りもＲ（ｘ）となる。
【００３２】
Ｑ（ｘ）は、上記（１）の商であり、Ｒ（ｘ）は、上記（１）の余りであるから、以下の式（６）となる。
ｘn-kＰ（ｘ）／Ｇ（ｘ）＝Ｑ（ｘ）＋Ｒ（ｘ）／Ｇ（ｘ）    …（６）
上記式（６）と、上記式（４）より、以下の式（７）、（８）となる。
ｘn-k｛Ｐ1（ｘ）＋Ｐ2（ｘ）＋…＋Ｐt（ｘ）｝／Ｇ（ｘ）
＝Ｑ（ｘ）＋Ｒ（ｘ）／Ｇ（ｘ）    …（７）
ｘn-k｛Ｐ1（ｘ）＋Ｐ2（ｘ）＋…＋Ｐt（ｘ）｝／Ｇ（ｘ）
＝ｘn-kＰ1（ｘ）／Ｇ（ｘ）＋ｘn-kＰ2（ｘ）／Ｇ（ｘ）＋…＋ｘn-kＰt（ｘ）／Ｇ（ｘ）
…（８）
【００３３】
上記式（８）中のｘn-kＰi（ｘ）／Ｇ（ｘ）の商をＱi（ｘ）、余りをＲi（ｘ）とすると、以下の式（９）が成り立つ。
ｘn-kＰi（ｘ）／Ｇ（ｘ）＝Ｑi（ｘ）＋Ｒi（ｘ）／Ｇ（ｘ）    …（９）
【００３４】
以上の式（７）、（８）、（９）より、以下の式（１０）、(11)が導かれる。
Ｑ1（ｘ）＋Ｒ1（ｘ）／Ｇ（ｘ）＋Ｑ2（ｘ）＋Ｒ2（ｘ）／Ｇ（ｘ）＋
…＋Ｑt（ｘ）＋Ｒt（ｘ）／Ｇ（ｘ）＝ｘn-kＰ（ｘ）／Ｇ（ｘ）
＝Ｑ（ｘ）＋Ｒ（ｘ）／Ｇ（ｘ）…（１０）
｛Ｒ1（ｘ）＋Ｒ2（ｘ）＋…＋Ｒt（ｘ）｝／Ｇ（ｘ）
＝Ｑ（ｘ）−Ｑ1（ｘ）−Ｑ1（ｘ）−…−Ｑt（ｘ）＋Ｒ（ｘ）／Ｇ（ｘ）…（１１）
上記式（１１）により、｛Ｒ1（ｘ）＋Ｒ2（ｘ）＋Ｒ3（ｘ）＋…＋Ｒt（ｘ）｝／Ｇ（ｘ）の余りもＲ（ｘ）となる。
【００３５】
Ｒ1（ｘ）＋Ｒ2（ｘ）＋Ｒ3（ｘ）＋…＋Ｒt（ｘ）の最高次数はＲ（ｘ）と同じｍ−１次であるから、Ｒ（ｘ）は、以下の式（１２）に示すようにＲ1（ｘ），Ｒ2（ｘ），Ｒ3（ｘ），…，Ｒt（ｘ）の加算（排他的論理和）となる。
Ｒ1（ｘ）＋Ｒ2（ｘ）＋Ｒ3（ｘ）＋…＋Ｒt（ｘ）＝Ｒ（ｘ）          …（１２）
【００３６】
このように、Ｐ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）に基づいて、Ｒ1（ｘ），Ｒ2（ｘ），Ｒ3（ｘ），…，Ｒt（ｘ）を求めておけば、ｋビットの情報に対応する検査ビットＲ（ｘ）を求めることができる。以上のことから、Ｒ1（ｘ），Ｒ2（ｘ），Ｒ3（ｘ），…，Ｒt（ｘ）の算出順はどのような順でもよいことになる。このため、データブロックの到着順に符号化を行ったり、複数のデータブロックの符号化を並列したりして演算することが可能となる。
【００３７】
本実施の形態では、まず、ＥＣＣ符号化回路１が各データブロックに基づいて各データブロックのデータ長に基づく通常の符号化処理を行い検査ビット（パリティ）を中間結果として求める。そして、位置調整回路２が、中間結果に基づいて、上記式（２）に示したＰ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）に基づいて生成した検査ビットＲ1（ｘ），Ｒ2（ｘ），Ｒ3（ｘ），…，Ｒt（ｘ）に相当する検査ビットを生成する。具体的には、上記式（２）に示したＰ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）において０が乗算されている項に対応するビットに０を入力したことに相当する処理を行う。この処理は、具体的にどのような回路で実現してもよく、実際に０が乗算されている項に対応するビットに０を入力する処理を行ってもよいし、ビットをシフトする処理等により実現してもよい。
【００３８】
なお、Ｐ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）のそれぞれ対応する情報（データ）の一部しか最終的に得られない場合にも本実施の形態の位置調整は適用できる。例えば、図２においてデータブロック＃３のみ到着して、他のデータブロックのデータが到着しない場合等に相当する。この場合も、情報が得られたデータブロックに対応するＰ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）に基づいてＲ1（ｘ），Ｒ2（ｘ），Ｒ3（ｘ），…，Ｒt（ｘ）を生成し、生成したＲ1（ｘ），Ｒ2（ｘ），Ｒ3（ｘ），…，Ｒt（ｘ）を加算することによりＲ（ｘ）を求める（生成したＲ1（ｘ），Ｒ2（ｘ），Ｒ3（ｘ），…，Ｒt（ｘ）が１つの場合はそのまま用いる）。これにより、例えば、データ圧縮等のために、符号化対象データのうち一部のデータブロックのみにデータを格納して送信しても、通常と同様に規定復号処理により復号することができる。
【００３９】
図５は、ＥＣＣ符号化処理回路１の構成例を示す図である。図５は、生成多項式Ｇ（ｘ）＝ｘ3＋ｘ＋１を用いる場合のＥＣＣ符号化処理回路１の構成例を示している。図５に示すように、ＥＣＣ符号化処理回路１は、レジスタ（Ｒ）１１，１２，１３と、加算器１４，１８，１９と、ゲート１５，１６，１７と、を備える。なお、図５は一例であり、ＥＣＣ符号化処理回路１の構成および生成多項式は図５の例に限定されない。
【００４０】
図６、７は、位置調整回路２の構成例を示す図である。上述したＰ1（ｘ），Ｐ2（ｘ），Ｐ3（ｘ），…，Ｐt（ｘ）では、実際の情報が存在するビット位置より高次数のビット（例えば、Ｐ2（ｘ）ではｘj+1からｘk-1までの項に対応するビット）と、実際の情報が存在するビット位置より低次数のビット（例えば、Ｐ2（ｘ）ではｘ0からｘi-1までの項に対応するビット）を０としているが、実際の情報が存在するビット位置より高次数のビットについては、０を入力してもしなくても結果は同じである。したがって、図６、７の構成例では、実際の情報が存在するビット位置より高次数のビットに０を入力する構成を示している。なお、図６では、パリティが３ビットの例を示している。
【００４１】
図６の構成例では、位置調整回路２は、セレクタ４、ＸＯＲゲート５およびＦＦ（FlipFlop）６を備える。位置調整回路２は、内部または外部の制御部３により、調整するビット数（実際の情報が存在するビット位置より高次数で０を入力するビット数）に応じて繰り返し回数（１、２または３回）が制御される。セレクタ４は、制御部３からの制御により、入力された中間結果（ＥＣＣ符号化処理回路１により生成されたパリティ）とＦＦ６の出力とのいずれか一方を選択して出力する。１回目では、セレクタ４は入力された中間結果を選択し、これにより１ビット０を入力することになる。２回目および３回目ではセレクタ４はＦＦ６の出力を選択する。これにより、繰り返し２回では２ビット、繰り返し３回では３ビット０を入力することができる。このように、繰り返し回数に応じて調整するビット数を変更することができる。
【００４２】
図７の構成例では、例えば、図６のようにｓビット（図６の場合は３ビット）の０入力が可能であるｓビット位置調整回路８と、セレクタ７と、ＦＦ９と、を備える。そして、制御部３は、ｓビット位置調整回路８に対してはｓビット０入力をするよう制御すると、セレクタ７の選択に応じてｓビット、２ｓビット、３ｓビット、…のようにｓビット単位で０の入力を実施することができる。セレクタ７は、１回目の繰り返しでは入力された中間結果を選択し、これによりｓビット０を入力することになる。２回目および３回目ではセレクタ７はＦＦ９の出力を選択する。これにより、繰り返し２回では２ｓビット、繰り返し３回では３ｓビット０を入力することができる。なお、図６、７は一例であり、位置調整回路２の構成はこれらに限定されない。
【００４３】
以上のように、本実施の形態では、符号化対象データ内の一部のデータを用いて符号化処理を行うＥＣＣ符号化処理回路１と、ＥＣＣ符号化処理回路１により生成されたパリティに基づいてビット位置の調整を行ったパリティを生成する位置調整回路２とを備えるようにした。これにより、ビット位置の調整を行ったパリティを用いて、符号化対象データ全体が符号化されたことを前提とした復号を行うことが可能となる。このため、符号化装置へのデータの入力順に自由度を持たせることができ、演算速度の向上やバッファの削減などを図ることができる。
【００４４】
（第２の実施の形態）
図８は、第２の実施の形態にかかる記憶装置２１の構成例を示すブロック図である。図８に示すように、記憶装置２１は、メモリコントローラ２２、半導体メモリ部２３を備える。記憶装置２１は、通信インタフェースを介してホスト２４に接続され、ホスト２４に対する外部記憶媒体として機能する。ホスト２４の例としては、パーソナルコンピュータやＣＰＵ（Central  Processing  Unit）コア等があげられる。
【００４５】
半導体メモリ部２３は、例えばＮＡＮＤ型フラッシュメモリ等の不揮発性半導体メモリにより構成されるが、ＮＡＮＤフラッシュメモリ以外のメモリであってもよい。
【００４６】
メモリコントローラ２２は、内部バス３０と、ＨｏｓｔＩ／Ｆ（インタフェース）３１と、メモリＩ／Ｆ（メモリインタフェース）３２と、制御部３３と、符号化／復号化処理部３４と、ＲＡＭ（Random  Access  Memory）３７と、で構成される。符号化／復号化処理部３４は、符号化部（符号化装置）３５と、復号化部（復号化装置）３６と、で構成される。
【００４７】
ＨｏｓｔＩ／Ｆ３１は、ホスト２４から受信した命令、データなどを内部バス３０に出力する。また、ＨｏｓｔＩ／Ｆ３１は、内部バス３０経由で入力されたデータ、制御部３３からの応答通知（命令の実行完了を示す通知など）などをホスト２４へ送信する。
【００４８】
制御部３３は、半導体記憶装置２１の各構成要素を統括的に制御する制御部であり、ＣＰＵコア、ＲＡＭ、ＲＯＭ（Read  Only  Memory）、ＤＭＡ（Direct  Memory  Access）コントローラなどで構成される。制御部３３は、ホスト２４からＨｏｓｔＩ／Ｆ３１および内部バス３０経由で命令を受けた場合に、その命令に従った制御を行う。例えば、制御部３３は、ホスト４からの命令に従って、半導体メモリ部２３へのデータの書き込み、半導体メモリ部２３からの読み出しなどをメモリＩ／Ｆ３２へ指示する。また、制御部３３は、半導体メモリ部２３へ書き込む際に書き込みデータに対して符号化処理を実施するよう符号化部３５を制御し、半導体メモリ部２３からの読み出された符号語に基づいて復号化処理を実施するよう復号化部３６を制御する。ＲＡＭ３７は、ホストから受信したデータやホストへ送信するデータを一時的に保持する。
【００４９】
本実施の形態では、ホスト２４から受信するデータを符号化して半導体メモリ部２３へ書き込むこととし、符号化対象データが第１の実施の形態の図２で示したようにＮＢ＋１個のデータブロックで構成されているとする。復号化部３６は、符号化対象データ単位であらかじめ決められたデータブロックの入力順で入力されることを前提に復号化処理を行う。
【００５０】
ホスト２４から受信したデータは、ＲＡＭ３７に一時的に格納される。制御部３３は、ホスト２４から受信したデータ（以下、ホストデータという）について、論理アドレスと半導体メモリ部２３上のアドレスとの対応を管理しており、どのホストデータで符号化対象データを構成するかを決定する。また、制御部３３は、符号化対象データ内のデータブロックの識別番号（例えば、データブロック＃ｉ（ｉ＝１，２，…，ＮＢ）のデータブロックの番号をｉとする）がＲＡＭ３７に格納されたかを管理している。制御部３３は、ＲＡＭ３７に格納されたデータブロックの番号に応じて符号化部３５を制御する。
【００５１】
あらかじめ決められたデータブロックの入力順で復号処理を行う場合でも、符号化部３５として第１の実施の形態で述べた符号化装置を用いると、データブロックの入力順を自由に設定することができる。例えば、図１に示した符号化装置により、データブロックを任意の順に処理し、各データブロックの位置調整後のパリティを保持しておき、符号化対象データ分のＮＢ＋１個の位置調整後のパリティが生成できた時点でパリティの排他的論理和をとることにより、最終的なパリティを生成することができる。一方、第１の実施の形態では、符号化対象データの情報が存在するビットの位置を固定せずに変更できるように構成しているが、図２のようにデータブロックの区切りがあらかじめわかっている場合、各々のデータブロックに対応した位置調整回路をそれぞれ備えることで処理の高速化を図ることができる。本実施の形態では、データブロックごとに位置調整回路を備える例を説明する。
【００５２】
図９は、本実施の形態の符号化部３５の構成例を示す図である。本実施の形態の符号化部３５は、図９に示すように、セレクタ４１と、ＥＣＣ符号化回路１と、位置調整回路２−１〜２−Ｌ（Ｌ＝ＮＢ＋１）と、加算器４３と、を備える。ＥＣＣ符号化回路１は、第１の実施の形態のＥＣＣ符号化回路１と同様である。位置調整回路２−１〜２−Ｌは、それぞれ第１の位置調整回路２と同様であるが、０を入力するビット数が変更可能でなくともよく、固定の個数の０を入力する構成としてもよい。図９の構成例では、Ｌ＝ＮＢ＋２とし、位置調整回路２−１がデータブロック＃０に対応し、位置調整回路２−２がデータブロック＃１に対応し、・・・、位置調整回路２−Ｌがデータブロック＃（ＬＢ＋１）に対応している。したがって、例えば、位置調整回路２−１はデータブロック＃０に対応するビット位置の調整を行うことができればよく、位置調整回路２−２はデータブロック＃１に対応するビット位置の調整を行うことができればよい。
【００５３】
次に、本実施の形態の符号化処理について説明する。図１０は、本実施の形態の符号化処理手順の一例を示す図である。図１０は、１つの符号化対象データのパリティを生成する処理を示している。まず、制御部３３は、ＨｏｓｔＩ／Ｆ３１経由でホスト２４から書込み要求を受信した場合に、書込み対象のホストデータのアドレスに基づいて符号化対象データを構成するデータのアドレスの割当てを行う。
【００５４】
例えば、ホストからの送信が所定の第１のデータ単位で行われるとし、所定のデータ単位がさらに複数の第２のデータ単位で構成され、実際のデータの転送は第２のデータ単位で行われるとする。そして、第１のデータ単位ごとにホスト２４からのデータの転送が管理され、第１のデータ単位間ではホスト２４から送信された順にＲＡＭ３７へ到着するとし、第１のデータ単位内では、第２のデータ単位間でＲＡＭ３７への到着順は送信順となることを保証されていないとする。例えば、ホスト２４からホストデータ＃１、ホストデータ＃２、ホストデータ＃３の３つの第１のデータ単位のホストデータが、ホストデータ＃１、ホストデータ＃２、ホストデータ＃３の順で送信された場合、ＲＡＭ３７への到着順はホストデータ＃１、ホストデータ＃２、ホストデータ＃３であるとする。一方、例えば、ホストデータ＃１が５個の第２のデータ単位であるホストデータ＃１−１〜ホストデータ＃１−５で構成され、ホストからホストデータ＃１−１，ホストデータ＃１−２，…，ホストデータ＃１−５の順で送信される場合、ホストデータ＃１−３がホストデータ＃１−１より先に到着するような到着順の変更が有り得るとする。
【００５５】
なお、ここでは、第１のデータ単位での到着順の変更はないとしたが、第１のデータ単位での到着順の変更がある場合にも、ＲＡＭ３７に複数の第１のデータ単位を格納できる容量があれば同様の符号化処理を実施可能である。
【００５６】
また、ここでは、簡単のために、第１のデータ単位を図２の符号化対象データとし、第２のデータ単位を図２のデータブロックとする。第１のデータ単位と符号化対象データは異なっていてもよく、例えば、複数の第１のデータ単位で符号化対象データを構成してもよい。例えば、符号化対象データが２つの第１のデータ単位で構成され、第１のデータ単位が５つの第２のデータ単位（＝データブロックとする）で構成される場合、符号化対象データは１０個のデータブロックで構成される。この場合の動作は、１つの第１のデータ単位が符号化対象データを構成する場合とデータブロック数が異なるだけで同様である。また、データブロックの到着の管理が複雑になるが、第２のデータ単位とデータブロックが異なっていてもよい。
【００５７】
図１０の説明に戻る。制御部３３は、データブロック（＝第１のデータ単位）を受信した（ＲＡＭ３７にデータブロックが格納された）ことを認識する（ステップＳ１）と、当該データブロックのデータブロック番号を把握する。データブロック番号は、ＨｏｓｔＩ／Ｆ３１がホストデータに格納されているデータブロック番号を識別するための識別情報（データのアドレス等）を参照して制御部３３へ通知してもよいし、制御部３３が直接ホストデータの識別情報を抽出してデータブロック番号を把握してもよい。
【００５８】
制御部３３は、受信済のデータブロック番号に基づいて、符号化処理対象のデータブロックを選択して符号化部３５へデータブロックの選択信号を送信するとともに符号化処理の開始を指示し、ＥＣＣ符号化回路１による符号化処理が実施される（ステップＳ３）。この際、セレクタ４１は、制御部３３からの選択信号に基づいて入力するデータブロックを選択してＥＣＣ符号化回路１へ入力し、セレクタ４２は、ＥＣＣ符号化回路１により生成されたパリティ（中間結果）を選択信号に基づいて選択した位置調整回路（位置調整回路２−１〜２−Ｌのうちのいずれか１つ）に出力する。以下、データブロック＃ｉに対応する中間結果であるパリティをパリティ＃ｉ´と表記する。
【００５９】
パリティ＃ｉ´が入力された位置調整回路２−ｉは、データブロック＃ｉの符号化対象データ内の位置に基づいて、第１の実施の形態で述べた位置調整を実施してパリティ＃ｉを生成する（ステップＳ４）。その後、制御部３３は、符号化対象データ内の全データブロックを処理済（パリティを生成済）であるか否かを判断し（ステップＳ５）、処理済でない場合（ステップＳ５  Ｎｏ）は、ステップＳ２に戻る。
【００６０】
符号化対象データ内の全データブロックを処理済の場合（ステップＳ５  Ｙｅｓ）、
加算器４３が、パリティ＃０〜＃Ｌの排他的論理和を当該符号化対象データのパリティＰとして算出し（ステップＳ６）、処理を終了する。
【００６１】
パリティＰは、符号化対象データとともに半導体メモリ部２３へ書き込まれる。半導体メモリ部２３からの読み出し時には、符号化対象データとパリティＰとが読み出され、復号化部３６により復号化され、復号化後のデータがホスト２４へ送信される。
【００６２】
なお、ここでは、符号化対象データの全てのデータブロックが揃ってからパリティＰを求めるようにしたが、符号化対象データの一部のデータブロックしか到着しないことが分かっている場合には、一部のデータブロックについての位置調整後のパリティの排他的論理和を算出することでパリティＰを求めるようにしてもよい。また、例えば、符号化対象の最後のデータブロックを受信してから所定の時間が経過しても符号化対象データの全てのデータブロックが揃わない場合、未受信のデータブロックは途中で失われたものと判断して、受信済のデータブロックを用いてパリティＰを求めるようにしてもよい。
【００６３】
位置調整回路２−１〜２−Ｌの構成例について説明する。ここでは、一例として、データブロックのサイズを１ビットとし、ＮＢ＝３（１つの符号化対象データを構成するデータブロック数は４）とし、Ｌ＝４として４つの位置調整回路を備える例を説明する。また、パリティは３ビットとし、ＥＣＣ符号化生成回路１により生成されたパリティ（中間結果）の各ビットの値をそれぞれｒ［０］、ｒ［１］、ｒ［２］とする。
【００６４】
図１１〜１４は、位置調整回路２−１〜２−４の構成例を示す図である。図１１は、位置調整回路２−１の構成例を示し、図１２は、位置調整回路２−２の構成例を示し、図１３は、位置調整回路２−３の構成例を示し、図１４は、位置調整回路２−４の構成例を示している。また、図１５は、図１１〜１４の構成を前提とした場合に入力される中間結果（パリティ＃ｉ´）と出力されるパリティ＃ｉの一例を示す図である。
【００６５】
符号化対象データを（ｄ３  ｄ２  ｄ３  ｄ０）とするとき、各データブロックでは、以下のように０入力を行うことにより位置調整を行う。
（１）データブロック＃０  （                  ｄ０）
（２）データブロック＃１  （            ｄ１    ０）
（３）データブロック＃２  （      ｄ２    ０    ０）
（４）データブロック＃３  （ｄ３    ０    ０    ０）
【００６６】
データブロック＃０に対応する位置調整回路２−１は、図１１に示すように、０の入力を行う必要がないため、ｒ［０］、ｒ［１］、ｒ［２］をそのまま出力する。図１２に示すように、データブロック＃１に対応する位置調整回路２−２は、ＸＯＲゲート５を備える。位置調整回路２−２は、１つの０を入力する処理として、出力ビット＃０（位置調整を行わない場合のｒ［０］の出力に対応）としてｒ［２］を出力し、出力ビット＃１（位置調整を行わない場合のｒ［１］の出力に対応）ｒ［０］＾ｒ［２］を出力し、出力ビット＃２（位置調整を行わない場合のｒ［２］の出力に対応）としてｒ［０］を出力する。なお、＾は排他的論理和の演算を示す。
【００６７】
図１３に示すように、データブロック＃２に対応する位置調整回路２−３は、ＸＯＲゲート５−１，５−２を備える。位置調整回路２−３は、２つの０を入力する処理として、出力ビット＃０としてｒ［１］を出力し、出力ビット＃１としてｒ［２］＾ｒ［１］を出力し、出力ビット＃２ｒ［１］を出力する。
【００６８】
図１４に示すように、データブロック＃３に対応する位置調整回路２−４は、ＸＯＲゲート５−１，５−２，５−３を備える。位置調整回路２−４は、３つの０を入力する処理として、出力ビット＃０としてｒ［０］＾ｒ［２］を出力し、出力ビット＃１としてｒ［０］＾ｒ［２］＾ｒ［１］を出力し、出力ビット＃２としてｒ［２］＾ｒ［１］を出力する。
【００６９】
図１６は、入力される情報と０の入力の一例を示す図である。図１７は、図１６の情報が入力された場合の中間結果（パリティ＃ｉ´）と位置調整後のパリティ（パリティ＃ｉ）の具体例を示す図である。図１６の右欄に示すように情報を１１０１（ｄ３＝１：ｄ２＝１：ｄ１＝０：ｄ０＝１）とすると、図１６の左欄に示すように、データブロックに応じて０を入力する。
【００７０】
図１７に示すように、データブロック＃０については、ＥＣＣ符号化回路１により生成されるパリティ＃（Ｐａｒｉｔｙ）０´は、｛ｒ［２］，ｒ［１］，ｒ［０］｝＝｛０，１，１｝となる。データブロック＃１については、ＥＣＣ符号化回路１により生成されるパリティ＃１´は、｛ｒ［２］，ｒ［１］，ｒ［０］｝＝｛０，１，１｝となる。データブロック＃２については、ＥＣＣ符号化回路１により生成されるパリティ＃２´は、｛ｒ［２］，ｒ［１］，ｒ［０］｝＝｛０，０，０｝となる。データブロック＃３については、ＥＣＣ符号化回路１により生成されるパリティ＃３´は、｛ｒ［２］，ｒ［１］，ｒ［０］｝＝｛０，１，１｝となる。
【００７１】
また、図１５を用いて説明した処理により、パリティ＃０は｛１，０，０｝となり、パリティ＃１は｛１，１，１｝となり、パリティ＃２は｛０，０，０｝となり、パリティ＃３は｛０，１，１｝となる。そして、最終的に得られるパリティＰは、｛０，０，１｝となる。したがって、情報１１０１に対するパリティＰは、００１となり、符号語は１１０１００１となる。
【００７２】
なお、ここでは、各データブロックサイズが等しい例を説明したが、各データブロックのデータサイズは異なっていてもよい。
【００７３】
以上のように、本実施の形態では、データブロックごとに位置調整回路を備え、位置調整処理を並列に実施できるようにした。このため、符号化対象データ内のうち符号化を開始する位置をデータブロック単位で任意に設定できるとともに、位置調整回路の構成を簡易化することができる。また、データブロックの到着順が所定の順序と異なる場合にも、到着順に符号化処理を実施することができ、バッファ量を削減できるとともに処理速度を向上させることができる。
【００７４】
（第３の実施の形態）
図１８は、第３の実施の形態の符号化部３５ａの構成例を示す図である。本実施の形態の符号化部３５ａは、第２の実施の形態で述べた記憶装置２１において符号化部３５ａの替わりに用いられる。第２の実施の形態と同様の機能を有する構成要素は、第２の実施の形態と同一の符号を用いて重複する説明を省略する。
【００７５】
符号化部３５ａは、第２の実施の形態の符号化２５からセレクタ４１，４２を削除し、ＥＣＣ符号化回路１の替わりにＥＣＣ符号化回路１−１〜１−Ｌを備える以外は第２の実施の形態の符号化部３５と同様である。第２の実施の形態では、ＥＣＣ符号化回路１を各データブロックで共有したが、本実施の形態では、データブロックと同じ数のＥＣＣ符号化回路１−１〜１−Ｌを備え、データブロックごとに異なるＥＣＣ符号化回路で符号化処理を実施する。これにより、符号化処理を並列して行うことができ、第２の実施の形態に比べ、処理速度を向上させることができる。以上述べたように、本実施の形態の動作は、第２の実施の形態と同様である。
【００７６】
例えば、各データブロックのデータサイズが同じの場合、符号化処理の時間は、比較例の符号化装置の１／Ｌである。このように、本実施の形態では、第２の実施の形態と同様の効果が得られるとともに、符号化処理を並列化することができ、符号化処理速度を向上させることができる。
【００７７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７８】
１，１−１〜１−Ｌ  ＥＣＣ符号化回路、２，２−１〜２−Ｌ  位置調整回路、３，３３  制御部、記憶装置２１、半導体メモリ部２３、３４  符号化／復号化部、３５  符号化部、３６  復号化部、４１，４２  セレクタ、４３  加算器。
【図１】
2013201479.tif 000007
【図２】
2013201479.tif 000008
【図３】
2013201479.tif 000009
【図４】
2013201479.tif 000010
【図５】
2013201479.tif 000011
【図６】
2013201479.tif 000012
【図７】
2013201479.tif 000013
【図８】
2013201479.tif 000014
【図９】
2013201479.tif 000015
【図１０】
2013201479.tif 000016
【図１１】
2013201479.tif 000017
【図１２】
2013201479.tif 000018
【図１３】
2013201479.tif 000019
【図１４】
2013201479.tif 000020
【図１５】
2013201479.tif 000021
【図１６】
2013201479.tif 000022
【図１７】
2013201479.tif 000023
【図１８】
2013201479.tif 000024