(57)【要約】【課題】除算回路において記憶部の容量を削減する。【解決手段】多項式選択部が、それぞれが共通因数および部分多項式からなる複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する。指定部が、入力多項式が選択されるたびに前記選択された入力多項式内の共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する。多項式乗算部が、指定された第１因数に対応する第１の剰余と指定された第２因数に対応する第２の剰余とを入力多項式が選択されるたびに取得して第１および第２の剰余のそれぞれと供給された部分多項式とを乗算して乗算結果を供給する。多項式加算部が、供給された乗算結果の全てを加算して加算結果を供給する。多項式除算部が、加算結果に対して所定の除算を行って除算結果を出力する。【選択図】図６
2016004468.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが共通因数および部分多項式からなる複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、
前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、
前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、
前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、
前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、
前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、
前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部と
を具備する除算回路。
【請求項２】
前記多項式加算部は、前記供給された乗算結果の全てを加算した結果を２つの分離多項式に分離して当該２つの分離多項式の一方における共通因数に対する前記所定の除算により生じる剰余と前記一方における部分多項式とを乗算した結果に前記２つの分離多項式の他方を加算した結果を前記加算結果として供給する
請求項１記載の除算回路。
【請求項３】
前記第１因数および前記第２因数と異なる複数の第３因数のそれぞれについて前記第３因数に対する前記所定の除算により生じる剰余を第３の剰余として保持する第３剰余テーブルをさらに具備し、
前記指定部は、前記因数分解により生成される前記複数の第３の因数のいずれかをさらに指定し、
前記多項式乗算部は、前記指定された第３因数に対応する前記第３の剰余を前記第３の剰余テーブルからさらに取得して前記第１および第２の剰余とのそれぞれと前記供給された部分多項式とを乗算した結果にさらに前記第３の剰余を乗算する
請求項１記載の除算回路。
【請求項４】
各々が複数の第３因数からなる複数の第３因数群のそれぞれについて前記第３因数に対する前記所定の除算により生じる剰余を第３の剰余として保持する複数の第３剰余テーブルをさらに具備し、
前記指定部は、前記因数分解により生成される前記第３の因数を前記複数の第３因数群のそれぞれについてさらに指定し、
前記多項式乗算部は、前記指定された第３因数ごとに当該第３因数に対応する前記第３の剰余を前記第３の剰余テーブルからさらに取得して前記第１および第２の剰余とのそれぞれと前記供給された部分多項式とを乗算した結果にさらに前記第３の剰余の各々を乗算する
請求項１記載の除算回路。
【請求項５】
前記指定部は、前記共通因数の次数に応じた数値を所定の除数により除した商および余りを求め当該商に応じた次数の単項式と前記余りに応じた次数の単項式との一方を前記第１因数とし、他方を前記第２因数として指定する
請求項１記載の除算回路。
【請求項６】
前記入力多項式を選択した順番を示すインデックスと前記共通因数の次数との関係を示す所定の関数を使用して前記インデックスを前記次数に置き換えて前記指定部に供給するマッピング部をさらに具備し、
前記多項式選択部は、前記インデックスを生成して前記マッピング部に供給し、
前記指定部は、前記供給された次数の前記共通因数に対する因数分解により生成される前記複数の第１因数のいずれかと前記複数の第２因数のいずれかとを指定する
請求項１記載の除算回路。
【請求項７】
前記入力多項式が選択されるたびに計数値を計数するカウンタをさらに具備し、
前記指定部は、前記計数値に応じた次数の前記共通因数に対する因数分解により生成される前記第１因数および第２因数を指定する
請求項１記載の除算回路。
【請求項８】
それぞれが共通因数および部分多項式からなる複数の入力多項式を示すデータを保持するデータバッファと、
前記複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、
前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、
前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、
前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、
前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、
前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、
前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部と、
前記データと前記除算結果を示すパリティとを含む符号語を生成して出力する符号語生成部と
を具備する符号化装置。
【請求項９】
それぞれが共通因数および部分多項式からなる複数の入力多項式を示すデータとパリティとを含む受信語を保持するデータバッファと、
前記複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、
前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、
前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、
前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、
前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、
前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、
前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部と、
前記除算結果を示すビット列が前記パリティと一致するか否かにより前記受信語における誤りの有無を検出する誤り検出部と
を具備する復号装置。
【請求項１０】
多項式選択部が、それぞれが共通因数および部分多項式からなる複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択手順と、
指定部が、前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定手順と、
多項式乗算部が、前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルとから前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記入力多項式が選択されるたびに取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算手順と、
多項式加算部が、前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算手順と、
多項式除算部が、前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算手順と
を具備する除算回路の制御方法。
【請求項１１】
多項式選択部が、それぞれが共通因数および部分多項式からなる複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択手順と、
指定部が、前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定手順と、
多項式乗算部が、前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルとから前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記入力多項式が選択されるたびに取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算手順と、
多項式加算部が、前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算手順と、
多項式除算部が、前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算手順と
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、除算回路、符号化装置、復号装置、および、これらにおける処理方法ならびに当該方法をコンピュータに実行させるプログラムに関する。詳しくは、多項式を除算する除算回路、符号化装置、復号装置、および、これらにおける処理方法ならびに当該方法をコンピュータに実行させるプログラムに関する。
【背景技術】
【０００２】
従来より情報処理装置においては、データの符号化や復号などにおいて多項式を除算する処理が行われている。例えば、巡回符号に符号化する際には、データを多項式表現した被除多項式が生成多項式により除算され、この除算により生じた剰余を示すビット列がパリティとしてデータに付加される。また、復号においても被除多項式の除算が行われ、算出された剰余の示すビット列がパリティと一致するか否かにより誤りの有無が判定される。
【０００３】
このような多項式の除算においては、一般に、シフトレジスタが用いられ、このシフトレジスタによりデータ内のビットが１ビットずつ順に処理される。このため、被除多項式の次数が多いほど（すなわち、データサイズが大きいほど）、除算器の遅延時間が大きくなる。
【０００４】
そこで、除算器における遅延時間を低減するために、被除多項式を複数の多項式に分割して処理する除算装置が提案されている（例えば、特許文献１参照。）。この除算装置において、被除多項式は、Ｍ（Ｍは２以上の整数）個の多項式Ａｋ（ｘ）ｘｎｋに分割されて順に入力される。ここで、ｋは０乃至（Ｍ−１）の整数であり、ｎは、各多項式の項の個数である。除算装置は、多項式Ａｋ（ｘ）ｘｎｋの共通因数ｘｎｋを生成多項式により除した剰余を予めテーブルに保持しておき、Ａｋ（ｘ）を順に選択し、そのＡｋ（ｘ）に対応する剰余をテーブルから読み出して、Ａｋ（ｘ）に乗算する。除算装置は、入力多項式ごとの乗算結果の合計を生成多項式により除算して、その剰余を示すビット列をパリティとして求める。これにより、除算対象の多項式の次数が小さくなるため、遅延時間を短くすることができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−１６０６６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述の従来技術では、データサイズが大きくなるほど、テーブルのエントリ数や、各剰余の次数が大きくなり、テーブルを格納する記憶部の容量が増大してしまうという問題がある。
【０００７】
本技術はこのような状況に鑑みて生み出されたものであり、除算回路において記憶部の容量を削減することを目的とする。
【課題を解決するための手段】
【０００８】
本技術は、上述の問題点を解消するためになされたものであり、その第１の側面は、それぞれが共通因数および部分多項式からなる複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部とを具備する除算回路、および、その制御方法、ならびに当該方法をコンピュータに実行させるためのプログラムである。これにより、共通因数を分解した第１因数および第２因数に対応する第１および第２の剰余と部分多項式との乗算結果の全ての加算結果に対する除算が行われるという作用をもたらす。
【０００９】
また、この第１の側面において、上記多項式加算部は、上記供給された乗算結果の全てを加算した結果を２つの分離多項式に分離して当該２つの分離多項式の一方における共通因数に対する上記所定の除算により生じる剰余と上記一方における部分多項式とを乗算した結果に上記２つの分離多項式の他方を加算した結果を上記加算結果として供給してもよい。これにより、乗算結果の全てを加算した結果が２つの分離多項式に分離されるという作用をもたらす。
【００１０】
また、この第１の側面において、前記第１因数および前記第２因数と異なる複数の第３因数のそれぞれについて前記第３因数に対する前記所定の除算により生じる剰余を第３の剰余として保持する第３剰余テーブルをさらに具備し、前記指定部は、前記複数の第３の因数のいずれかをさらに指定し、前記多項式乗算部は、前記指定された第３因数に対応する前記第３の剰余を前記第３の剰余テーブルからさらに取得して前記第１および第２の剰余とのそれぞれと前記供給された部分多項式とを乗算した結果にさらに前記第３の剰余を乗算してもよい。これにより、共通因数を分解した第１因数、第２因数および第３因数に対応する第１、第２および第３の剰余と部分多項式との乗算結果の全ての加算結果に対する除算が行われるという作用をもたらす。
【００１１】
また、この第１の側面において、各々が複数の第３因数からなる複数の第３因数群のそれぞれについて前記第３因数に対する前記所定の除算により生じる剰余を第３の剰余として保持する複数の第３剰余テーブルをさらに具備し、前記指定部は、前記因数分解により生成される前記第３の因数を前記複数の第３因数群のそれぞれについてさらに指定し、前記多項式乗算部は、前記指定された第３因数ごとに当該第３因数に対応する前記第３の剰余を前記第３の剰余テーブルからさらに取得して前記第１および第２の剰余とのそれぞれと前記供給された部分多項式とを乗算した結果にさらに前記第３の剰余の各々を乗算してもよい。これにより、これにより、共通因数を分解した第１因数、第２因数および第３因数に対応する第１の剰余と、第２の剰余と、第３の剰余のそれぞれと部分多項式との乗算結果の全ての加算結果に対する除算が行われるという作用をもたらす。
【００１２】
また、この第１の側面において、上記指定部は、上記共通因数の次数に応じた数値を所定の除数により除した商および余りを求め当該商に応じた次数の単項式と上記余りに応じた次数の単項式との一方を上記第１因数とし、他方を上記第２因数として指定してもよい。これにより、共通因数の次数に応じた数値を所定の除数により除した余りおよび商のうち余りに応じた次数の単項式と商に応じた次数の単項式の一方が第１因数として、他方が第２因数として指定されるという作用をもたらす。
【００１３】
また、この第１の側面において、前記入力多項式を選択した順番を示すインデックスと前記共通因数の次数との関係を示す所定の関数を使用して前記インデックスを前記次数に置き換えて前記指定部に供給するマッピング部をさらに具備し、前記多項式選択部は、前記インデックスを生成して前記マッピング部に供給し、前記指定部は、前記供給された次数の前記共通因数に対する因数分解により生成される前記複数の第１因数のいずれかと前記複数の第２因数のいずれかとを指定してもよい。これにより、インデックスが次数に置き換えられるという作用をもたらす。
【００１４】
また、この第１の側面において、前記入力多項式が選択されるたびに計数値を計数するカウンタをさらに具備し、前記指定部は、前記計数値に応じた次数の前記共通因数に対する因数分解により生成される前記第１因数および第２因数を指定してもよい。これにより、計数値に応じた次数の共通因数に対する因数分解により生成される第１因数および第２因数が指定されるという作用をもたらす。
【００１５】
また、本技術の第２の側面は、それぞれが共通因数および部分多項式からなる複数の入力多項式を示すデータを保持するデータバッファと、前記複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部と、前記データと前記除算結果を示すパリティとを含む符号語を生成して出力する符号語生成部とを具備する符号化装置である。これにより、共通因数を分解した第１因数および第２因数に対応する第１および第２の剰余と部分多項式との乗算結果の全ての加算結果に対する除算が行われるという作用をもたらす。
【００１６】
また、本技術の第３の側面は、それぞれが共通因数および部分多項式からなる複数の入力多項式を示すデータとパリティとを含む受信語を保持するデータバッファと、前記複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部と、前記除算結果を示すビット列が前記パリティと一致するか否かにより前記受信語における誤りの有無を検出する誤り検出部とを具備する復号装置である。これにより、共通因数を分解した第１因数および第２因数に対応する第１および第２の剰余と部分多項式との乗算結果の全ての加算結果に対する除算が行われるという作用をもたらす。
【発明の効果】
【００１７】
本技術によれば、除算回路において記憶部の容量を削減することができるという優れた効果を奏し得る。なお、ここに記載された効果は必ずしも限定されるものではなく、本開示中に記載されたいずれかの効果であってもよい。
【図面の簡単な説明】
【００１８】
【図１】第１の実施の形態における情報処理システムの一構成例を示すブロック図である。
【図２】第１の実施の形態におけるホストコンピュータの一構成例を示すブロック図である。
【図３】第１の実施の形態におけるメモリコントローラの一構成例を示すブロック図である。
【図４】第１の実施の形態におけるＥＣＣ処理部の一構成例を示すブロック図である。
【図５】第１の実施の形態における符号化部の一構成例を示すブロック図である。
【図６】第１の実施の形態における除算回路の一構成例を示すブロック図である。
【図７】第１の実施の形態における多項式除算部の一構成例を示すブロック図である。
【図８】第１の実施の形態における符号化方法を説明するための図である。
【図９】第１の実施の形態における剰余多項式テーブルの一構成例を示す図である。
【図１０】第１の実施の形態における復号部の一構成例を示すブロック図である。
【図１１】第１の実施の形態におけるメモリコントローラの動作の一例を示すフローチャートである。
【図１２】第１の実施の形態におけるライト処理の一例を示すフローチャートである。
【図１３】第１の実施の形態における除算処理の一例を示すフローチャートである。
【図１４】第１の実施の形態におけるリード処理の一例を示すフローチャートである。
【図１５】第１の実施の形態の第１の変形例における除算回路の一構成例を示すブロック図である。
【図１６】第１の実施の形態の第１の変形例における除算処理の一例を示すフローチャートである。
【図１７】第１の実施の形態の第２の変形例における除算処理の一例を示すフローチャートである。
【図１８】第２の実施の形態における除算回路の一構成例を示すブロック図である。
【図１９】第２の実施の形態における除算処理の一例を示すフローチャートである。
【図２０】第２の実施の形態における分離演算処理の一例を示すフローチャートである。
【図２１】第３の実施の形態における除算回路の一構成例を示すブロック図である。
【図２２】第３の実施の形態における除算処理の一例を示すフローチャートである。
【図２３】第４の実施の形態における除算回路の一構成例を示すブロック図である。
【図２４】第４の実施の形態における除算処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本技術を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（共通因数に含まれる２つの因数を指定する例）
２．第２の実施の形態（共通因数に含まれる２つの因数を指定し、加算結果を分離する例）
３．第３の実施の形態（共通因数に含まれる３つの因数を指定する例）
４．第４の実施の形態（インデックスを次数に置き換え、その次数の共通因数に含まれる２つの因数を指定する例）
【００２０】
＜１．第１の実施の形態＞
［情報処理システムの構成例］
図１は、実施の形態における情報処理システムの一構成例を示すブロック図である。この情報処理システムは、ホストコンピュータ１００およびストレージ２００を備える。
【００２１】
ホストコンピュータ１００は、情報処理システム全体を制御するものである。具体的には、ホストコンピュータ１００は、コマンドおよびライトデータを生成してストレージ２００に信号線１０９を介して供給する。また、ホストコンピュータ１００は、ストレージ２００からリードデータを受け取る。ここで、コマンドは、ストレージ２００を制御するためのものであり、例えば、ライトデータの書込みを指示するライトコマンドや、リードデータの読出しを指示するリードコマンドを含む。
【００２２】
ストレージ２００は、メモリコントローラ３００および不揮発性メモリ５００を備える。このメモリコントローラ３００は、不揮発性メモリ５００を制御するものである。メモリコントローラ３００は、ホストコンピュータ１００からライトコマンドおよびライトデータを受け取った場合には、そのライトデータから誤り検出訂正符号（ＥＣＣ：Error detection and Correction Code）で符号化する。メモリコントローラ３００は、不揮発性メモリ５００に信号線３０９を介してアクセスして符号化したデータを書き込む。
【００２３】
また、ホストコンピュータ１００からリードコマンドを受け取った場合、メモリコントローラ３００は、不揮発性メモリ５００に信号線３０９を介してアクセスして符号化されたデータを読み出す。そして、メモリコントローラ３００は、符号化されたデータを、符号化前のデータに変換（すなわち、復号）する。復号においてメモリコントローラ３００は、ＥＣＣに基づいてデータにおける誤りの検出および訂正を行う。そして、メモリコントローラ３００は、訂正したデータをホストコンピュータ１００に供給する。
【００２４】
不揮発性メモリ５００は、メモリコントローラ３００の制御に従って、データを記憶するものである。例えば、フラッシュメモリが不揮発性メモリ５００として用いられる。
【００２５】
なお、フラッシュメモリの代わりに、ＲｅＲＡＭ（resistance random access memory）やＰＣＲＡＭ（Phase change Random Access Memory）を不揮発性メモリ５００として用いてもよい。または、フラッシュメモリの代わりにＭＲＡＭ（Magnetoresistive Random Access Memory）を不揮発性メモリ５００として用いてもよい。また、メモリコントローラ３００は、データを不揮発性メモリ５００に記録しているが、データを記録することができる媒体や装置であれば、不揮発性メモリ５００以外の記録媒体や記憶装置にデータを記録してもよい。そのような記憶装置の一例として、ハードディスクドライブ（ＨＤＤ：Hard Disk Drive）などを想定することができる。
【００２６】
また、記録媒体等にアクセスする際に符号化および復号が行われているが、この構成に限定されない。通信システムや放送システムなどにおいて、送信装置および受信装置が符号化および復号を行ってもよい。
【００２７】
［ホストコンピュータの構成例］
図２は、第１の実施の形態におけるホストコンピュータ１００の一構成例を示すブロック図である。このホストコンピュータ１００は、ＲＯＭ（Read Only Memory）１０２、ＲＡＭ（Random Access Memory）１０３およびＣＰＵ（Central Processing Unit）１０４を備える。また、ホストコンピュータ１００は、ユーザインターフェース１０１、バス１０５およびストレージインターフェース１０６を備える。
【００２８】
ユーザインターフェース１０１は、情報処理システムと、その利用者とが互いに、入力データや出力データをやりとりするためのインターフェースである。ＲＯＭ１０２は、ＣＰＵ１０４が実行するプログラム等を記憶するものである。ＲＡＭ１０３は、ＣＰＵ１０４が実行する処理において必要となるデータを一時的に保持するものである。ＣＰＵ１０４は、ホストコンピュータ１００全体を制御するものである。バス１０５は、ユーザインターフェース１０１、ＲＯＭ１０２、ＲＡＭ１０３、ＣＰＵ１０４およびストレージインターフェース１０６が相互にデータを交換するための共通の経路である。ストレージインターフェース１０６は、ホストコンピュータ１００とストレージ２００とがデータやコマンドを相互に交換するためのインターフェースである。
【００２９】
［メモリコントローラの構成例］
図３は、第１の実施の形態におけるメモリコントローラ３００の一構成例を示すブロック図である。このメモリコントローラ３００は、ホストインターフェース３０１、ＲＯＭ３０２、ＲＡＭ３０３、ＣＰＵ３０４、ＥＣＣ処理部３１０、バス３０５およびメモリインターフェース３０６を備える。
【００３０】
ホストインターフェース３０１は、メモリコントローラ３００がホストコンピュータ１００との間でデータやコマンドを相互に交換するものである。ＲＡＭ３０３は、ＣＰＵ３０４が実行する処理において必要となるデータを一時的に保持するものである。
【００３１】
ＥＣＣ処理部３１０は、ライトデータを符号化し、また、リードデータを復号するものである。符号化において、ライトデータは所定の単位で誤り訂正符号により符号化される。誤り訂正符号には、例えば、巡回符号の１種である、２元のＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号が用いられる。所定の単位で符号化された個々のデータを以下、「符号語」と称する。それぞれの符号語は、符号化前のデータとパリティとを含む。ＥＣＣ処理部３１０は、符号化したライトデータを不揮発性メモリ５００にメモリインターフェース３０６を介して供給する。
【００３２】
なお、ＥＣＣ処理部３１０は、ＢＣＨ符号にライトデータを符号化しているが、ＢＣＨ符号以外の巡回符号、例えば、ＲＳ（Reed-Solomon）符号やＣＲＣ（Cyclic Redundancy Check）符号にライトデータを符号化してもよい。
【００３３】
また、ＥＣＣ処理部３１０は、符号化されたリードデータを元のデータに復号する。そして、ＥＣＣ処理部３１０は、復号した元のデータをホストコンピュータ１００にホストインターフェース３０１を介して供給する。
【００３４】
ＣＰＵ３０４は、メモリコントローラ３００全体を制御するものである。ＲＯＭ３０２は、ＣＰＵ３０４が実行するプログラム等を記憶するものである。バス３０５は、ホストインターフェース３０１、ＲＯＭ３０２、ＲＡＭ３０３、ＣＰＵ３０４、ＥＣＣ処理部３１０およびメモリインターフェース３０６が相互にデータを交換するための共通の経路である。メモリインターフェース３０６は、メモリコントローラ３００が不揮発性メモリ５００との間でデータやコマンドを相互に交換するためのインターフェースである。
【００３５】
［ＥＣＣ処理部の構成例］
図４は、第１の実施の形態におけるＥＣＣ処理部３１０の一構成例を示すブロック図である。このＥＣＣ処理部３１０は、符号化部３２０および復号部３３０を備える。
【００３６】
符号化部３２０は、ライトデータを、ＥＣＣを用いて符号化するものである。復号部３３０は、リードデータを符号語の単位で復号するものである。
【００３７】
［符号化部の構成例］
図５は、第１の実施の形態における符号化部３２０の一構成例を示すブロック図である。この符号化部３２０は、データバッファ３２１、除算回路４００および符号語生成部３２２を備える。
【００３８】
データバッファ３２１は、バス３０５から入力されたライトデータを符号化対象のデータとして保持するものである。除算回路４００は、データバッファ内のデータを読み出して、そのデータの示す多項式Ａ（ｘ）を所定の除多項式により除算するものである。除多項式として、例えば、ＢＣＨ符号における生成多項式が用いられる。また、以下、除多項式により除算される多項式Ａ（ｘ）を「被除多項式」と称する。この被除多項式Ａ（ｘ）は、例えば、次の式により表される。
【数１】
2016004468.tif 000003
【００３９】
上式において、Ｋは、データ内のシンボル数、すなわち被除多項式Ａ（ｘ）の項数である。Ａｋ（ｘ）ｘｎｋは、被除多項式をＭ（Ｍは、２以上の整数）個に分割した際の個々の多項式である。以下、Ａｋ（ｘ）ｘｎｋを「入力多項式」と称し、Ａｋ（ｘ）を「部分多項式」と称する。また、ｋは、入力多項式を選択した順番を示すインデックスであり、ｎは、入力多項式のそれぞれの項数である。ｘｎｋは、入力多項式の共通因数である。これらの入力多項式内の部分多項式が順に除算回路４００に入力される。除算回路４００は、これらの部分多項式を処理して、被除多項式Ａ（ｘ）を除算した剰余多項式Ｒ（ｘ）を求め、その剰余多項式Ｒ（ｘ）を示すビット列をパリティとして符号語生成部３２２に供給する。剰余多項式Ｒ（ｘ）を求める演算の詳細については後述する。
【００４０】
符号語生成部３２２は、データバッファ３２１から読み出したデータと、除算回路４００からのパリティとからなる符号語を生成し、バス３０５へ出力するものである。
【００４１】
［除算回路の構成例］
図６は、第１の実施の形態における除算回路４００の一構成例を示すブロック図である。この除算回路４００は、多項式選択部４１０と、指定部４１２と、剰余多項式テーブル４１３および４１４と、多項式乗算器４１５および４１６と、多項式加算器４１７と、レジスタ４１８と、多項式除算部４５０とを備える。剰余多項式テーブル４１３および４１４は、例えば、図３におけるＲＡＭ３０３に格納される。
【００４２】
多項式選択部４１０は、複数の入力多項式を次数の小さいものから順に選択するものである。この多項式選択部４１０は、最初の入力多項式内の部分多項式をデータバッファ３２１から取得すると、除算開始フラグを生成して、レジスタ４１８および多項式除算部４５０に供給する。また、多項式選択部４１０は、入力多項式Ａｋ（ｘ）ｘｎｋを選択するたびに、入力多項式内の部分多項式Ａｋ（ｘ）を多項式乗算器４１５に供給し、インデックスｋを指定部４１２に供給する。部分多項式Ａｋ（ｘ）の次数をｄとすると、部分多項式Ａｋ（ｘ）は、ｄ＋１ビットのビット列により表される。
【００４３】
なお、多項式選択部４１０は、部分多項式Ａｋ（ｘ）を順にデータバッファ３２１から読み出す構成としているが、被除多項式全体（すなわち、符号化前のデータ）を読み出す構成としてもよい。多項式選択部４１０とデータバッファ３２１との間のインターフェースとして、読み出すデータのデータ量に応じた帯域のものが用いられる。
【００４４】
指定部４１２は、入力多項式が選択されるたびに、その入力多項式内の共通因数ｘｎｋに対する因数分解により生成される２つの因数を指定するものである。この指定部４１２は、インデックスｋを多項式選択部４１０から受け取り、そのインデックスに対応する共通因数ｘｎｋを分解した際の因数を求める。共通因数ｘｎｋは、例えば、次の式により分解される。
ｘ＾（ｎｋ）＝ｘ＾｛ｎ（ｋ０Ｆ０＋ｆ０）｝
＝ｘ＾（ｎｋ０Ｆ０）・ｘ＾（ｎｆ０）                ・・・式２
上式において、ｋ０は、インデックスｋを所定の除数Ｆ０により除した商であり、ｆ０は、インデックスｋを除数Ｆ０により除した余りである。除数Ｆ０には、（Ｍ−２）よりも小さな値が設定される。ｘ＾（ｎｋ０Ｆ０）と、ｘ＾（ｎｆ０）とのそれぞれは、共通因数を因数分解した因数である。なお、ｘ＾（ｎｋ０Ｆ０）およびｘ＾（ｎｆ０）の一方は、特許請求の範囲に記載の第１因数の一例であり、他方は、特許請求の範囲に記載の第２因数の一例である。また、Ｆ０は、特許請求の範囲に記載の除数の一例である。
【００４５】
例えば、項数ｎが５でインデックスｋが１０である場合、そのインデックスに対応する共通因数はｘ５０である。ここで、除数Ｆ０を４とすると、インデックスｋ（＝１０）を除数Ｆ０（＝４）で除した商ｋ０は２で、余りｆ０は２である。このため、式２により、共通因数ｘ５０は、因数ｘ４０と因数ｘ１０とに分解される。
【００４６】
指定部４１２は、因数ｘ＾（ｎｆ０）を示す余りｆ０を剰余多項式テーブル４１３に供給し、因数ｘ＾（ｎｋ０Ｆ０）を示す商ｋ０を剰余多項式テーブル４１４に供給する。項数ｎおよび除数Ｆ０は固定値であるため、供給する必要はない。
【００４７】
剰余多項式テーブル４１３は、因数ｘ＾（ｎｆ０）ごとに、その因数を除多項式ｇ（ｘ）により除算することにより生じる剰余多項式を保持するテーブルである。剰余多項式は、例えば、ｍビットのビット列により表される。項数ｎは固定値であるため、余りｆ０ごとに剰余多項式が保持される。剰余多項式テーブル４１３を格納する記憶部（ＲＡＭ３０３など）は、指定部４１２からのｆ０に対応する剰余多項式を多項式乗算器４１５に供給する。
【００４８】
剰余多項式テーブル４１４は、因数ｘ＾（ｎｋ０Ｆ０）ごとに、その因数を除多項式ｇ（ｘ）により除算することにより生じる剰余多項式を保持するテーブルである。剰余多項式は、例えば、ｍビットのビット列により表される。項数ｎおよび除数Ｆ０は固定値であるため、ｋ０ごとに剰余多項式が保持される。剰余多項式テーブル４１４を格納する記憶部（ＲＡＭ３０３など）は、指定部４１２からの商ｋ０に対応する剰余多項式を多項式乗算器４１６に供給する。なお、剰余多項式テーブル４１３および４１４の一方は、特許請求の範囲に記載の第１の剰余テーブルの一例であり、他方は特許請求の範囲に記載の第２の剰余テーブルの一例である。
【００４９】
多項式乗算器４１５は、剰余多項式テーブル４１３からの剰余多項式と、多項式選択部４１０からの部分多項式Ａｋ（ｘ）とを乗算するものである。この乗算結果は、（ｄ＋ｍ−１）次の多項式となり、（ｄ＋ｍ）ビットのビット列により表される。多項式乗算器４１５は、その乗算結果を多項式乗算器４１６に供給する。
【００５０】
多項式乗算器４１６は、剰余多項式テーブル４１４からの剰余多項式と、多項式乗算器４１５からの多項式とを乗算するものである。この乗算結果は、（ｄ＋２ｍ−２）次の多項式となり、（ｄ＋２ｍ−１）ビットのビット列により表される。多項式乗算器４１６は、その乗算結果を多項式加算器４１７に供給する。なお、多項式乗算器４１５および４１６からなる回路は、特許請求の範囲に記載の多項式乗算部の一例である。
【００５１】
多項式加算器４１７は、入力多項式が選択されるたびに、レジスタ４１８に保持された値に多項式乗算器４１６からの乗算結果を加算するものである。この多項式加算器４１７は、加算結果によりレジスタ４１８を更新する。
【００５２】
レジスタ４１８は、多項式加算器４１７により生成された加算結果を保持するものである。また、レジスタ４１８は、除算開始フラグが多項式選択部４１０から供給されると、保持している値を初期値（例えば、「０」）にする。
【００５３】
これらの多項式加算器４１７およびレジスタ４１８により、入力多項式のそれぞれについて生成された乗算結果の全てが加算される。なお、多項式加算器４１７およびレジスタ４１８を含む回路は、特許請求の範囲に記載の多項式加算部の一例である。
【００５４】
多項式除算部４５０は、全ての乗算結果が加算された加算結果を除多項式ｇ（ｘ）により除算して剰余多項式Ｒ（ｘ）を求めるものである。この多項式除算部４５０は、除算開始フラグが供給されてから、レジスタ４１８がＭ回更新されたタイミングで加算結果Ｂｉ（ｘ）をレジスタ４１８から読み出す。そして、多項式除算部４５０は、読み出した加算結果Ｂｉ（ｘ）を除多項式ｇ（ｘ）により除算して剰余多項式Ｒ（ｘ）を符号語生成部３２２に供給する。
【００５５】
これらの構成により、次式により表される演算が行われる。
【数２】
2016004468.tif 000004
上式において「ｍｏｄ」は、有限体上の多項式に対するモジュロ演算を示す。また、「ｘ＾（ｎｆ０）  ｍｏｄ  ｇ（ｘ）」は、剰余多項式テーブル４１３から読み出される。「ｘ＾（ｎｋ０Ｆ０）  ｍｏｄ  ｇ（ｘ）」は、剰余多項式テーブル４１４から読み出される。さらに、ｑＭ、ｒＭは、ＭをＦ０で割った商と余りを表す。これ以降では、ｒＭ＝０、すなわち、ＭがＦ０で割り切れるときのみについて説明を行なうが、ｒＭ≠０、すなわち、ＭがＦ０で割り切れないときでも同様の議論をすることが可能である。ｒＭ＝０のとき、式３の第２項は０になる。
【００５６】
式３において部分多項式Ａｋ（ｘ）と剰余との乗算結果の積算値は、被除多項式Ａ（ｘ）より次数が小さくなる。このため、この積算値を多項式除算部４５０がｇ（ｘ）により除算することにより、Ａ（ｘ）をそのまま除算する構成と比較して、除算回路４００の遅延時間を低減することができる。
【００５７】
また、共通因数ｘ＾（ｎｋ）をｘ＾（ｎｋ０Ｆ０）とｘ＾（ｎｆ０）との各因数に分解して、それらの因数ごとに剰余を保持するため、共通因数ごとに剰余を保持する構成と比較して剰余多項式テーブルのエントリ数を少なくすることができる。これにより、剰余多項式テーブルを格納する記憶部（ＲＡＭ３０３など）の容量を削減することができる。
【００５８】
［多項式除算部の構成例］
図７は、第１の実施の形態における多項式除算部４５０の一構成例を示すブロック図である。この多項式除算部４５０は、除算制御部４５１と、スイッチ４５２と、ｍ個の乗算器４５３と、ｍ段のフリップフロップ４５４と、ｍ個の加算器４５５とを備える。除算制御部４５１およびフリップフロップ４５４は、所定のクロック信号ＣＬＫに同期して動作する。
【００５９】
フリップフロップ４５４は、加算器４５５から供給されたビットを保持するものである。ｍ段のフリップフロップ４５４のそれぞれの前段には、加算器４５５が設けられる。０段目から（ｍ−２）段目までのフリップフロップは、それぞれ、クロック信号ＣＬＫに同期して前段の加算器４５５からのビットを保持し、保持したビットを後段の加算器４５５に供給する。また、（ｍ−１）段目のフリップフロップ４５４は、クロック信号ＣＬＫに同期して前段の加算器４５５からのビットを保持し、保持したビットを符号語生成部３２２とスイッチ４５２とに供給する。
【００６０】
乗算器４５３は、スイッチ４５２からのビットとｇ０乃至ｇｍ-1のいずれかとを乗算するものである。ここで、ｇ０乃至ｇｍ-1は、除多項式ｇ（ｘ）における０乃至（ｍ−１）次の項の係数を示す。ｇ０乃至ｇｍ-1に対応する乗算器４５３のそれぞれは、０乃至（ｍ−１）段目のフリップフロップの前段の加算器４５５に乗算結果を供給する。
【００６１】
加算器４５５は、乗算器４５３からの乗算結果と加算結果Ｂｉ（ｘ）のいずれかの項の係数とを加算するものである。初段のフリップフロップ４５４の前段の加算器４５５は、加算結果Ｂｉ（ｘ）の最小次数の項の係数ｂ０と、ｇ０に対応する乗算器４５３からの乗算結果とを加算し、加算結果のビットを初段のフリップフロップ４５４に供給する。ｊ（ｊは１乃至ｍ−１の整数）段目のフリップフロップ４５４の前段の加算器４５５は、前段のフリップフロップ４５４からのビットと、係数ｂｊと、ｇｊに対応する乗算器４５３からの乗算結果とを加算し、後段のフリップフロップ４５４へ供給する。
【００６２】
スイッチ４５２は、除算制御部４５１の制御に従って、最終段のフリップフロップ４５４と、全ての乗算器４５３との間の経路を開閉するものである。
【００６３】
除算制御部４５１は、スイッチ４５２を制御するものである。この除算制御部４５１は、加算結果Ｂｉ（ｘ）がレジスタ４１８に保持されたときから、その加算結果Ｂｉ（ｘ）の全てのビットが入力されるまでの間、スイッチ４５２を閉状態に制御する。例えば、
Ｂｉ（ｘ）を示すデータのビット数がｍビットである場合、Ｂｉ（ｘ）が保持されてから、ｍクロックが経過するまでの間、スイッチ４５２が閉状態に制御される。また、その期間以外において、除算制御部４５１は、スイッチ４５２を開状態に制御する。
【００６４】
図７に例示した構成により、加算結果Ｂｉ（ｘ）を示すビット列は１ビットずつ順に処理される。このため、除算対象の多項式の次数が高いほど、遅延時間が多くなる。しかし、前述したように、加算結果Ｂｉ（ｘ）は被除多項式Ａ（ｘ）より次数が小さい。このため、この加算結果Ｂｉ（ｘ）を除算する多項式除算部４５０の遅延時間は、Ａ（ｘ）をそのまま除算する除算器の遅延時間よりも短くなる。
【００６５】
図８は、第１の実施の形態における符号化方法を説明するための図である。同図におけるａは、符号化前のデータの一例である。符号化前のデータとして、Ｋ（例えば、２４６）ビットのデータが符号化部３２０に入力される。
【００６６】
図８におけるｂは、符号化前のデータにより表される被除多項式Ａ（ｘ）の一例である。Ｋが２４６の場合、データは、そのデータ内の各ビットの値を各項の係数とする２４５次の被除多項式Ａ（ｘ）により表される。例えば、データ内の０番目から２４５番目のビットの値は、それぞれ、被除多項式Ａ（ｘ）内の０次乃至２４５次の項の係数ａ０乃至ａ２４５を示す。
【００６７】
図８におけるｃは、被除多項式Ａ（ｘ）を分割した入力多項式の一例である。例えば、被除多項式Ａ（ｘ）は、Ｍ（例えば、５０）個の入力多項式に分割される。それぞれの入力多項式において、各項は、共通因数により括ることができる。例えば、次数が９の入力多項式＃２の各項は、ｘ５の共通因数により括ることができる。共通因数により括った項からなる多項式（すなわち、部分多項式）はＭ個生成され、除算回路４００に順に入力される。
【００６８】
図８におけるｄは、部分多項式を示す部分多項式データの一例を示す図である。Ｍ個の部分多項式のそれぞれは、Ｋにパディングのビット数を加えた値をＭで割った商のビット数の部分多項式データにより表される。パディングは、ＫをＭで割り切れない場合に、割り切れる値になるように加えられる。例えば、Ｋが２４６でＭが５０である場合、パディングとして「０」の値の４ビットが加えられ、２５０を５０で割った５ビットの部分多項式データが順に入力される。
【００６９】
図８におけるｅは、被除多項式Ａ（ｘ）内の共通因数の一例である。Ｍが５０の場合、Ａ（ｘ）は、次数が５ずつ異なるｘ０乃至ｘ２４５の５０個の共通因数を含む。
【００７０】
図８おけるｆは、共通因数のそれぞれを２つの因数に分解した因数の一例である。上述の式２により共通因数ｘ＾（ｎｋ）は、ｘ＾（ｎｋ０Ｆ０）と、ｘ＾（ｎｆ０）とに分解される。ｋを０乃至４９、項数ｎを５、除数Ｆ０を４とすると、インデックスｋを除数Ｆ０で除した余りｆ０は、０乃至３の値となる。また、インデックスｋを除数Ｆ０で除した商ｋ０は、０乃至１２の値となる。このため、商ｋ０ごとのｘ＾（ｎｋ０Ｆ０）からなる配列Ａは、次数が２０ずつ異なるｘ０乃至ｘ２４０の１３個の因数を含む。また、余りｆ０ごとのｘ＾（ｎｆ０）からなる配列Ｂは、次数が５ずつ異なるｘ０乃至ｘ１５の４個の因数を含む。つまり、５０個の共通因数のそれぞれは、配列Ａ内の１３個の因数のいずれかと、配列Ｂ内の４個の因数のいずれかとに分解される。例えば、共通因数ｘ２４５は、配列Ａ内の因数ｘ２４０と配列Ｂ内の因数ｘ５とに分解される。
【００７１】
配列Ａ、Ｂ内のそれぞれの因数ごとに、その因数を除多項式ｇ（ｘ）で除した剰余が、予め剰余多項式テーブル４１３および４１４に保持される。これにより、共通因数ごとに剰余を保持する構成と比較してテーブルを格納する記憶部の容量を削減することができる。
【００７２】
共通因数ごとに剰余を保持する構成では、共通因数の個数がＭ個である場合に、テーブルのエントリ数はＭ個必要とされる。これに対して、共通因数を分解する際には、エントリ数は、（Ｍ／Ｆ０＋Ｆ０）個であればよい。（Ｍ／Ｆ０＋Ｆ０）をＭより小さくするには、次の式が成立する必要がある。
Ｍ＞（Ｍ／Ｆ０＋Ｆ０）  ⇔  Ｍ＞Ｆ０２／（Ｆ０−１）              ・・・式４
【００７３】
ここで、Ｆ０≧２のとき、
Ｆ０＋２≧Ｆ０２／（Ｆ０−１）≧Ｆ０＋１                          ・・・式５
が成立するため、式４および式５より、次式が成立する際に、（Ｍ／Ｆ０＋Ｆ０）がＭより小さくなる。
Ｍ＞Ｆ０＋２                                                    ・・・式６
したがって、式６より、（Ｍ−２）より小さなＦ０を設定すれば、テーブルのエントリ数を削減することができる。
【００７４】
例えば、Ｍが５０である場合、テーブルのエントリ数が５０個必要とされる。これに対して、（Ｍ−２）より小さな４の値をＦ０に設定して、共通因数を２つの因数に分解した場合、（Ｍ／Ｆ０＋Ｆ０）が１７であるからテーブルのエントリ数は１７個あればよく、５０個より少なくなる。
【００７５】
図８におけるｇは、符号語の一例を示す図である。符号語は、符号化前のデータとパリティとを含む。このパリティは、被除多項式Ａ（ｘ）を除多項式ｇ（ｘ）により除した剰余を示すビット列である。Ｋ（例えば、２４６）ビットのデータに、Ｎ−Ｋビットのパリティが付加され、これらを含むＮ（例えば、２５５）ビットの符号語が生成される。
【００７６】
［剰余多項式テーブルの構成例］
図９は、第１の実施の形態における剰余多項式テーブルの一構成例を示す図である。同図におけるａは、剰余多項式テーブル４１３の一例を示す図である。この剰余多項式テーブル４１３は、因数ｘ＾（ｎｆ０）ごとに、その因数を除多項式ｇ（ｘ）により除した剰余多項式を保持する。ｎは、固定値であるため、同図のａにおいては、ｆ０ごとに、剰余多項式が保持されている。
【００７７】
図９におけるｂは、剰余多項式テーブル４１４の一例を示す図である。この剰余多項式テーブル４１４は、因数ｘ＾（ｎｋ０Ｆ０）ごとに、その因数を除多項式ｇ（ｘ）により除した剰余多項式を保持する。ｎおよびＦ０は、固定値であるため、同図のｂにおいては、ｋ０ごとに、剰余多項式が保持されている。
【００７８】
図１０は、第１の実施の形態における復号部３３０の一構成例を示すブロック図である。この復号部３３０は、データバッファ３３１、除算回路４０１、および、誤り検出訂正部３３２を備える。
【００７９】
データバッファ３３１は、読み出された符号語を受信語として保持するものである。除算回路４０１の構成は、符号化部３２０における除算回路４００と同様である。この除算回路４０１は、剰余多項式Ｒ（ｘ）を示すビット列を誤り検出訂正部３３２に供給する。
【００８０】
誤り検出訂正部３３２は、パリティに基づいて誤りの有無の検出と、誤りの訂正とを行うものである。この誤り検出訂正部３３２は、データバッファ３３１に保持された受信語のパリティと、除算回路４０１からのビット列とが一致するか否かを判断する。これらが一致する場合に誤り検出訂正部３３２は受信語に誤りがないと判断し、不一致の場合には誤りがあると判断する。不一致のある場合には、誤り検出訂正部３３２は、その誤りを訂正する。２元のＢＣＨ符号を用いる場合には、例えば、チェン探索法により誤りの位置が探索され、探索された位置のビットの反転により誤りが訂正される。誤り検出訂正部３３２は、訂正したデータを、誤り検出の結果とともにバス３０５を介してホストコンピュータ１００に供給する。
【００８１】
なお、誤り検出訂正部３３２は、誤り検出と、誤りの訂正との両方を行っているが、誤りの検出のみを行う構成としてもよい。また、誤り検出訂正部３３２は、パリティを除いたデータのみを供給しているが、パリティおよびデータを含む受信語を供給してもよい。また、誤り検出訂正部３３２は、特許請求の範囲に記載の誤り検出部の一例である。
【００８２】
［メモリコントローラの動作例］
図１１は、第１の実施の形態におけるメモリコントローラの動作の一例を示すフローチャートである。この動作は、例えば、メモリコントローラ３００に電源が投入されたときに開始する。
【００８３】
メモリコントローラ３００は、ホストコンピュータ１００からライトコマンドを受信したか否かを判断する（ステップＳ９０１）。ライトコマンドを受信した場合には（ステップＳ９０１：Ｙｅｓ）、メモリコントローラ３００は、ライトデータの符号化と、符号化したライトデータの不揮発性メモリ５００への書込みとを行うライト処理を実行する（ステップＳ９１０）。
【００８４】
ライトコマンドを受信していない場合（ステップＳ９０１：Ｎｏ）、または、ステップＳ９１０の後、メモリコントローラ３００は、ホストコンピュータ１００からリードコマンドを受信したか否かを判断する（ステップＳ９０２）。リードコマンドを受信した場合には（ステップＳ９０２：Ｙｅｓ）、メモリコントローラ３００は、リードデータにおいて誤りの検出および訂正を行うリード処理を実行する（ステップＳ９７０）。リードコマンドを受信していない場合には（ステップＳ９０２：Ｎｏ）、または、ステップＳ９７０の後、メモリコントローラ３００は、ステップＳ９０１に戻る。
【００８５】
図１２は、第１の実施の形態におけるライト処理の一例を示すフローチャートである。メモリコントローラ３００は、まず、符号化前のデータを保持する（ステップＳ９１１）。そして、メモリコントローラ３００は、そのデータの示す被除多項式を除多項式により除算する除算処理を実行する（ステップＳ９２０）。メモリコントローラ３００は、除算処理により得られた剰余多項式を示すビット列をパリティとしてデータに付加して符号語を生成し、その符号語の書込みを行う（ステップＳ９１２）。ステップＳ９１２の後、メモリコントローラ３００は、ライト処理を終了する。
【００８６】
図１３は、第１の実施の形態における除算処理の一例を示すフローチャートである。メモリコントローラ３００は、変数Ｖ０を初期値（例えば、「０」）にする（ステップＳ９２１）。そして、メモリコントローラ３００は、部分多項式Ａｋ（ｘ）のいずれかを選択する（ステップＳ９２２）。また、メモリコントローラ３００は、部分多項式のインデックスｋをＦ０で除算し、商ｋ０と余りｆ０とを得る（ステップＳ９２３）。そして、メモリコントローラ３００は、商ｋ０および余りｆ０に対応する剰余多項式Ｖ１およびＶ２を剰余多項式テーブル４１３および４１４から取得する（ステップＳ９２４）。
【００８７】
メモリコントローラ３００は、部分多項式Ａｋ（ｘ）と、剰余多項式Ｖ１およびＶ２とを乗算し（ステップＳ９２５）、その乗算結果を変数Ｖ０に加算する（ステップＳ９２６）。そして、メモリコントローラ３００は、部分多項式Ａｋ（ｘ）の全てを選択したか否かを判断する（ステップＳ９２７）。
【００８８】
部分多項式Ａｋ（ｘ）の全てを選択していない場合に（ステップＳ９２７：Ｎｏ）、メモリコントローラ３００は、ステップＳ９２２に戻る。一方、部分多項式Ａｋ（ｘ）の全てを選択した場合に（ステップＳ９２７：Ｙｅｓ）、メモリコントローラ３００は、変数Ｖ０を除多項式ｇ（ｘ）により除算し、剰余多項式を生成する（ステップＳ９２８）。ステップＳ９２８の後、メモリコントローラ３００は、除算処理を終了する。
【００８９】
図１４は、第１の実施の形態におけるリード処理の一例を示すフローチャートである。メモリコントローラ３００は、受信語を保持する（ステップＳ９７１）。そして、メモリコントローラ３００は、受信語内のデータの示す被除多項式を除多項式により除算する除算処理を実行する（ステップＳ９８０）。この除算処理は、ライト処理における除算処理（ステップＳ９２０）と同様の処理である。メモリコントローラ３００は、除算処理により得られた剰余多項式とパリティとに基づいて受信語における誤り検出と誤り訂正とを行う（ステップＳ９７２）。ステップＳ９７２の後、メモリコントローラ３００は、リード処理を終了する。
【００９０】
このように、本技術の第１の実施の形態によれば、除算回路４００は、共通因数の分解により生成される２つの因数のそれぞれに対応する剰余をテーブルに保持するため、テーブルを格納する記憶部の容量を削減することができる。
【００９１】
［第１の変形例］
第１の実施の形態では、多項式選択部４１０が、部分多項式のインデックスｋを生成していたが、計数値をカウントアップしてインデックスｋとして供給するカウンタを多項式選択部４１０とは別に設けてもよい。次数の小さい入力多項式から順に選択する構成では、アップカウンタにより、インデックスを容易に生成することができる。第１の変形例の除算回路４００は、計数値をカウントアップするカウンタをさらに設けた点において第１の実施の形態と異なる。
【００９２】
図１５は、第１の実施の形態の第１の変形例における除算回路４００の一構成例を示すブロック図である。第１の変形例の除算回路４００は、カウンタ４１１をさらに備える。
【００９３】
カウンタ４１１は、部分多項式が選択されるたびに計数値を計数するものである。このカウンタ４１１は、除算開始フラグが入力されると、計数値を初期値（例えば、「０」）にし、多項式選択部４１０が部分多項式を選択するたびに計数値を計数する。例えば、多項式選択部４１０の動作に同期して、計数値がカウントアップされる。カウンタ４１１は、計数値をインデックスｋとして、指定部４１２に供給する。
【００９４】
第１の変形例の多項式選択部４１０は、除算開始フラグをカウンタ４１１にさらに供給し、次数の小さい入力多項式から順に選択する。
【００９５】
図１６は、第１の実施の形態の第１の変形例における除算処理の一例を示すフローチャートである。第１の変形例の除算処理は、ステップＳ９２１およびＳ９２７の代わりにステップＳ９３１およびＳ９３２を実行し、ステップＳ９３３をさらに実行する点において第１の実施の形態と異なる。
【００９６】
メモリコントローラ３００は、まず、変数Ｖ０およびインデックスｋを初期値（「０」）にする（ステップＳ９３１）。そして、メモリコントローラ３００は、ステップＳ９２２乃至Ｓ９２６を実行する。ステップＳ９２６の後、メモリコントローラ３００は、インデックスｋが最大値Ｍ−１であるか否かを判断する（ステップＳ９３２）。
【００９７】
ｋがＭ−１でない場合に（ステップＳ９３２：Ｎｏ）、メモリコントローラ３００は、インデックスｋをインクリメントし（ステップＳ９３３）、ステップＳ９２２に戻る。一方、ｋがＭ−１である場合に（ステップＳ９３２：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９２８を実行する。
【００９８】
このように、第１の変形例によれば、カウンタがカウントアップした計数値をインデックスとして供給するため、次数の小さい入力多項式から順に選択する場合に、除算回路４００は、カウンタによりインデックスを容易に生成することができる。
【００９９】
［第２の変形例］
第１の実施の形態では、多項式選択部４１０が、部分多項式のインデックスｋを生成していたが、計数値をカウントダウンしてインデックスｋとして供給するカウンタを多項式選択部４１０とは別に設けてもよい。次数の大きい入力多項式から順に選択する構成では、ダウンカウンタにより、インデックスを容易に生成することができる。第２の変形例の除算回路４００は、計数値をカウントダウンするカウンタをさらに設けた点において第１の実施の形態と異なる。
【０１００】
第２の変形例の除算回路４００の構成は、カウンタ４１１がダウンカウンタである点以外は、第１の変形例と同様である。また、第２の変形例の多項式選択部４１０は、次数の大きい入力多項式から順に選択する。
【０１０１】
図１７は、第１の実施の形態の第２の変形例における除算処理の一例を示すフローチャートである。第２の変形例の除算処理は、ステップＳ９２１およびＳ９２７の代わりにステップＳ９３４およびＳ９３５を実行し、ステップＳ９３６をさらに実行する点において第１の実施の形態と異なる。
【０１０２】
メモリコントローラ３００は、まず、変数Ｖ０を初期値「０」にし、インデックスｋを初期値「Ｍ−１」にする（ステップＳ９３４）。そして、メモリコントローラ３００は、ステップＳ９２２乃至Ｓ９２６を実行する。ステップＳ９２６の後、メモリコントローラ３００は、インデックスｋが最小値「０」であるか否かを判断する（ステップＳ９３５）。
【０１０３】
ｋが「０」でない場合に（ステップＳ９３５：Ｎｏ）、メモリコントローラ３００は、インデックスｋをデクリメントし（ステップＳ９３６）、ステップＳ９２２に戻る。一方、ｋが「０」である場合に（ステップＳ９３５：Ｙｅｓ）、メモリコントローラ３００は、ステップＳ９２８を実行する。
【０１０４】
このように、第２の変形例によれば、カウンタがカウントダウンした計数値をインデックスとして供給するため、次数の大きい入力多項式から順に選択する場合に、除算回路４００は、カウンタによりインデックスを容易に生成することができる。
【０１０５】
＜２．第２の実施の形態＞
第１の実施の形態では除算回路４００が、レジスタ４１８に保持された加算結果をそのまま多項式除算部４５０で除算していたが、この加算結果をさらに複数の多項式に分離してから多項式除算部４５０で除算してもよい。分離することにより、除算対象の多項式の次数を低減することができる。第２の実施の形態の除算回路４００は、レジスタ４１８に保持された加算結果を複数の多項式に分離する点において第１の実施の形態と異なる。
【０１０６】
図１８は、第２の実施の形態における除算回路４００の一構成例を示すブロック図である。第２の実施の形態の除算回路４００の構成は、多項式分離部４２０、多項式乗算器４２１および多項式加算器４２２をさらに備える点において第１の実施の形態と異なる。また、第２の実施の形態の多項式選択部４１０は、除算開始フラグを多項式分離部４２０にさらに供給する。
【０１０７】
多項式分離部４２０は、除算開始フラグが供給されてからレジスタ４１８がＭ回更新されたタイミングで、加算結果Ｂｉ（ｘ）を読み出し、その加算結果Ｂｉ（ｘ）を２つの多項式に分離するものである。分離された２つの多項式のそれぞれを以下、「分離多項式」と称する。加算結果Ｂｉ（ｘ）の多項式の次数が（ｄ＋２ｍ−２）である場合、例えば、その多項式は、（ｄ＋２ｍ−２）次の分離多項式と（ｄ＋２ｍ−２−ｓ）次の分離多項式とに分離される。ｓの設定方法については後述する。これらの分離多項式は、次の式により表される。
【数３】
2016004468.tif 000005
【数４】
2016004468.tif 000006
【０１０８】
式７において、Ａｕ（ｘ）ｘd+2m-1-sと、Ａｖ（ｘ）とが分離多項式に相当する。また、ｘd+2m-1-sは、分離多項式Ａｕ（ｘ）ｘd+2m-1-sの共通因数であり、Ａｕ（ｘ）は、その分離多項式内の部分多項式である。
【０１０９】
多項式分離部４２０は、部分多項式Ａｕ（ｘ）を多項式乗算器４２１に供給し、分離多項式Ａｖ（ｘ）を多項式加算器４２２に供給する。部分多項式Ａｕ（ｘ）は、ｓビットのビット列により表される。また、分離多項式Ａｖ（ｘ）は、（ｄ＋２ｍ−１−ｓ）ビットのビット列により表される。
【０１１０】
多項式乗算器４２１は、共通因数ｘd+2m-1-sを除多項式により除した剰余多項式と、部分多項式Ａｕ（ｘ）とを乗算するものである。この多項式乗算器４２１は、共通因数ｘd+2m-1-sに対応する剰余多項式を剰余多項式テーブル４１３または４１４から取得する。なお、多項式乗算器４２１は、剰余多項式テーブルを格納した領域以外の記憶領域に予め保持しておいた剰余多項式を読み出してもよい。そして、多項式乗算器４２１は、乗算結果を多項式加算器４２２に供給する。乗算結果は、（ｍ−１＋ｓ）ビットのビット列により表される。
【０１１１】
多項式加算器４２２は、多項式乗算器４２１からの乗算結果に分離多項式Ａｖ（ｘ）を加算するものである。この多項式加算器４２２は、加算結果を多項式除算部４５０に供給する。
【０１１２】
これらの多項式分離部４２０、多項式乗算器４２１、多項式加算器４２２および多項式除算部４５０により、次式により表される演算が実行される。
【数５】
2016004468.tif 000007
【０１１３】
ここで、Ａｕ（ｘ）の次数はｓ−１次以下であり、共通因数ｘd+2m-1-sの剰余はｍ−１次以下であり、Ａｖ（ｘ）の次数は、ｄ＋２ｍ−２−ｓ以下である。このため、式９の右辺の最後の除多項式ｇ（ｘ）により除算される多項式の次数ｔは、次の式により表される。
【０１１４】
ｔ：＝ｍａｘ｛（ｍ−２＋ｓ）、（ｄ＋２ｍ−２−ｓ）｝              ・・・式１０
上式においてｍａｘ（Ａ、Ｂ）は、ＡおよびＢのうち大きい方を返す関数である。
【０１１５】
式１０により表された次数を、分離前の多項式の次数であるｄ＋２ｍ−２よりも小さくする場合には、次式が成立する必要がある。
ｄ＋２ｍ−２＞ｍ−２＋ｓ                                      ・・・式１１
ｄ＋２ｍ−２＞ｄ＋２ｍ−２−ｓ                                ・・・式１２
【０１１６】
式１１および式１２の両方が成立するには、次式が成立する必要がある。
０＜ｓ＜ｄ＋ｍ                                                ・・・式１３
【０１１７】
式１３が成立する際のｓを設定することにより、多項式除算部４５０により除算される多項式の次数を分離前より小さくすることができる。これにより、除算回路４００の遅延時間を短くすることができる。
【０１１８】
より詳細には、ｄ＋ｍが偶数であれば、ｓが（ｄ＋ｍ）／２のときに次数ｔは最小となり、その最小値は（ｄ＋３ｍ−４）／２である。一方、ｄ＋ｍが奇数であれば、ｓが（ｄ＋ｍ±１）／２のときに次数ｔは最小となり、その最小値は（ｄ＋３ｍ−３）／２である。
【０１１９】
例えば、ｄを１２８、ｍを１０４とすると、レジスタ４１８から読み出される多項式の次数は、次の式により求められる。
ｄ＋２ｍ−２＝１２８＋２×１０４−２＝３３４                  ・・・式１４
【０１２０】
また、式１３を満たすｓを１１６とすると、多項式加算器４２２の出力する多項式の次数ｔは、式１０に基づいて、次式により求められる。
ｔ＝（ｄ＋３ｍ−４）／２＝（１２８＋３×１０４−４）／２＝２１８  …式１５
【０１２１】
式１４および式１５に例示したように、レジスタ４１８からの多項式を分離して処理することにより、多項式除算部４５０に入力される多項式の次数を３３４から２１８に低減することができる。
【０１２２】
なお、多項式加算器４１７、レジスタ４１８、多項式分離部４２０、多項式乗算器４２１および多項式加算器４２２からなる回路は、特許請求の範囲に記載の多項式加算部の一例である。
【０１２３】
また、多項式分離部４２０、多項式乗算器４２１および多項式加算器４２２を１組として、１組の回路だけで、多項式除算部４５０に入力される多項式の次数を低減しているが、２組以降の回路をレジスタ４１８と多項式除算部４５０との間に直列に挿入してもよい。これにより、多項式除算部４５０に入力する多項式の次数をさらに低減して、遅延時間を短くすることができる。
【０１２４】
また、第２の実施の形態の除算回路４００において、第１の変形例や第２の変形例と同様にカウンタ４１１をさらに設けてもよい。
【０１２５】
図１９は、第２の実施の形態における除算処理の一例を示すフローチャートである。第２の実施の形態の除算処理は、ステップＳ９４０をさらに実行する点において第１の実施の形態と異なる。Ａｋ（ｘ）の全てを選択した場合に（ステップＳ９２７：Ｙｅｓ）、メモリコントローラ３００は、分離演算処理（ステップＳ９４０）を実行し、ステップＳ９２８を実行する。
【０１２６】
図２０は、第２の実施の形態における分離演算処理の一例を示すフローチャートである。メモリコントローラ３００は、変数Ｖ０の示す多項式を分離多項式Ａｕ（ｘ）ｘd+2m-1-sと、分離多項式Ａｖ（ｘ）とに分離する（ステップＳ９４１）。また、メモリコントローラ３００は、共通因数ｘd+2m-1-sに対応する剰余Ｃを取得する（ステップＳ９４２）。
【０１２７】
そして、メモリコントローラ３００は、部分多項式Ａｕ（ｘ）および剰余Ｃを乗算する（ステップＳ９４３）。メモリコントローラ３００は、その乗算結果に分離多項式Ａｖ（ｘ）を加算し、その加算結果により変数Ｖ０を更新する（ステップＳ９４４）。ステップＳ９４４の後、メモリコントローラ３００は、分離演算処理を終了する。
【０１２８】
このように、本技術の第２の実施の形態によれば、除算回路４００は、加算結果を複数の分離多項式に分離してから除算するため、除算対象の多項式の次数を分離前よりも低減することができる。これにより、除算回路４００の遅延時間をさらに短くすることができる。
【０１２９】
＜３．第３の実施の形態＞
第１の実施の形態では除算回路４００が、共通因数を２つの因数に分解していたが、３つ以上の因数に分解してもよい。これにより、剰余多項式テーブルのエントリ数をさらに削減することができる。第３の実施の形態の除算回路４００は、共通因数を３つ以上の因数に分解する点において第１の実施の形態と異なる。
【０１３０】
図２１は、第３の実施の形態における除算回路４００の一構成例を示すブロック図である。第３の実施の形態の除算回路４００は、指定部４１２の代わりに指定部４３１を備え、剰余多項式テーブル４３２および多項式乗算器４３３をさらに備える点において第１の実施の形態と異なる。
【０１３１】
指定部４３１は、共通因数の因数分解により生成される３つの因数を指定するものである。余りｆ０を除数Ｆ１で割った商をｋ１、余りをｆ１とすると、余りｆ０は次の式により表すことができる。ここで、余りｆ１は、「０」乃至Ｆ１の整数である。
ｆ０＝ｋ１Ｆ１＋ｆ１                                            ・・・式１６
【０１３２】
式２および式１６より、共通因数ｘｎｋは、次の式により分解される。
ｘ＾（ｎｋ）＝ｘ＾（ｎｋ０Ｆ０）・ｘ＾（ｎｆ０）
＝ｘ＾（ｎｆ１）・ｘ＾（ｎｋ１Ｆ１）・ｘ＾（ｎｋ０Ｆ０）・・・式１７
【０１３３】
指定部４３１は、余りｆ１を剰余多項式テーブル４１３に供給し、商ｋ０を剰余多項式テーブル４１４に供給し、商ｋ１を剰余多項式テーブル４３２に供給する。ｎ、Ｆ０およびＦ１は固定値であるため、供給する必要はない。
【０１３４】
剰余多項式テーブル４３２は、因数ｘ＾（ｎｋ１Ｆ１）ごとに、その因数を除多項式ｇ（ｘ）により除算することにより生じる剰余多項式を保持するテーブルである。剰余多項式は、例えば、ｍビットのビット列により表される。ただし、ｎおよびＦ１は固定値であるため、ｋ１ごとに剰余多項式が保持される。剰余多項式テーブル４３２を格納する記憶部（ＲＡＭ３０３など）は、指定部４３１からのｋ１に対応する剰余多項式を多項式乗算器４３３に供給する。なお、剰余多項式テーブル４３２は、特許請求の範囲に記載の第３の剰余テーブルの一例である。
【０１３５】
多項式乗算器４３３は、多項式乗算器４１６の乗算結果に、剰余多項式テーブル４３２からの剰余多項式を乗算するものである。この多項式乗算器４３３は、乗算結果を多項式加算器４１７に供給する。多項式乗算器４３３からの乗算結果は、（ｄ＋３ｍ−２）ビットのビット列により表される。
【０１３６】
なお、多項式乗算器４１５、４１６および４３３からなる回路は、特許請求の範囲に記載の多項式乗算部の一例である。
【０１３７】
これらの構成により、次式の演算が行われる。
【数６】
2016004468.tif 000008
ただし、ｑＭ は、ＭをＦ０で割った商であり、qF0は、Ｆ０をＦ1で割った商である。上記ではＦ０をＦ1で割った余りが０であるときの式変形であるが、Ｆ０をＦ1で割った余りが０でないときも同様の議論が可能である。
【０１３８】
部分多項式の次数はｄ以下であり、３つの因数のそれぞれに対応する剰余多項式の次数は、いずれも（ｍ−１）次以下である。このため、式１８の右辺の最後の除多項式ｇ（ｘ）により除算される多項式の次数は、（ｄ＋３ｍ−３）次以下である。
【０１３９】
なお、指定部４３１は、共通因数の因数分解により生成される３つの因数を指定しているが、４つ以上の因数を指定することもできる。この場合には、指定した因数の個数と同数の剰余多項式テーブルが設けられ、指定した因数の個数と同数の多項式乗算器が設けられる。
【０１４０】
また、第３の実施の形態の除算回路４００において、第１の変形例や第２の変形例と同様にカウンタ４１１をさらに設けてもよい。
【０１４１】
また、第３の実施の形態の除算回路４００は、第２の実施の形態と同様に、レジスタ４１８に保持された加算結果を複数の分離多項式に分離してもよい。この場合には、多項式分離部４２０、多項式乗算器４２１および多項式加算器４２２がさらに設けられる。
【０１４２】
図２２は、第３の実施の形態における除算処理の一例を示すフローチャートである。第３の実施の形態の除算処理は、ステップＳ９２３乃至Ｓ９２５の代わりにステップＳ９５０乃至Ｓ９５２を実行する点において第１の実施の形態と異なる。
【０１４３】
メモリコントローラ３００は、ステップＳ９２２の後、部分多項式のインデックスｋをＦ０で除算し、商ｋ０と余りｆ０とを得る（ステップＳ９５０）。そして、メモリコントローラ３００は、商ｋ０、ｋ１と余りｆ１とのそれぞれに対応する剰余多項式Ｖ１、Ｖ２およびＶ３を剰余多項式テーブル４１３および４１４から取得する（ステップＳ９５１）。メモリコントローラ３００は、部分多項式Ａｋ（ｘ）と、剰余多項式Ｖ１、Ｖ２およびＶ３とを乗算し（ステップＳ９５２）、ステップＳ９２６を実行する。
【０１４４】
このように、本技術の第３の実施の形態によれば、除算回路４００は、共通因数の分解により生成される３つの因数のそれぞれに対応する剰余をテーブルに保持するため、テーブルを格納する記憶部の容量をさらに削減することができる。
【０１４５】
＜４．第４の実施の形態＞
第１の実施の形態では多項式選択部４１０が、入力多項式が入力された順番を示すインデックスｋを生成していたが、入力多項式の入力順が入れ替わると、インデックスｋが共通因数の次数に対応する値にならないことがある。この場合には、インデックスｋと、次数との関係を示す関数を用いてインデックスｋを次数に置き換えればよい。第４の実施の形態の除算回路４００は、インデックスｋを次数に置き換える点において第１の実施の形態と異なる。
【０１４６】
図２３は、第４の実施の形態における除算回路４００の一構成例を示すブロック図である。第４の実施の形態の除算回路４００は、マッピング部４４０をさらに備える点において第１の実施の形態と異なる。
【０１４７】
第４の実施の形態の多項式選択部４１０は、入力多項式の入力順、すなわち、部分多項式を選択した順番を示すインデックスｋを生成してマッピング部４４０に供給する。
【０１４８】
マッピング部４４０は、インデックスｋを、次数に応じた値ｋ'に置き換えて指定部４１２に供給するものである。ここで、ｋ'は、共通因数の次数ｎｋ'を項数ｎにより割った値である。マッピング部４４０は、ｋとｋ'との対応関係を示す関数π（ｋ）を使用して、ｋをｋ'に置き換える。
【０１４９】
例えば、最初に、次数が最大の入力多項式が選択され、２番目に、次数が最小の入力多項式が選択される場合について考える。項数ｎは５であり、次数が最大の入力多項式の共通因数の次数は「２４５」であり、次数が最小の入力多項式の共通因数の次数は「０」であるものとする。この場合には、「０」のインデックスｋを「４９」（＝２４５／５）のインデックスｋ'に置き換え、「１」のインデックスｋを「０」に置き換える関数π（ｋ）が用いられる。このように、インデックスｋを次数に応じた値ｋ'に置き換えることにより、入力多項式の入力順が入れ替わっても、除算回路４００は、適切な値の剰余を算出することができる。
【０１５０】
第４の実施の形態の指定部４１２は、共通因数ｘ＾（ｎｋ'）、すなわちｘ＾｛ｎπ（ｋ）｝を次の式により分解する。
ｘ＾（ｎｋ'）＝ｘ＾｛ｎ（ｋ０Ｆ０＋ｆ０）｝
＝ｘ＾（ｎｋ０Ｆ０）・ｘ＾（ｎｆ０）                ・・・式１９
【０１５１】
なお、第４の実施の形態の除算回路４００は、第２の実施の形態と同様に、レジスタ４１８に保持された加算結果を複数の分離多項式に分離してもよい。この場合には、多項式分離部４２０、多項式乗算器４２１および多項式加算器４２２がさらに設けられる。
【０１５２】
また、第４の実施の形態の除算回路４００は、第３の実施の形態と同様に、共通因数を３つ以上の因数に分解してもよい。この場合には、分解した個数と同数の剰余多項式テーブルが設けられ、分解した個数と同数の多項式乗算器が設けられる。
【０１５３】
図２４は、第４の実施の形態における除算処理の一例を示すフローチャートである。第４の実施の形態の除算処理は、ステップＳ９２３およびＳ９２４の代わりにステップＳ９６１およびＳ９６２を実行する点において第１の実施の形態と異なる。
【０１５４】
ステップＳ９２２の後、メモリコントローラ３００は、インデックスｋをｋ'に変換する（ステップＳ９６１）。そして、メモリコントローラ３００は、ｋ'を商ｋ０および余りｆ０に変換し（ステップＳ９６２）、ステップＳ９２４以降の処理を実行する。
【０１５５】
このように、本技術の第４の実施の形態によれば、除算回路４００は、入力順を示すインデックスｋを次数に置き換えるため、入力順が入れ替わっても、適切な剰余を算出することができる。
【０１５６】
なお、上述の実施の形態は本技術を具現化するための一例を示したものであり、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本技術の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本技術は実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０１５７】
また、上述の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disc）、メモリカード、ブルーレイディスク（Blu-ray（登録商標）Disc）等を用いることができる。
【０１５８】
なお、ここに記載された効果は必ずしも限定されるものではなく、本開示中に記載されたいずれかの効果であってもよい。
【０１５９】
なお、本技術は以下のような構成もとることができる。
（１）  それぞれが共通因数および部分多項式からなる複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、
前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、
前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、
前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、
前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、
前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、
前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部と
を具備する除算回路。
（２）前記多項式加算部は、前記供給された乗算結果の全てを加算した結果を２つの分離多項式に分離して当該２つの分離多項式の一方における共通因数に対する前記所定の除算により生じる剰余と前記一方における部分多項式とを乗算した結果に前記２つの分離多項式の他方を加算した結果を前記加算結果として供給する
前記（１）記載の除算回路。
（３）  前記第１因数および前記第２因数と異なる複数の第３因数のそれぞれについて前記第３因数に対する前記所定の除算により生じる剰余を第３の剰余として保持する第３剰余テーブルをさらに具備し、
前記指定部は、前記因数分解により生成される前記複数の第３の因数のいずれかをさらに指定し、
前記多項式乗算部は、前記指定された第３因数に対応する前記第３の剰余を前記第３の剰余テーブルからさらに取得して前記第１および第２の剰余とのそれぞれと前記供給された部分多項式とを乗算した結果にさらに前記第３の剰余を乗算する
前記（１）または（２）に記載の除算回路。
（４）各々が複数の第３因数からなる複数の第３因数群のそれぞれについて前記第３因数に対する前記所定の除算により生じる剰余を第３の剰余として保持する複数の第３剰余テーブルをさらに具備し、
前記指定部は、前記因数分解により生成される前記第３の因数を前記複数の第３因数群のそれぞれについてさらに指定し、
前記多項式乗算部は、前記指定された第３因数ごとに当該第３因数に対応する前記第３の剰余を前記第３の剰余テーブルからさらに取得して前記第１および第２の剰余とのそれぞれと前記供給された部分多項式とを乗算した結果にさらに前記第３の剰余の各々を乗算する
前記（１）または（２）に記載の除算回路。
（５）前記指定部は、前記共通因数の次数に応じた数値を所定の除数により除した商および余りを求め当該商に応じた次数の単項式と前記余りに応じた次数の単項式との一方を前記第１因数とし、他方を前記第２因数として指定する
前記（１）または（２）に記載の除算回路。
（６）前記入力多項式を選択した順番を示すインデックスと前記共通因数の次数との関係を示す所定の関数を使用して前記インデックスを前記次数に置き換えて前記指定部に供給するマッピング部をさらに具備し、
前記多項式選択部は、前記インデックスを生成して前記マッピング部に供給し、
前記指定部は、前記供給された次数の前記共通因数に対する因数分解により生成される前記複数の第１因数のいずれかと前記複数の第２因数のいずれかとを指定する
前記（１）から（５）のいずれかに記載の除算回路。
（７）前記入力多項式が選択されるたびに計数値を計数するカウンタをさらに具備し、
前記指定部は、前記計数値に応じた次数の前記共通因数に対する因数分解により生成される前記第１因数および第２因数を指定する
前記（１）から（５）のいずれかに記載の除算回路。
（８）それぞれが共通因数および部分多項式からなる複数の入力多項式を示すデータを保持するデータバッファと、
前記複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、
前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、
前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、
前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、
前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、
前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、
前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部と、
前記データと前記除算結果を示すパリティとを含む符号語を生成して出力する符号語生成部と
を具備する符号化装置。
（９）それぞれが共通因数および部分多項式からなる複数の入力多項式を示すデータとパリティとを含む受信語を保持するデータバッファと、
前記複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択部と、
前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定部と、
前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと、
前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルと、
前記入力多項式が選択されるたびに前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記第１および第２の剰余テーブルから取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算部と、
前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算部と、
前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算部と、
前記除算結果を示すビット列が前記パリティと一致するか否かにより前記受信語における誤りの有無を検出する誤り検出部と
を具備する復号装置。
（１０）多項式選択部が、それぞれが共通因数および部分多項式からなる複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択手順と、
指定部が、前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定手順と、
多項式乗算部が、前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルとから前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記入力多項式が選択されるたびに取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算手順と、
多項式加算部が、前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算手順と、
多項式除算部が、前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算手順と
を具備する除算回路の制御方法。
（１１）多項式選択部が、それぞれが共通因数および部分多項式からなる複数の入力多項式のいずれかを選択して当該選択した入力多項式内の前記部分多項式を供給する多項式選択手順と、
指定部が、前記入力多項式が選択されるたびに前記選択された入力多項式内の前記共通因数に対する因数分解により生成される複数の第１因数のいずれかと複数の第２因数のいずれかとを指定する指定手順と、
多項式乗算部が、前記第１因数ごとに当該第１因数に対する所定の除算により生じる剰余を第１の剰余として保持する第１の剰余テーブルと前記第２因数ごとに当該第２因数に対する前記所定の除算により生じる剰余を第２の剰余として保持する第２の剰余テーブルとから前記指定された第１因数に対応する前記第１の剰余と前記指定された第２因数に対応する前記第２の剰余とを前記入力多項式が選択されるたびに取得して当該取得した第１および第２の剰余のそれぞれと前記供給された部分多項式とを乗算して乗算結果を供給する多項式乗算手順と、
多項式加算部が、前記供給された乗算結果の全てを加算して加算結果を供給する多項式加算手順と、
多項式除算部が、前記加算結果に対して前記所定の除算を行って除算結果を出力する多項式除算手順と
をコンピュータに実行させるためのプログラム。
【符号の説明】
【０１６０】
１００  ホストコンピュータ
１０１  ユーザインターフェース
１０２、３０２  ＲＯＭ
１０３、３０３  ＲＡＭ
１０４、３０４  ＣＰＵ
１０５、３０５  バス
１０６  ストレージインターフェース
２００  ストレージ
３００  メモリコントローラ
３０１  ホストインターフェース
３０６  メモリインターフェース
３１０  ＥＣＣ処理部
３２０  符号化部
３２１、３３１  データバッファ
３２２  符号語生成部
３３０  復号部
３３２  誤り検出訂正部
４００、４０１  除算回路
４１０  多項式選択部
４１１  カウンタ
４１２、４３１  指定部
４１３、４１４、４３２  剰余多項式テーブル
４１５、４１６、４２１、４３３  多項式乗算器
４１７、４２２  多項式加算器
４１８  レジスタ
４２０  多項式分離部
４４０  マッピング部
４５０  多項式除算部
４５１  除算制御部
４５２  スイッチ
４５３  乗算器
４５４  フリップフロップ
４５５  加算器
５００  不揮発性メモリ
【図１】
2016004468.tif 000009
【図２】
2016004468.tif 000010
【図３】
2016004468.tif 000011
【図４】
2016004468.tif 000012
【図５】
2016004468.tif 000013
【図６】
2016004468.tif 000014
【図７】
2016004468.tif 000015
【図８】
2016004468.tif 000016
【図９】
2016004468.tif 000017
【図１０】
2016004468.tif 000018
【図１１】
2016004468.tif 000019
【図１２】
2016004468.tif 000020
【図１３】
2016004468.tif 000021
【図１４】
2016004468.tif 000022
【図１５】
2016004468.tif 000023
【図１６】
2016004468.tif 000024
【図１７】
2016004468.tif 000025
【図１８】
2016004468.tif 000026
【図１９】
2016004468.tif 000027
【図２０】
2016004468.tif 000028
【図２１】
2016004468.tif 000029
【図２２】
2016004468.tif 000030
【図２３】
2016004468.tif 000031
【図２４】
2016004468.tif 000032