特許ウォッチ

公開番号2024080211
公報種別公開特許公報(A)
公開日2024-06-13
出願番号2022193213
出願日2022-12-02
発明の名称演算回路、メモリシステムおよび制御方法
出願人キオクシア株式会社
代理人弁理士法人酒井国際特許事務所
主分類H03M 13/15 20060101AFI20240606BHJP(基本電子回路)
要約【課題】ガロア体の乗算を行うための回路規模の増加を抑制する。
【解決手段】演算回路は、ガロア体の元aおよび元bのAND演算の結果であるAND値を計算する。演算回路は、複数の相互に異なる(u,v)の組それぞれについて、AND値と、組ごとに異なる複数のテンソルをまとめた連結テンソルとに基づくXOR演算により、aの2^u乗とbの2^v乗との積であるa^(2^u)×b^(2^v)を計算する。
【選択図】図2
特許請求の範囲【請求項１】
ガロア体の元ａおよび元ｂのＡＮＤ演算の結果であるＡＮＤ値を計算し、
複数の相互に異なる（ｕ，ｖ）の組それぞれについて、前記ＡＮＤ値と、前記組ごとに異なる複数のテンソルをまとめた連結テンソルとに基づくＸＯＲ演算により、ａの２
ｕ
乗とｂの２
ｖ
乗との積であるａ＾（２
ｕ
）×ｂ＾（２
ｖ
）を計算する、
演算回路。
続きを表示（約 2,300 文字）【請求項２】
前記ガロア体は、要素数が２
ｍ
（ｍは２以上の整数）であり、
前記ガロア体の元は、値が０または１であるｍ個の成分を含むｍ次元ベクトルにより表され、
前記ｍ次元ベクトルの第ｉ成分（ｉは０≦ｉ≦ｍ－１を満たす整数）に対する複数の前記テンソルそれぞれは、前記第ｉ成分に対して定められるテンソルＴ
ｉ
と、２
ｕ
乗を表す線形演算Ｓ
ｕ
と、２
ｖ
乗を表す線形演算Ｓ
ｖ
と、を含む以下の（１）式により表される、
（Ｓ
ｖ
）
Ｔ
×Ｔ
ｉ
×Ｓ
ｕ
・・・（１）
請求項１に記載の演算回路。
【請求項３】
前記連結テンソルは、
前記ｍ次元ベクトルのｍ個の成分に対応してｍ個定められ、
前記ｍ次元ベクトルの前記第ｉ成分に対応する前記連結テンソルは、前記（１）式により表される複数の前記テンソルをまとめたテンソルである、
請求項２に記載の演算回路。
【請求項４】
前記ＡＮＤ値は、前記元ａのｍ個の成分と、前記元ｂのｍ個の成分と、のＡＮＤ演算の結果であるｍ×ｍ個の演算成分を含み、
複数の前記テンソルのそれぞれは、前記演算成分それぞれをＸＯＲ演算に用いるか否かを表すｍ×ｍ個のテンソル成分を含み、
前記テンソル成分によりＸＯＲ演算に用いることが表された前記演算成分を用いてＸＯＲ演算を行い、ａ＾（２
ｕ
）×ｂ＾（２
ｖ
）を計算する、
請求項２に記載の演算回路。
【請求項５】
前記連結テンソルは、
複数の前記テンソルのうち、ｊ番目（ｊは０≦ｊ≦Ｊ－１、Ｊは複数の前記テンソルの総数）の前記テンソルを１次元化したベクトルを第ｊ行の行ベクトルとするテンソルである、
請求項１に記載の演算回路。
【請求項６】
前記連結テンソルは、
複数の前記テンソルのうち、ｊ番目（ｊは０≦ｊ≦Ｊ－１、Ｊは複数の前記テンソルの総数）の前記テンソルを１次元化したベクトルを第ｊ行の行ベクトルとする変形前テンソルの２つ以上の行ベクトルのうち、２つ以上の対象列の値が１で共通する行ベクトルの前記対象列の値を０に変更し、前記変形前テンソルに前記対象列の値を１とした行ベクトルを追加したテンソルである、
請求項１に記載の演算回路。
【請求項７】
前記元ａおよび前記元ｂは、同じ元ｃであり、
前記元ｃおよび前記元ｃのＡＮＤ演算により前記ＡＮＤ値を計算し、
複数の相互に異なる（ｕ，ｖ）の組それぞれについて、前記ＡＮＤ値と前記連結テンソルとに基づくＸＯＲ演算により、ｃの２
ｕ
乗とｃの２
ｖ
乗との積であるｃ＾（２
ｕ
）×ｃ＾（２
ｖ
）を計算する、
請求項１に記載の演算回路。
【請求項８】
複数の前記テンソルは、ガロア体の原始多項式に対応するコンパニオン行列に基づいて決定される、
請求項１に記載の演算回路。
【請求項９】
誤り訂正符号で符号化されたデータを記憶する不揮発性メモリと、
請求項１に記載の演算回路を備えるメモリコントローラと、を備え、
前記メモリコントローラは、
前記不揮発性メモリから読み出された受信語を用いて、ガロア体の元である複数のシンドロームを計算し、
複数の前記シンドロームに含まれる第１シンドロームを元ａとし、複数の前記シンドロームに含まれる第２シンドロームを元ｂとして、前記演算回路を用いてａの２
ｕ
乗とｂの２
ｖ
乗との積であるａ＾（２
ｕ
）×ｂ＾（２
ｖ
）を計算し、
計算された積ａ＾（２
ｕ
）×ｂ＾（２
ｖ
）を係数に含む誤り位置多項式を用いて、誤り位置を計算し、
計算された前記誤り位置の誤りを訂正する、
メモリシステム。
【請求項１０】
不揮発性メモリを制御する制御方法であって、
誤り訂正符号で符号化されたデータを前記不揮発性メモリへ記憶し、
前記不揮発性メモリから前記データを受信語として読み出し、
前記不揮発性メモリから読み出された受信語を用いて、ガロア体の元である複数のシンドロームを計算し、
複数の前記シンドロームに含まれる第１シンドロームを元ａとし、複数の前記シンドロームに含まれる第２シンドロームを元ｂとして、前記元ａおよび前記元ｂのＡＮＤ演算の結果であるＡＮＤ値を計算し、
複数の相互に異なる（ｕ，ｖ）の組それぞれについて、前記ＡＮＤ値と、前記組ごとに異なる複数のテンソルをまとめた連結テンソルとに基づくＸＯＲ演算により、ａの２
ｕ
乗とｂの２
ｖ
乗との積であるａ＾（２
ｕ
）×ｂ＾（２
ｖ
）を計算し、
計算された積ａ＾（２
ｕ
）×ｂ＾（２
ｖ
）を係数に含む誤り位置多項式を用いて、誤り位置を計算し、
誤り位置多項式を用いて、誤り位置を計算し、
計算された誤り位置の誤りを訂正する、
ことを含む制御方法。

発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、演算回路、メモリシステムおよび制御方法に関する。
続きを表示（約 2,300 文字）【背景技術】
【０００２】
メモリシステムでは、ＮＡＮＤ型フラッシュメモリ等のメモリに記憶するデータを保護するために、誤り訂正符号化されたデータがメモリに記憶される。このため、メモリに記憶されたデータを読み出す際には、メモリから読み出された誤り訂正符号化されたデータ（受信語とも称される。）を復号して誤り訂正符号化される前のデータを復元する。
【０００３】
誤り訂正符号に関する技術では、ガロア体（有限体）の乗算が行われる場合がある。例えば、誤り訂正符号の例であるＢＣＨ（Bose-Chaudhuri-Hocquenghem）符号の復号では、メモリから読み出された受信語（読み出し系列）からシンドロームが計算され、シンドロームから誤り位置多項式の係数が計算される。シンドロームはガロア体の要素である。このため、誤り位置多項式の係数を計算するときに、シンドロームの乗算、すなわち、ガロア体の乗算が行われる場合がある。誤り訂正可能なビット数（ｔビット、ｔは２以上の整数）が増加するに従い、必要なガロア体の乗算の個数が増加する。すなわち、乗算に用いられる演算回路（乗算器）の規模が増加する。
【先行技術文献】
【特許文献】
【０００４】
米国特許第１０，０９７，２０７号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の実施形態は、ガロア体の乗算を行うための回路規模の増加を抑制することができる演算回路を提供することを目的とする。
【課題を解決するための手段】
【０００６】
実施形態の演算回路は、ガロア体の元ａおよび元ｂのＡＮＤ演算の結果であるＡＮＤ値を計算する。演算回路は、複数の相互に異なる（ｕ，ｖ）の組それぞれについて、ＡＮＤ値と、組ごとに異なる複数のテンソルをまとめた連結テンソルとに基づくＸＯＲ演算により、ａの２
ｕ
乗とｂの２
ｖ
乗との積であるａ＾（２
ｕ
）×ｂ＾（２
ｖ
）を計算する。
【図面の簡単な説明】
【０００７】
実施形態に係るメモリシステムのブロック図。
実施形態に係る復号部のブロック図。
シンドロームおよび誤り位置多項式の計算手順の概要を示す図。
シンドロームと誤り位置多項式との関係の例を示す図。
ガロア体ＧＦ（２
4
）の元のベクトル表現の例を示す図。
コンパニオン行列の例を説明する図。
テンソルＴ
ｉ
の求め方の一例を示す図。
テンソルＴ
０
の求め方の具体例を示す図。
テンソルＳの求め方の一例を示す図。
テンソルＳの求め方の具体例を示す図。
乗算を書き換える手順を説明するための図。
連結テンソルの求め方の例を説明するための図。
連結テンソルの例を示す図。
ＸＯＲの共有化の例を説明するための図。
ＸＯＲ演算の共有化手法の一例を示す図。
演算部の構成例を示す図。
回路の比較例を示す図。
演算部の他の構成例を示す図。
図１８の演算部によるＸＯＲ演算に対応する連結テンソルの例を示す図。
図１８に対応する回路の比較例を示す図。
復号処理のフローチャート。
【発明を実施するための形態】
【０００８】
以下に添付図面を参照して、この発明にかかる演算回路の好適な実施形態を詳細に説明する。以下では、誤り訂正符号の復号時にガロア体の乗算を行う演算回路を含むメモリシステムを例に説明する。演算回路を用いる構成はこの例に限られず、どのようなシステム（装置、機器）であってもよい。例えば、誤り位置を計算するときにガロア体の乗算を行うメモリシステム、および、暗号処理時にガロア体の乗算を行うシステムなどに対しても、以下に説明する演算回路を適用することができる。
【０００９】
まず、本実施形態に係るメモリシステムについて、図面を参照して詳細に説明する。図１は、本実施形態に係るメモリシステムの概略構成例を示すブロック図である。図１に示すように、メモリシステム１は、メモリコントローラ１０と不揮発性メモリ２０とを備える。メモリシステム１は、ホスト３０と接続可能であり、図１ではホスト３０と接続された状態が示されている。ホスト３０は、例えば、パーソナルコンピュータ、携帯端末などの電子機器であってよい。
【００１０】
不揮発性メモリ２０は、データを不揮発に記憶する不揮発性メモリであり、例えば、ＮＡＮＤ型フラッシュメモリ（以下、単にＮＡＮＤメモリという）である。以下の説明では、不揮発性メモリ２０としてＮＡＮＤメモリが用いられた場合を例示するが、不揮発性メモリ２０として３次元構造フラッシュメモリ、ＲｅＲＡＭ（Resistive Random Access Memory）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）等のＮＡＮＤメモリ以外の記憶装置を用いることも可能である。また、不揮発性メモリ２０が半導体メモリであることは必須ではなく、半導体メモリ以外の種々の記憶媒体に対して本実施形態を適用することも可能である。
（【００１１】以降は省略されています）

関連特許