(57)【要約】  意図する用途に固有の特性を有する符号を生成するための方法および装置であって、この方法は、群の集合から１つの群を選択するステップと、環の集合から１つの群を選択するステップと、選択した群および選択した環から群環を形成するステップと、生成すべき符号の所望する特性に基づき、群環から生成子要素ｕを選択するステップと、選択した生成子要素ｕを符号生成プロセスに入力し、対応するチェック要素を得るステップとを備える。
2008541540.tif 000002
【特許請求の範囲】
【請求項１】
ａ）群の集合から１つの群を選択するステップと、
ｂ）環の集合から１つの環を選択するステップと、
ｃ）前記選択した群および前記選択した環から群環を形成するステップと、
ｄ）生成すべき符号の所望する特性に基づき、前記群環から生成子要素ｕを選択するステップと、
ｅ）前記選択した生成子要素ｕを符号生成プロセスに入力し、対応するチェック要素を得るステップとを備えた、意図する用途に固有の特性を有する符号を生成するための方法。
【請求項２】
生成すべき前記符号は、非周期的群のゼロ因子符号であり、前記生成子要素を選択する前記ステップは、ゼロ因子要素を選択することを含む、請求項１に記載の方法。
【請求項３】
生成すべき前記符号は、単位符号であり、前記生成子要素を選択する前記ステップは、単位要素を選択することを含む、請求項１に記載の方法。
【請求項４】
生成すべき前記符号は、低密度パリティチェック（ＬＤＰＣ）符号であり、生成子要素ｕを選択する前記ステップは、前記群のサイズと比較して少数の非ゼロ係数を有する要素を選択することを含む、請求項１に記載の方法。
【請求項５】
前記符号の特性は、符号距離を含む、請求項１から４のいずれかに記載の方法。
【請求項６】
前記符号の特性は、符号長さを含む、請求項１から５のいずれかに記載の方法。
【請求項７】
前記符号の特性は、符号レートを含む、請求項１から６のいずれかに記載の方法。
【請求項８】
ｆ）前記生成子要素ｕおよび前記チェック要素を対応するペアの符号化マトリックスおよび復号化マトリックスに写像するステップを更に含む、請求項１から７のいずれかに記載の方法。
【請求項９】
ｇ）前記生成された符号の評価を実行するために符号化マトリックスおよび復号化マトリックスを使用することを含む、請求項８に記載の方法。
【請求項１０】
前記評価は、符号レートを計算することを含む、請求項９に記載の方法。
【請求項１１】
前記評価は、符号ガースを計算することを含む、請求項９または１０記載の方法。
【請求項１２】
前記評価は、符号距離を計算することを含む、請求項９から１１のいずれかに記載の方法。
【請求項１３】
ステップａ）およびｂ）を実行するときに、前記評価の結果をフィードバックとして使用して、前記ステップａ）からｅ）を繰り返すステップｈ）を更に含む、請求項９から１２のいずれかに記載の方法。
【請求項１４】
前記ステップａ）およびｂ）は、前記選択プロセスにおいて前記生成した符号を使用するようになっている前記システムの特性を使用することを含む、請求項９から１２のいずれかに記載の方法。
【請求項１５】
前記ステップａ）およびｂ）は、前記選択プロセスにおいて、ユーザの入力を使用することを含む、請求項９から１２のいずれかに記載の方法。
【請求項１６】
前記ステップａ）およびｂ）は、前記選択プロセスにおいて、予め定められた選択基準を使用することを含む、請求項９から１２のいずれかに記載の方法。
【請求項１７】
前記ステップｄ）は、前記選択された生成子要素ｕがゼロ因子要素であるかどうかを判断するステップｉ）を更に含む、請求項１から１６のいずれかに記載の方法。
【請求項１８】
前記ステップｄ）は、
ｉｉ）前記選択された生成子要素ｕが前記ゼロ因子要素である場合に、ｕｖ＝０となるように群環の整合要素ｖを決定するステップ、または
ｉｉｉ）前記生成子要素ｕが単位要素である場合に、ｕｖ＝１となるように群環の整合要素ｖを決定するステップを更に含む、請求項１７に記載の方法。
【請求項１９】
前記ステップｅ）は、前記整合要素ｖを前記符号生成プロセス内に入力するステップを更に含む、請求項１８に記載の方法。
【請求項２０】
ａ）群の集合から１つの群を選択するための手段と、
ｂ）環の集合から１つの環を選択するための手段と、
ｃ）前記選択した群および前記選択した環から群環を形成するための手段と、
ｄ）生成すべき符号の所望する特性に基づき、前記群環から生成子要素ｕを選択するための手段と、
ｅ）前記選択された生成子要素ｕを受け取り、対応するチェック要素を生成するよう適合された符号生成子とを備えた、意図する用途に固有の特性を有する符号を生成するための装置。
【請求項２１】
生成すべき前記符号は、非周期的群のゼロ因子符号であり、生成子要素ｕを選択するための前記手段は、ゼロ因子要素を選択するよう適合されている、請求項２０に記載の装置。
【請求項２２】
生成すべき前記符号は、単位符号であり、生成子要素を選択するための前記手段は、単位要素を選択するよう適合されている、請求項２０に記載の装置。
【請求項２３】
生成すべき前記符号は、低密度パリティチェック（ＬＤＰＣ）符号であり、生成子要素ｕを選択するための前記手段は、前記群のサイズと比較して少数の非ゼロ係数を有する要素を選択するよう適合されている、請求項２０に記載の装置。
【請求項２４】
前記符号の特性は、符号距離を含む、請求項１から２３のいずれかに記載の装置。
【請求項２５】
前記符号の特性は、符号長さを含む、請求項１から２４のいずれかに記載の装置。
【請求項２６】
前記符号の特性は、符号レートを含む、請求項１から２５のいずれかに記載の装置。
【請求項２７】
ｆ）前記生成子要素ｕおよび前記チェック要素を対応するペアの符号化マトリックスおよび復号化マトリックスに写像する手段を更に含む、請求項１から２６のいずれかに記載の装置。
【請求項２８】
ｇ）符号化マトリックスおよび復号化マトリックスを使用して前記生成された符号を評価するための生成符号アナライザを更に含む、請求項２７に記載の装置。
【請求項２９】
前記生成された符号のアナライザは、符号レートを計算するよう適合されている、請求項２８に記載の装置。
【請求項３０】
前記生成された符号のアナライザは、符号ガースを計算するよう適合されている、請求項２８または２９に記載の装置。
【請求項３１】
前記生成された符号のアナライザは、符号距離を計算するよう適合されている、請求項２８から３０のいずれかに記載の装置。
【請求項３２】
群を選択するための前記手段および環を選択するための前記手段は、前記生成された符号のアナライザの結果をフィードバックとして使用するよう適合されている２８から３１のいずれかに記載の装置。
【請求項３３】
群を選択するための前記手段および環を選択するための前記手段は、前記生成された符号が使用するために意図されている前記システムの特性を使用するようになっている、請求項２８から３１のいずれかに記載の装置。
【請求項３４】
群を選択するための前記手段および環を選択するための前記手段は、前記選択プロセスにおいて、ユーザの入力を使用するよう適合されている、請求項２８から３１のいずれかに記載の装置。
【請求項３５】
群を選択するための前記手段および環を選択するための前記手段は、前記選択プロセスにおいて、予め定められた選択基準を使用するよう適合されている、請求項２８から３１のいずれかに記載の装置。
【請求項３６】
前記群環から生成子要素を選択するための前記手段は、前記選択された生成子要素ｕがゼロ因子要素であるかどうかを判断する手段を含む、請求項１から３５のいずれかに記載の装置。
【請求項３７】
前記群環から生成子要素を選択するための前記手段は、
前記選択された生成子要素が前記ゼロ因子要素である場合に、ｕｖ＝０となるように群環の整合要素ｖを決定するよう適合され、かつ、
前記選択された生成子要素ｕが単位要素である場合に、ｕｖ＝１となるように群環の整合要素ｖを決定するよう適合されている、請求項３６に記載の装置。
【請求項３８】
前記符号生成子は、前記整合要素ｖを受け取り、前記符号生成プロセス内の前記整合要素を使用するように適合されている、請求項３７に記載の装置。
【請求項３９】
通信システムにおいて、通信チャンネルを通して送信するためのデータを符号化するための、請求項１から１４のいずれかに記載の方法によって生成される符号の使用方法。
【請求項４０】
データ記憶媒体に記憶するためにデータを符号化するための、請求項１から１４のいずれかに記載の方法によって生成される符号の使用方法。
【請求項４１】
前記データは、デジタルデータである、請求項２９または３０に記載の使用方法。
【請求項４２】
前記生成された要素ｕが公開鍵として働き、前記チェック要素が秘密鍵として働く、公開鍵暗号化方法を使って暗号化されているメッセージを符号化するための、請求項１から１４のいずれかに記載の方法によって生成される符号の使用方法。
【請求項４３】
ａ）生成すべき符号の所望する特性に基づき、非特異的マトリックスから生成子要素を選択するステップと、
ｂ）前記選択された生成子要素を符号生成プロセスに入力し、対応するチェック要素を得るステップとを備えた、意図する用途に固有の特性を有する符号を生成する方法。
【請求項４４】
ｃ）前記生成子要素および前記チェック要素を対応するペアの符号化マトリックスおよび復号化マトリックスに写像するステップを更に含む、請求項４３に記載の方法。
【請求項４５】
本明細書に実質的に説明し、添付図面に示したように符号を生成する方法。
【請求項４６】
実質的に本明細書に説明したような、請求項２９から３１のいずれかに記載の使用方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は符号に関し、特に誤り訂正符号および誤り検出符号を含む符号の生成に関するものである。
【背景技術】
【０００２】
符号化理論、特に誤り訂正符号および誤り検出符号を使用することは、ソース符号化変調および暗号化と共に最近の通信システムのうちの核心的要素の１つであり、誤り訂正符号および誤り検出符号を使用することは、通信システムにおける基本的ツールとなっている。
【０００３】
時間および空間を通した通信中にデータを保護するために誤り訂正符号が使用される。これら符号は、ノイズのあるチャンネル、例えば無線通信チャンネル、光ファイバーまたはイーサネット（登録商標）リンク、デジタルケーブルまたはデジタル加入者回線（ＤＳＬ）、衛星通信チャンネルまたはディープ宇宙通信チャンネルを通して空間を横断するようにデータを安全に送信するのに使用できる。チャンネルにノイズがあることは、送信中にデータが破壊される可能性があることを意味する。例えば記憶媒体、例えば標準ハードドライブ、ディスク、ＣＤ、ＤＶＤおよびコンピュータメモリにあるデータを時間経過しても劣化しないことを保証することにより、時間に対しデータ通信を保護するのに誤り検出符号も使用される。
【０００４】
誤り制御のための最も基本的な形式の符号化の１つは、二進データのストリングにパリティチェックビットを加えることである。このことによって、１つの誤りが生じたことを検出できる。しかしながら、２つの誤りが生じた場合、受信者は誤りが起こったことを知ることはできない。一般に、符号によって提供される、誤り制御ビットをより多くする結果、誤り検出／訂正能力はより良好となるが、送信ごとの情報のコンテントはより少なくなる。従って、誤り取り扱い能力と情報コンテントとをバランスできる符号を生成することが望ましい。
【０００５】
現在使用されるほとんどの符号は周期的符号である。多項式符号と時々称されるこれら周期的符号は、周期的群のうちのゼロ因子群環符号である。群環は一般に代数的構造であり、所定の群Ｇおよび所定の環Ｒに対し、群環ＲＧは次の式
【数１】
2008541540.tif 000003
で示されるフォームのすべての要素から成り、有限数のα（ｇ）だけがゼロでない。Ｇ＝｛ｇ１，ｇ２，．．．，ｇｎ｝が有限である場合、ＲＧは、すべての
【数２】
2008541540.tif 000004
から成る。
【０００６】
従って、群環ＲＧはＧの要素から成る基底および分散法則と共にＧの要素のたたみ込みタイプの乗算によって決定される乗算により、Ｒを通したモジュールと見なすことができる。任意のモジュールのサブモジュールは、それ自身が１つのモジュールであるモジュールの非空部分集合である。Ｒが体であるとき、ＲＧは群代数と称されることが多い。
【０００７】
群環はマトリックスの環として見なすことができることが知られている。
【０００８】
環Ｒを通した群Ｇの群環ＲＧは、Ｒに対するＲＧマトリックスと称される所定のマトリックスの環である。
【０００９】
代数的に、かつより正確には、Ｇが次数ｎの群であり、Ｒが環である場合、Ｒを通したｎ×ｎのマトリックスの環の部分環に対し群環ＲＧを写像する単写φ：ＲＧ→Ｒｎ×ｎが存在する。Ｒｎ×ｎの部分環は、ＲＧマトリックスの集合である。ｕ∈ＲＧである場合、Ｕによりφ（ｕ）を示す。すなわち対応する大文字によりφの下のｕの像を示す。また、ＵがＲＧマトリックスである場合、φの下の逆像をｕ、すなわち対応するより低いケースの文字で表す。ＲＧ−マトリックスの最初の行（または列）が一旦既知であれば、マトリックス全体も既知であることに注目することが重要である。従って、群環のうちの要素Ｕおよび群の乗算を仮定した場合、対応するマトリックスＵを決定できる。
【００１０】
周期的符号として、かかる重要な符号、例えばＢＣＨ符号、リードソロモン符号、ゴーレー符号およびハミング符号を挙げることができる。現在の多くの符号は一般に周期的群環のゼロ因子から得られるマトリックスから生成される。
【００１１】
現在の符号は、累積符号でもあり、本発明の目的は非累積符号を提供することにある。
【００１２】
特に符号をランダムに生成した場合の現在の方法は、チェックマトリックスによって符号を生成することが多く、生成マトリックスを提供することは計算上不可能となり得る。本発明の別の目的は、代数的かつ同時にチェックマトリックスと生成マトリックスを提供することにある。
【００１３】
本発明の別の目的は、低密度パリティチェック（ＬＤＰＣ）符号、セルフデュアルタイプの符号および直交符号を含む多くの、より新規で有効な興味ある符号を生成するための方法を提供することにある。
【発明の開示】
【課題を解決するための手段】
【００１４】
本発明は、
ａ）群の集合から１つの群を選択するステップと、
ｂ）環の集合から１つの群を選択するステップと、
ｃ）前記選択した群および前記選択した環から群環を形成するステップと、
ｄ）生成すべき符号の所望する特性に基づき、前記群環から生成子要素ｕを選択するステップと、
ｅ）前記選択した生成子要素ｕを符号生成プロセスに入力し、対応するチェック要素を得るステップとを備えた、意図する用途に固有の特性を有する符号を生成するための方法を提供するものである。
【００１５】
生成すべき前記符号は、非周期的群のゼロ因子符号でよく、前記生成子要素を得る前記ステップは、ゼロ因子要素を選択することを含む。
【００１６】
生成すべき前記符号は、単位符号でよく、前記生成子要素を得る前記ステップは、単位要素を選択することを含む。
【００１７】
生成すべき前記符号は、低密度パリティチェック（ＬＤＰＣ）符号でよく、前記生成子要素ｕを得る前記ステップは、前記群のサイズと比較して少数の非ゼロ係数を有する要素を選択することを含む。
【００１８】
前記符号の特性は、符号の距離および／または符号の長さおよび／または符号のレートを含むことができる。
【００１９】
本方法は、
ｆ）前記生成子要素および前記チェック要素を対応するペアの符号化マトリックスおよび復号化マトリックスに写像するステップを更に含むことができる。
【００２０】
好ましくは、この方法は、
ｇ）前記生成された符号の評価を実行するために符号化マトリックスおよび復号化マトリックスを使用することを含むことができる。
【００２１】
前記評価は、符号レートを計算することの外に、符号距離および／または符号ガースを計算することを含むことができる。
【００２２】
この方法は、ステップａ）およびｂ）を実行するときに、前記評価の結果をフィードバックとして使用して、前記ステップａ）〜ｅ）を繰り返すステップを更に含むことができる。
【００２３】
前記ステップａ）およびｂ）は、上記ステップに加え、またはその代わりに、前記選択プロセスにおいて前記生成した符号を使用するようになっている前記システムの特性を使用することを含むことができる。前記ステップａ）およびｂ）は、上記ステップに加え、またはその代わりに、前記選択プロセスにおいて、予め定めた選択基準を使用することを含むことができる。
【００２４】
前記ステップｄ）は、
前記選択された生成子要素ｕがゼロ因子要素であるかどうかを判断するステップを更に含むことができる。
【００２５】
前記ステップｄ）は、
前記選択された生成子要素ｕが前記因子要素である場合に、ｕｖ＝０となるように群環の整合要素ｖを決定するステップ、または
前記生成子要素ｕが単位要素である場合に、ｕｖ＝１となるように群環の整合要素ｖを決定するステップを更に含むことができる。
【００２６】
前記ステップｅ）は、前記整合要素ｖを前記生成プロセス内に入力するステップを更に含むことができる。
【００２７】
本発明は、
群の集合から１つの群を選択するための手段と、
環の集合から１つの環を選択するための手段と、
前記選択した群および前記選択した環から群環を形成するための手段と、
生成すべき符号の所望する特性に基づき、前記群環から生成子要素ｕを選択するための手段と、
前記選択された生成子要素ｕを受け取り、対応するチェック要素を生成するよう適合された符号生成子とを備えた、意図する用途に固有の特性を有する符号を生成するための装置を更に提供する。
【００２８】
本発明の１つの特徴によれば、生成すべき前記符号は、非周期的群のゼロ因子符号から得られ、生成子要素ｕを選択するための前記手段は、ゼロ因子要素を選択するようできる。
【００２９】
本発明の別の特徴によれば、生成すべき前記符号は、単位符号から得られ、前記生成子要素を選択するための前記手段は、単位要素を選択するようできる。
【００３０】
本発明の更に別の特徴によれば、生成すべき前記符号は、低密度パリティチェック（ＬＤＰＣ）符号とすることができ、生成子要素ｕを選択するための前記手段は、前記群のサイズと比較して少数の非ゼロ係数を有する要素を選択するようにできる。
【００３１】
前記符号の特性は、符号距離および／または符号長さおよび／または符号レートを含むことができる。
【００３２】
本装置は、前記生成子要素および前記チェック要素を対応するペアの符号化マトリックスおよび復号化マトリックスに写像する手段を更に含むことができる。
【００３３】
好ましくは、本装置は、符号化マトリックスおよび復号化マトリックスを使用して前記生成された符号を評価するための生成符号アナライザを更に含むことができる。
【００３４】
前記生成された符号のアナライザは、符号レートを計算するようにでき、前記生成された符号のアナライザは、符号レートを計算することに加え、またはその代わりに、符号のガースおよび／または符号距離を計算するようにできる。
【００３５】
１つの特徴によれば、群を選択するための前記手段および環を選択するための前記手段は、前記生成された符号のアナライザの結果をフィードバックとして使用するようにできる。
【００３６】
群を選択するための前記手段および環を選択するための前記手段は、前記生成した符号を使用するようになっている前記システムの特性を使用するようにできる。
【００３７】
群を選択するための前記手段および環を選択するための前記手段は、前記選択プロセスにおいて、ユーザの入力を使用するようにできる。
【００３８】
群を選択するための前記手段および環を選択するための前記手段は、前記選択された生成子要素ｕがゼロ因子要素であるかどうかを判断する手段を含む。
【００３９】
前記群環から生成子要素を選択するための前記手段は、更に
前記選択された生成子要素ｕが前記因子要素である場合に、ｕｖ＝０となるように群環の整合要素ｖを決定するかまたは
前記生成子要素ｕが単位要素である場合に、ｕｖ＝１となるように群環の整合要素ｖを決定するようになっている。
【００４０】
前記符号生成子は、前記整合要素ｖを受信し、前記整合要素を前記符号生成プロセス内に入力するようになっていることが好ましい。
【００４１】
本発明の方法によって生成される符号は、通信システムにおいて、通信チャンネルを通して送信するためのデータを符号化するために使用できることが理解できよう。
【００４２】
本発明の方法によって生成される符号は、さらに、データ記憶媒体に記憶するためのデータを符号化するために使用できることが理解できよう。
【００４３】
かかる使用法では、前記データは、デジタルデータである。
【００４４】
本発明の方法によって生成された符号は、暗号化されたメッセージを符号化するために使用でき、前記生成された要素ｕは公開鍵として働き、前記チェック要素は秘密鍵として働く、公開鍵暗号化方法を使って暗号化されたメッセージを符号化されている。
【００４５】
本発明の方法により、生成された新しい符号に対し、生成マトリックスおよびチェックマトリックスを容易に得ることが可能となることが理解できよう。群環符号の多くは群環と所定のマトリックスとの間の誘導された関係を使って、マトリックスに関連して示すことができるので、このことを行うことができる。
【００４６】
本発明の態様で群環符号を使用することにより、新規なセルフデュアル符号および新規な低密度パリティチェック（ＬＤＰＣ）符号を誘導することも可能となる。これによって、本発明以前に存在しなかったこれらタイプの新規な符号を本方法によって代数的に構築することが可能となる。
【００４７】
「所定の次数」までの符号を発生できるというこれら利点は、制限がない。例えば本発明によれば、前記群環から生成子要素を選択し、例えば生成された符号を調査により良好な距離を有すると証明された符号にすることを保証できる。かかる符号は、短い群環要素を使って誘導されたＬＤＰＣ符号とすることができる。別の例では、前記群環から生成子要素を選択し、例えばスピードを改善するために、大きなレートが必要な場合に、生成される符号が必要なレートを有することを保証することもできる。同様に符号距離に関し、符号誤り時間を最小にするように、符号が長い距離を有することが好ましい場合もある。
【００４８】
本発明の方法は、群環マトリックスから符号を生成することだけに限定されていないことが理解できよう。本方法は任意の可逆的マトリックスと共に使用できる。
【００４９】
従って、本発明は、
ｉ）生成すべき符号の所望する特性に基づき、非特異的マトリックスから生成子要素を選択するステップと、
ｉｉ）前記選択した生成子要素を符号生成プロセスに入力し、対応するチェック要素を得るステップとを備えた、意図する用途に固有の特性を有する符号を生成する方法を更に提供する。
【００５０】
当業者であれば理解できるように、本発明は、方法、データ処理システムまたはコンピュータプログラム製品として具現化できる。従って、本発明は全体がハードウェアの実施例、全体がソフトウェアの実施例またはソフトウェアの特徴とハードウェアの特徴を組み合わせた実施例の形態をとり得る。更に、本発明はメディア内で具現化された、コンピュータで読み取り可能なプログラム符号手段を有する、コンピュータで読み取り可能な記憶メディア上の、コンピュータプログラム製品の形態をとり得る。
【００５１】
本発明の実施例を例として示す添付図面を参照し、以下、本発明について説明する。しかしながら、本発明は多くの異なる形態で実施でき、本明細書に記載した実施例だけに限定されるとみなしてはならない。むしろこれら実施例は、発明の開示を完全にするように記載したものであり、これら実施例は本発明の範囲を当業者に完全に説明するためのものである。
【実施例】
【００５２】
本発明は、符号を生成し、使用するための新規な方法およびシステムを提供する。生成すべき符号の１つの可能性のある用途を、デジタル通信および記憶システムにおける誤り訂正または誤り検出とすることができる。
【００５３】
本発明の方法によって生成される新しいタイプの符号は、群環と称される代数構造におけるゼロ因子および単位である。
【００５４】
これら群環における単位およびゼロ因子は、マトリックスを得るために使用される。これらマトリックスは、符号化プロセスにおいて使用される生成マトリックスおよび復号化プロセスで使用されるパリティチェックマトリックスである。
【００５５】
（群環符号）
ＲＧを、環Ｒを通した群Ｇの群環であるとする。Ｒは体となることがかなり多いが、このように限定されているわけではない。Ｒが体である場合、ＲＧを群の代数と称すことが多い。群環はＲを通したモジュールと称される。１つの部分モジュールはそれ自身が１つのモジュールである非空部分集合である。
【００５６】
Ｇ＝｛ｇ１，ｇ２，．．．，ｇｎ｝とする。この集合は、環Ｒを通したモジュールＲＧの基底となる。ｕ∈ＲＧとする。
【００５７】
図１は、本発明の１つの特徴に従った符号生成方法のステップを示す。
【００５８】
この方法は、群選択プロセス１２０と、群環形成ステップ１２７に対して群と環の適当な組み合わせを決定できるようにする環選択プロセス１２４とを含む。双方の選択プロセスは、符号生成のための適当な群と環との組み合わせを決定するのを助けるための、ユーザ入力１１０、１１１で予め定められた選択基準１１２、１１３またはフィードバック基準１１４、１１５を含むことができる。
【００５９】
群と環との適当な組み合わせを一旦決定すると、これら群と環とを群環形成プロセス１２７に入力する。一旦群環を形成すると、次は所定の基準に従って前記群環１２８から特定の要素を選択しなければならない。
【００６０】
次に、生成要素として知られる選択された要素を符号生成プロセス１３０に入力し、対応するチェック要素を生じさせる。次に本発明に従い、符号化マトリックス１３２のように、対応するペアの符号化マトリックス１３２および復号化マトリックス１３６に、前記生成要素およびチェック要素を写像することができる。この符号生成ステップ１３０は、本明細書に説明する本発明を示す。
【００６１】
所定のケースでは、符号アナライザ１４０により、前記符号化マトリックス１３２および復号化マトリックス１３６を使用し、符号レート、ガースおよび距離のような特性の計算を含む、生成された符号の検査および経験的な評価が可能となる。これらデータは、フィードバック基準１１４を介して符号生成の次のサイクルに提供され、よって所定の実施例における符号生成プロセスの選択的な精緻化を可能にする。
【００６２】
別の実施例では、符号に基づく誤り訂正および／または暗号化を使用し、アクティブな通信リンクまたはデータインターフェースからフィードバックを誘導できる。かかる実施例では、フィードバック基準１１４、１１５は前記通信リンクまたはデータインターフェースの特性に応じて変えることもできる。従って、本明細書に開示する発明はリンク／インターフェースの条件の変化に応答して符号をダイナミックに生成できる。
【００６３】
満足できる特性を有する符号の最終集合を一旦決定すると、これら符号は従来の通信および暗号化システムでは使用のために出力できる。
【００６４】
図２を参照し、以下、要素選択ステップ１２８および符号生成ステップ１３０について詳細に説明する。まず、群環を形成するステップ１２７は、群環の要素も決定することに注目する。後に数学的な詳細について説明する。複素群環構造を使用する本発明の所定の実施例では、主要な要素選択プロセス１２８の前に、所定の要素を除くためのステップ１２７の後で別のプロセスのステップが必要となる場合がある。しかしながら、本発明の最も有効な実施例では、群環が既知のアプリケーションにより、ステップ１２０および１２４のもとで入力として使用された群および環から決定される、特定の特性を有する比較的小さい集合の要素を通常生成する。
【００６５】
図２は、群環が群代数であるケースにおける要素選択プロセスおよび符号生成プロセスを示す。このプロセスは、デジタルデータを使用する最新の通信システムまたはデジタル情報処理システムに対して特に有効である。使用される環は一般に、最も広い適用性を有する
【数３】
2008541540.tif 000005
となるが、所定の特別な通信システムまたは情報処理システムに対しては、他の体も適す。
【００６６】
要素選択プロセス１２８は、ステップ１２７に形成された群環の要素の集合から生成要素１２８−２を選択する別のサブステップを含む。この要素ｕがゼロ因子要素１２８−４であるかどうかを判断するために、この要素ｕを検査しなければならない。この要素が、ゼロ因子要素である場合、ｕｖ＝０となるように群環の整合要素ｖを定めることが可能である（１２８−６）。次に、符号生成の次のステップ１３０に、要素ｕがゼロ因子である事実およびこれら要素を入力する。
【００６７】
選択された要素がゼロ因子要素でなければ、群環を群代数に限定する実施例を説明することを条件に、選択された要素を単位要素としなければならない。この場合、ｕｖ＝１となるように群環の整合要素を決定する。ステップ１２８−８において、上記とは異なり、これら要素を符号生成ステップ１３０へ入力する。
所定の実施例ではアプリケーションによっては、要素をゼロ因子または単位のいずれかに限定することが望ましいことがあることに注目する。多くのケースではこのことは、ステップ１２０と１２４との間で選択された群および環に基づいて自然に行われる。
【００６８】
次に、符号生成ステップ１３０について説明する。このステップは、主に単写φ：ＲＧ→Ｒｎ×ｎによる対応する群環マトリックスへの群環要素ｕおよびｖの写像１３０−２に主に依存する。後に、いくつかの実際の実行例について説明する。実際には、ステップ１２０で選択された群の特性により、この単写または写像のフォームについて決定するが、ステップ１３０−１の下で計算により実現しなければならない。本発明の実施例が、例えば次数ｎの正２面体群のような群の単一ファミリーに限定されている場合、この単写は単一入力パラメータｎを有する単一のコンピュータスクリプトとして実現できる。しかしながら、より複雑な実施例では、当業者に知られているＭＡＴＥＭＡＴＩＣＡ（登録商標）、ＭＡＰＬＥ（登録商標）またはＧＡＰのようなシンボリックな処理プログラム、またはスタンドアローンコンピュータプログラム、またはこれら双方の組み合わせを使って、この単写を実施しなければならないことがある。
ステップ１３０−２の後で、符号生成子は群環要素ｕに対応するマトリックスを符号化マトリックス１３０−４として、更に群環要素ｖに対応するマトリックスを復号要素１３０−５として、出力しなければならない。これら出力１３２および１３６、並びに生成された符号（ゼロ因子または単位）の形式は、符号生成プロセス１３０の出力を形成する。
【００６９】
本発明の方法を実施する例
次数８の正２面体群を使用したゼロ因子符号の例
次数８の正２面体群Ｄ８は、非累積的であり、その要素は｛１，ｙ，ｙ２，ｙ３；ｘ，ｘｂ，ｘｂ２，ｘｂ３｝であり、ここでｙ４＝１；ｘ２＝１，ｙｘ＝ｘｙ−１である。この群ＧのＲＧマトリックスは、次の式で示されるフォームを有する。
【数４】
2008541540.tif 000006
ここで、Ａ、Ｂは次のフォームを有する（Ａは巡回的であり、Ｂはハンケルタイプである）。
【数５】
2008541540.tif 000007
係数に対する選択は多く、例えば要素ｕ＝ｂ２＋ａ＋ａｂ＋ａｂ２およびｖ＝１＋ｂ＋ｂ３＋ａｂ３を選択すると仮定する。次に、
【数６】
2008541540.tif 000008
に対してｕｖ＝０となる。このことは、Ａにおいてｐ＝０＝ｑ＝ｓ，ｒ＝１とし、Ｂにおいてａ＝１＝ｂ＝ｃ，ｄ＝０とすることに対応する。
【００７０】
これによって、次のようにｕに対応するＲＧマトリックスが得られる。
【数７】
2008541540.tif 000009
【００７１】
Ｐは、ゼロ因子であり、明らかに階数４も有する。
【数８】
2008541540.tif 000010
【００７２】
従って、
【数９】
2008541540.tif 000011
とすることにより、符号化Ｒ４→Ｒ８を行うことができる。Ｃはｃｖ＝０の場合およびその場合に限り、コードワードである。マトリックスのフォームでは、Ｐの頂部部分Ｗを生成マトリックスと見なすことができ、Ｑ、Ｕｔの第２部分の転置マトリックスは、チェックマトリックスとなる。このコードは距離ｄ＝３、長さ８および次元４を有する。
【００７３】
より一般的には、次の例で説明するようなコンピュータ代数パッケージを使用して正２面体群の群環の構造を実現することもできる。
【００７４】
双周期的単位を使ったＬＤＰＣ符号の正２面体群の例
次数２ｎの正２面体群：Ｄ２ｎ＝＜ａ，ｂ：ａ２，ｂｎ＝１，ａｂ＝ｂ−１ａ＞とみなす。ここでｎを任意に大きくできることに留意されたい。上記のように、ａ、ｂをとることにより、次の双周期的単位
【数１０】
2008541540.tif 000012
を得る。この場合、関係から、この単位はｕ＝１−ｂ＋ｂｎ−１＋ａｂ−ａｂｎ−１である。この単位では、５つの要素しかなく、その逆数はｕ−１＝１＋ｂ−ｂｎ−１−ａｂ＋ａｂｎ−１である。
【００７５】
次のように、コンピュータ代数パッケージＧＡＰにおいて、この群の群環を構築できる。
【００７６】
＃このＧＡＰプログラムは次数ｎの正２面体群の群環を構築する。
＃ｎを最初に選択するが、偶数としなければならない。素数ｐに対しｎ＝２ｐ
＃のフォームを有するようにこのｎを選択するが、このことは一般に必要では
＃ない。
＃本例では体は、Ｆであり、まず最初にこれを定めなければならない。そこで
＃２つの要素の二進の体であるＦ＝ＧＦ（２）をとるが、その他の可能性も存
＃在する。
＃要素ｆは双周期的単位であるとき、その逆数が存在することが分かっている
＃ので、この要素ｆを選択する。
Ｆ：＝ＧＦ（２）；
＃ｎを定義したことを確認する。
ｎ；
ＤＮ：＝ＤｉｈｅｄｒａｌＧｒｏｕｐ（ｎ）；
ＲＤＭ：＝ＦｒｅｅＭａｇｍａＲｉｎｇ（Ｆ，ＤＮ）；
ｅｍｂ：＝Ｅｍｂｅｄｄｉｎｇ（ＤＮ，ＲＤＭ）；；
ｇｅｎｓ：＝Ｌｉｓｔ（ＧｅｎｅｒａｔｏｒｓＯｆＧｒｏｕｐ（ＤＮ），ｘ−＞ｘ＾ｅｍｂ）；；
ｘ：＝ｇｅｎｓ［１］；
ｙ：＝ｇｅｎｓ［２］；
ｏｎｅ：＝Ｉｄｅｎｔｉｔｙ（ＲＤＭ）；
ｕ：＝ｏｎｅ−ｙ＋ｙ＾（ｎ／２−１）＋ｘ＊ｙ−ｘ＊ｙ＾（ｎ／２−１）；
＃理論から、ｕの逆数は次のフォームを有することが分かっている。
ｕｉｎｖｅｒｓｅ：＝ｏｎｅ＋ｙ−ｙ＾（ｎ／２−１）−ｘ＊ｙ＋ｘ＊ｙ＾（ｎ／２−１）；
＃ｕｉｎｖｅｒｓｅはｕの逆数であることをチェックする。
ｕ×ｕｉｎｖｅｒｓｅ；＃答えは１でなければならない。
【００７７】
＃ｕが次のコマンドにより逆数を有するか有しないかが分からない場合に、
＃ｕの逆数を求めることもできる。
ｕｉｎｖｅｒｓｅ：＝Ｉｎｖｅｒｓｅ（ｕ）；
＃ｕと、この逆数を求めれば、単位符号生成マトリックスを構築し、次のよう
＃にチェックに進むことができる。
【００７８】
［１］における結果を適用することにより、次のようにｕ、Ｕのマトリックスが示される。
【数１１】
2008541540.tif 000013
【００７９】
前に説明したように、この単位から誘導された（２ｎ，ｎ）符号
【数１２】
2008541540.tif 000014
を検討する。この符号の生成マトリックスは、Ｕの頂部部分である（Ａ，Ｂ）であり、ｎ×２ｎマトリックスである。このマトリックスは自動的に階数ｎを有する。
ｕ−１のマトリックスは次のとおりである。
【数１３】
2008541540.tif 000015
【００８０】
符号
【数１４】
2008541540.tif 000016
のチェックマトリックスは上記垂直線の右側までのマトリックスの転置マトリックスである（Ｄｔ，Ｃｔ）である。
これらマトリックスは疎マトリックスである。
上記のことは全ての任意の環Ｒに対して成立する。特に二進の体である
【数１５】
2008541540.tif 000017
を検討する。ここで、ｕ−１＝ｕであり、Ａ＝Ｃであり、Ｂ＝Ｄであることに注目されたい。これを符号化Ｒｎ→Ｒ２ｎと見なす場合、（２ｎ，ｎ）符号を有し、この場合、生成マトリックスは、（Ａ，Ｂ）であり、チェックマトリックスは、（Ｂｔ，Ａｔ）の転置マトリックスである。この符号は、セルフチェックマトリックスでもあるＬＤＰＣ符号である。
【００８１】
（群環構造を使った単位誘導周期符号の構築の例）
次のＭＡＰＬＥプログラムは、周期的ＬＤＰＣ単位で誘導された符号を構築する。Ａから生成マトリックスが得られ、Ｂからチェックマトリックスが得られる。
＃ｎを入力する；ｎ＞１２であることを確認する。ｎが＞１２でなければ、ｆ
＃ｈに対する式を変えなければならない。逆数を得ることを確認し、素数ｐに
＃対し、ｎ＝２ｐとする。
ｎ；＃ｎを既に入力したことをチェックする。
ｍ：＝ｔｒｕｎｃ（（ｎ）／２）；
ｆ：＝ｇ＾ｎ−１；
ｆｈ：＝１＋ｇ＾２＋ｇ＾５＋ｇ＾（ｍ）＋ｇ＾（ｍ＋４）；
ｊ：＝Ｇｃｄｅｘ（ｆｈ，ｆ，ｇ，’ｓ’，’ｔ’）ｍｏｄ  ２；
ｆｈｉｎｖｅｒｓｅ：＝ｓ；
ｉｄ：＝ｒｅｍ（ｆｈ＊ｆｈｉｎｖｅｒｓｅ，ｆ，ｇ）；
ｗｉｔｈ（ＬｉｎｅａｒＡｌｇｅｂｒａ）；
【００８２】
＃「ｃｉｒｃ＿ｐｏｌｙ．ｍａｐ」を読み出す；この関数は次のように示される。
ｃｉｒｃ＿ｐｏｌｙ：＝ｐｒｏｃ（ｆ，ｇ，ｎ）
ｄｅｓｃｒｉｐｔｉｏｎ“ｆｏｒｍ  ａ  ｃｉｒｃｕｌａｎｔ  ｍａｔｒｉｘ  ｆｒｏｍ  ｔｈｅ  ｐｏｌｙｎｏｍｉａｌ  ｉｎ  ｚ２”；
ｌｏｃａｌ  ｉ，ｊ，Ｍ，ｔｅｒｍ；
Ｍ：＝Ｍａｔｒｉｘ（ｎ＋１，ｎ＋１）；
ｆｏｒ  ｉ  ｆｒｏｍ  ０  ｔｏ  ｎ  ｄｏ
ｆｏｒ  ｊ  ｆｒｏｍ  ０  ｔｏ  ｎ  ｄｏ
Ｍ［ｊ＋１，１＋（（ｉ＋ｊ）ｍｏｄ（ｎ＋１））］：＝ｃｏｅｆｆ（ｆ，ｇ，ｉ）；
ｏｄ；
ｏｄ；
ｒｅｔｕｒｎ  Ｍ；
ｅｎｄ  ｐｒｏｃ；
Ａ：＝ｃｉｒｃ＿ｐｏｌｙ（ｆｈ，ｇ，ｎ−１）；
Ｂ：＝ｃｉｒｃ＿ｐｏｌｙ（ｆｈｉｎｖｅｒｓｅ，ｇ，ｎ−１）；
【００８３】
＃Ａから生成マトリックスを取り出し、Ｂからチェックマトリックスを取り出
＃す。符号レートは、使用するＡの部分によって決定する。
＃単位群符号の説明を参照されたい。
＃以下、ｎが偶数のとき、１／２であり、ｎが奇数のとき、１／２−１／２ｎ
＃であるｒａｔｅ（レート）＝ｍ／ｎを使用する。
＃これらマトリックスを使用するとき、これらをｍｏｄ２のマトリックスに変
＃換しなければならない。
ＧｅｎＣｏｄｅ：＝Ａ［１．．ｍ，１．．ｎ］；
ＣｈｅｃｋＣｏｄｅｌ：＝Ｂ［１．．ｎ，（ｍ＋１）．．ｎ］；
ＣｈｅｃｋＣｏｄｅ：＝Ｔｒａｎｓｐｏｓｅ（ＣｈｅｃｋＣｏｄｅ１）；
【００８４】
（ＬＤＰＣ符号を得るための交番タイプの単位の使用）
周期的群環内の交番単位から良好なＬＤＰＣ符号の別のソースを得ることができる。交番単位の完全な説明については、［３］を参照されたい。
これら単位は、次数ｎの周期的群における次のようなフォーム
【数１６】
2008541540.tif 000018
であり、ここで、ｎが奇数である場合、２＜ｃ＜ｎであり、（ｃも奇数とするように）（ｃ，２ｎ）＝１である。
【００８５】
ここでｃが小さいとき、ｇｃ（ｘ）はｎ−と比較して少数の非ゼロ係数しか有しなく、ｇｃ（ｘ）−１は、より多くの係数を有する。
【００８６】
次に、ｇｃ（ｘ）に対応するマトリックスは、各行および列に少数の要素しか有しなく、ｇｃ（ｘ）−１に対応するマトリックスは、一般に各行および列にｎ／２の要素の次数しか有しない。
【００８７】
従って、単位ｇｃ（ｃ）−１から適当な我々の生成マトリックスを取り出し、ｇｃ（ｘ）から我々のチェックマトリックスを取り出す。
【００８８】
ユークリドアルゴリズムを使って交番単位の逆数を得ることができるので、（少ない重みから選択できる）所定の交番単位に対し、逆数を極めて迅速に構築できる。
【００８９】
次のプログラムは単位交番要素を生成し、これら要素から単位符号を誘導する。
＃このプログラムは周期群環の交番単位を構築し、その逆数を探し、生成マト
＃リックスおよびチェックマトリックスを生成する対応するＲＧマトリックス
＃を解く。ｎは周期的群の次数であり、ｃは２＜ｃ＜ｎ（ここで（ｃ，２ｎ）
＃＝１である）となるような数である。体に対する制限はなく、この体を整数
＃に対する１つの符号と見なすことができる。このアルゴリズムは極めて高速
＃であり、大きな数字を使用できる。
ｎ；＃ｎを入力したことを確認する。
ｃ；＃ｃを入力したことを確認する。
ｇ：＝ｓｕｍ（（−ｘ）＾ｉ，ｉ＝０．．．ｃ−１）；
ｆ：＝ｘ＾ｎ−１；
ｊ：＝ｇｃｄｅｘ（ｇ，ｆ，ｘ，’ｓ’，’ｔ’）；
ｇｉｎｖｅｒｓｅ：＝ｓ；
ｉｄ：＝ｒｅｍ（ｇ＊ｇｉｎｖｅｒｓｅ，ｆ，ｘ）；
Ａ：＝ｃｉｒｃ＿ｐｏｌｙ（ｇ，ｘ，ｎ−１）；
Ｂ：＝ｃｉｒｃ＿ｐｏｌｙ（ｇｉｎｖｅｒｓｅ，ｘ，ｎ−１）；
＃Ａはこのケースにおけるチェックマトリックスを示し、Ｂは生成マトリック
＃スを示す。
＃ｃがｎと比較して小さい場合、ＬＤＰＣ符号を得る。
【００９０】
例えばｎ＝１７、ｃ＝３である場合、
【数１７】
2008541540.tif 000019
となる。チェックマトリックスは、各行および列において３つの要素しか有しない。
【００９１】
（その他のＬＤＰＣ符号の例）
その他の単位およびゼロ因子を検討することにより、別のＬＤＰＣ符号を同じように構築できる。次の方法が興味ある方法である。
ＬＤＰＣ符号が少なくとも６以上の大きなガースを有することが有効である。次に、ｘによって生成された次数ｍの周期的群Ｃｍを検討し、直積Ｇ＝Ｃｍ×Ｃ２（ここで、Ｃ２はｙによって生成されたものである）を形成する。３つの要素の体に対するＧのうちの群環ＧＦ（３）Ｇを形成する。要素ｆ（ｘ）＝１＋ｘ２−ｘ＊ｙ＋ｘ２＊ｙはこの群環において逆数を有する。対応するマトリックスの次元が大きくなるように、この要素を構築する。ｆ（ｘ）に対応するマトリックスは疎となるが、その逆数は疎とならない。すなわち逆数は各行および列においてｍ／２よりも多い要素を有する。生成マトリックスを得るために逆数を使用し、チェックマトリックスを得るためにｆ（ｘ）を使用する単位群環符号を形成するために、上記のように次元ｍの符号を形成する。
【００９２】
次のプログラムは、群環、対応する単位およびその逆数を生成する。
＃このプログラムは次数ｎ、Ｃ＿ｎの周期的群および次数２、Ｃ＿２の周期
＃的群の直積の群環を構築するためのＧＡＰプログラムである。この場合、Ｆ
＃をＧＦ（２）と見なす。すなわち２つの要素上の二進の体と見なす。必要と
＃されるサイズｎをまず入力し、記憶しなければならない。群環内の要素ｆを
＃選択し、その要素が１つの単位であるかどうかを見るためにテストする。
＃これは、「ｆｉｎｖｅｒｓｅ：＝Ｉｎｖｅｒｓｅ（ｆ）；」であるコマンドである。  ＃逆数が存在する場合、これを見つけ、次に他の場所で説明したように、
＃単位群環符号を探すように進む。他の検討事項から、
＃下記のように構築したｆの逆数が常に存在する。
Ｆ：＝ＤＦ（３）；
ｎ；
Ｃ＿ｎ：＝ＣｙｃｌｉｃＧｒｏｕｐ（ｎ）；
Ｃ＿２：＝ＣｙｃｌｉｃＧｒｏｕｐ（２）；
ＤＰ：＝ＤｉｒｅｃｔＰｒｏｄｕｃｔ（Ｃ＿ｎ，Ｃ＿２）；
ＲＭ：＝ＦｒｅｅＭａｇｍａＲｉｎｇ（Ｆ，ＤＰ）；
ｅｍｂ：＝Ｅｍｂｅｄｄｉｎｇ（ＤＰ，ＲＭ）；
ｇｅｎｓ：＝Ｌｉｓｔ（ＧｅｎｅｒａｔｏｒｓＯｆＧｒｏｕｐ（ＤＰ），ｘ−＞ｘ＾ｅｍｂ）；
ｓ：＝Ｓｉｚｅ（ｇｅｎｓ）；
ｘ：＝ｇｅｎｓ［１］；
ｙ：＝ｇｅｎｓ［ｓ］；
ｏｎｅ：＝Ｉｄｅｎｔｉｔｙ（ＲＭ）；
ｆ：＝ｏｎｅ＋ｘ＾２−ｘ＊ｙ＋ｘ＾４＊ｙ；
ｆｉｎｖｅｒｓｅ：＝Ｉｎｖｅｒｓｅ（ｆ）；
【００９３】
この群環に対するＲＧマトリックスは、次のフォームを有する。
【数１８】
2008541540.tif 000020
ここで、Ａ、Ｂは巡回マトリックスであり、（ＲＧマトリックスは周期的群環に対応する。）ｆに対する群環のフォームを見ると、Ａは最初の行（１，０，１，０，．．．，０）を有する巡回マトリックスであり、Ｂは最初の行（０，１，０，−１，０，．．．，０）を有する巡回マトリックスである。
【００９４】
ｆは疎であるので、チェックマトリックスを得るようｆを取り出し、（２ｎ，ｎ）符号の生成マトリックス、例えばＣを得るために、その逆数を取り出す。このケースにおけるｆの逆数は疎でないので、ｎ個の非ゼロの係数の次数を有する。従って、符号Ｃのチェックマトリックスは（Ｂｔ｜Ａｔ）となる。このチェックマトリックスは各行および列において、多くて４つの非ゼロエントリーを有し、符号はＬＤＰＣ符号となる。
証明された次元
【００９５】
本明細書では好ましい実施例を開示したが、本発明の概念、範囲および要旨に入る多くの変形が可能であり、本願を検討すれば、当業者にはこれら変形例は明らかであろう。
【００９６】
（数学的記述）
（群環符号の定義）
Ｗを群環ＲＧのサブモジュールとする。Ｗの群環符号化は、ＷからＲＧへの写像であり、この場合、
【数１９】
2008541540.tif 000021
であり、ＲＧでは固定されたｕとなる。
【数２０】
2008541540.tif 000022
である場合、これは左側の群環符号化であるが、
【数２１】
2008541540.tif 000023
である場合、右側の群環符号化となる。群環符号は群環符号化の像である。
したがって、群環符号は｛ｕｘ：∀ｘ∈Ｗ，ｕ（固定）∈ＲＧ｝または｛ｘｕ：∀ｘ∈Ｗ，ｕ{固定}∈ＲＧ]．となる。
【００９７】
一般に、
【数２２】
2008541540.tif 000024
は異なる。すべてのｘに対してｘｕ＝ｕｘであれば、この符号｛ｘｕ｝（または｛ｕｘ｝）は累積的であり、そうでない場合、この符号は非累積的と称すことができる。
【００９８】
ｕがゼロ因子であるとき、符号はゼロ因子（ＲＧ）符号であり、ｕが１つの単位であるとき、符号は単位（ＲＧ）符号となる。非周期的群のうちの群環のゼロ因子符号および単位符号について検討する。Ｒが群環ごとの体であるとき、ＲＧ内の群環符号はゼロ因子符号または単位符号となる。
【００９９】
Ｗがｎ未満の次元を有するケースについて検討する。多くのケースでは、Ｗはあるｒ＜ｎに対し、ｇ１，ｇ２，．．．，ｇｒによって生成されたモジュールとなる。しかしながら、Ｗが１≦ｔ＜ｎかつ｛ｉ１，ｉ２，．．．，ｉｔ｝の場合のｇｉ１，ｇｉ２，．．．，ｇｉｔによって生成されるモジュールである場合、｛１，２，．．．，ｎ｝の部分集合も有効となる。Ｗはサブモジュールであり、イデアルではないことに留意されたい。
【０１００】
（前の既知の符号との接続。）これら新しい符号は、表面に生じ、前の既知の符号よりも実施にかかる時間がより長くかかるが、このようなケースはない。既に注目したように、ＲＧマトリックスが既知であれば、マトリックスの第１行も既知であり、このことは、この符号を実施する時間を大幅に短縮するように働く。前の符号は、写像β：Ｒｒ→Ｒｎ（ここでｒ＜ｎ）を使用する。群環符号のマトリックスフォームでは、
【数２３】
2008541540.tif 000025
によって示される写像Ｆｎ×ｎ→Ｆｎ×ｎを有する。次に、Ｘは第１行のうちの最後のｎ−ｒエントリーのうちの各々に対し、エントリー０を有するＲＧマトリックスであり、Ｘはその第１行によって決定される。ＸＵはＲＧマトリックスでもあるので、これは第１行によって決定される。したがって、写像βおよびαは実施するのに同じ回数の計算および同じ時間が必要となる。
【０１０１】
・新しい低密度パリティチェック（ＬＤＰＣ）チェック符号の生成にはこの群環方法によっても容易となる。
・セルフデュアル符号は、群環内の要素として解釈が容易であるので、この方法による生成が容易である。
【０１０２】
これら特定の符号は重要なアプリケーションを有し、現在まで生成が困難であった。
【０１０３】
（群環ゼロ因子符号）
ＲＧにおいて、ｕｖ＝０（ここでｕ≠０かつｖ≠０）を仮定する。Ｇの要素を｛ｇ１，ｇ２，．．．，ｇｎ｝と仮定し、Ｗをｇ１，ｇ２，．．．，ｇｒが生成したモジュールであるとする。Ｗがｇｉ１，ｇｉ２，．．．，ｇｉｒによって生成されたモジュールであるケースも同様であり、以下、同じように取り扱う。次に、ゼロ因子群環符号を次のように示す。
【数２４】
2008541540.tif 000026
【０１０４】
次の要素のベクトル
【数２５】
2008541540.tif 000027
を仮定し、
【数２６】
2008541540.tif 000028
とすることにより、このベクトルを符号化し、
【数２７】
2008541540.tif 000029
によって符号化を示す。ｃがコードワードであれば、明らかにｃｖ＝０である。したがって、ｖはチェック要素であり、Ｖはチェックマトリックスである。
【０１０５】
ｒ≦階数Ｕと仮定できる。ｒ＝階数Ｕであるケースは、特別に重要であり、このケースによってフル階数生成子およびチェックマトリックスが得られる。
【０１０６】
次に、Ｕは階数ｒを有し、Ｖは階数ｎ−ｒを有すると仮定する。次に、Ｖｙ＝０である場合、かつその場合に限り、ｙはコードワードとなる。Ｖがｎ−ｒ未満の階数を有する場合、ＲＧマトリックスＶ０＝Ｖ，Ｖ１，Ｖ２，．．．，Ｖｔ（ここでｔ＜ｎ−ｒ）が存在するので、ｉ＝０，１，．．．，ｔに対し、Ｖｉｙ＝０の場合およびこの場合に限り、ｙはコードワードとなる。多くのケースでは、ｔ＝０の場合の階数ｎ−ｒのＶを探すことができる。マトリックスの既知の特性およびこれらＲＧマトリックスＵ、Ｖの構造からこのようになる。
【０１０７】
（ゼロ因子符号の一般的な例としての正２面体符号）
次数８の正２面体群を使ったゼロ因子符号の一例を例に関する章に示す。
長さ２ｎおよび次元ｎの一般的な正２面体符号の構造は次のとおりである。
次数２ｎの正２面体群Ｇ＝Ｄ２ｎの要素を｛１，ｂ，ｂ２，．．．，ｂｎ−１，ａ，．．．，ａｂｎ−１｝とリストすることができる。次に、ｕ＝１＋ａ＋ａｂ＋．．．＋ａｂｎ−２およびｖ＝ｂ＋ｂ２＋．．．＋ｂｎ−１＋ａｂｎ−１を設定すると、ｕｖ＝０であることが証明される。
次数２ｎの正２面体群、Ｄ２ｎは、ＲＧ行列
【数２８】
2008541540.tif 000030
（ここで、Ａは巡回マトリックスであり、Ｂはハンケルタイプの行列である）を有する。Ａ＝Ｉｎとし、Ｂを次のように見なす。
【数２９】
2008541540.tif 000031
【０１０８】
階数Ｐをｎと見ることは容易である。マトリックスＰは群環要素ｕに対応するＲＧマトリックスである。
【０１０９】
Ｐを
【数３０】
2008541540.tif 000032
を通したマトリックスと見なす。マトリックスＱはｖから発見するので、ＰＱ＝０である。この場合、Ｑを得るためにＰ内の各０を１に置換し、Ｐ内の各１を０に置換することに留意されたい。
【０１１０】
これによって、次の式が得られる。
【数３１】
2008541540.tif 000033
【０１１１】
Ｑは、群環要素ｖに対応するマトリックスである。
【０１１２】
次にＰＱ＝０であり、Ｑは、チェックマトリックスを与える。Ｑも階数ｎを有するので、可能なフルの階数を有する。
【０１１３】
次に、Ｐによって示される符号化
【数３２】
2008541540.tif 000034
を検討する。生成マトリックス（Ａ，Ｂ）はｎ×ｎであり、チェックマトリックスであるＥｔもｎ×ｎである。この符号は長さ２ｎおよび次元ｎを有し、レートはｎ／（２ｎ）＝１／２である。
【０１１４】
セルフデュアル正２面体符号を検討する次の章も参照されたい。
【０１１５】
セルフデュアルタイプの符号
【０１１６】
【数３３】
2008541540.tif 000035
を群環内の１つの要素と見なし、Ｕを対応するＲＧマトリックスと見なす。
【数３４】
2008541540.tif 000036
（ここで、α’ｉは、Ｕ、Ｕｔの転置マトリックスの第１行の、順の要素である）を定義する。Ｕが対称的である場合、明らかにｕｔ＝ｕであり、この場合、ｕも対称的であると称す。ｇの係数が群Ｇのうちのすべての要素ｇに対し、ｕ内の係数ｇ−１に等しい場合およびその場合に限り、ｕは対称的であると容易に見なす。このことは容易な条件であるが、大きな限定ではない。
【０１１７】
セルフデュアル群環符号は次の符号化
【数３５】
2008541540.tif 000037
（ここで、ｕはｕｕｔ＝０を満足する）によって示される符号である。ｕが対称的である場合、セルフデュアル群環符号に対する条件はｕ２＝０であることである。
【０１１８】
例えばｕ２＝０である場合、およびこの場合に限り、ｕによって示される群環符号はセルフチェックである。
【０１１９】
次に新しいセルフデュアル符号を生成することは容易である。
【０１２０】
フォーム
【数３６】
2008541540.tif 000038
（ここで、Ａ、Ｂはｎ×ｎマトリックスである）のＲＧマトリックスを有する群環要素を検討する。この要素は、Ａ、Ｂの双方が巡回マトリックスである次数ｎの周期的群の直積のケースに対するものとするか、またはＡが巡回マトリックスであり、Ｂがハンケルタイプのマトリックスである次数２ｎの正２面体群のケースに対するものであるとすることができる。
【０１２１】
Ａ＝Ｉｎとし、ＢがＢ２＝Ｉを満たす場合、
【数３７】
2008541540.tif 000039
となる。次に、符号を次元ｎのうちの１つおよび生成マトリックス（Ａ，Ｂ）を有する長さ２ｎと見なすことができ、Ｐ２＝０であるので、チェックマトリックス（Ａ，Ｂ）ｔも有する。Ｂも対称的であれば、この符号はセルフデュアル符号となる。
【０１２２】
ｎが偶数であり、Ｂ２＝Ｉである場合に、
【数３８】
2008541540.tif 000040
を通したｎ×ｎの巡回対称マトリックスＢの一例は、次のフォーム
【数３９】
2008541540.tif 000041
のうちの１つである。
【０１２３】
ｎ＝４のとき、これによってハミング符号が得られる。
【０１２４】
ｎが偶数であり、Ｂ２＝Ｉである場合の、ハンケルタイプのマトリックスの一例は、次のフォーム
【数４０】
2008541540.tif 000042
のうちの１つである。
【０１２５】
ハンケルタイプのマトリックスは自動的に対称的である。
【０１２６】
Ｐ２＝０である場合、
【数４１】
2008541540.tif 000043
を通して（Ｐ＋Ｉ）（Ｐ＋Ｉ）＝Ｉである。これにより、Ｐに対する式内でＢをＰ＋Ｉに置換し、Ａをアイデンティティ２ｎ×２ｎマトリックスに置換することにより、更にセルフデュアル符号を構築することが可能となる。こうして、例えば１からスタートするかかる符号の無限シーケンスを作成し続けることができる。
【０１２７】
第１の行として、０で終了するシーケンス１，０，１，１，０，０，１，１，１，０，０，０，．．．を有するマトリックスとしてＢを検討する。Ｂを巡回マトリックスとして見なすか、ハンケルタイプのマトリックスとして見なす。Ｂのサイズを２ｎ＝ｍ（ｍ−１）と仮定し、
【数４２】
2008541540.tif 000044
を通して作業する。次にＢ２ｎ＝Ｉとし、次のマトリックス
【数４３】
2008541540.tif 000045
（ここで、Ａ＝Ｉ２ｎでありＣ＝Ｂｎである）はＰ２＝０を満足する。これによって写像
【数４４】
2008541540.tif 000046
とみなすとき、セルフチェック符号が得られる。例えばｍ＝３のとき、（１２，６，４）符号が得られる。他の値のｍに対して良好な距離特性を有する新しい符号が得られる。
【０１２８】
（群環単位の符号）
群環における単位を見ることによって、新規で、かつ有効な符号も得られる。
この方法は、符号を構築するための新規な完全な方法である。前の方法はほとんどのケースではゼロ因子周期的符号が得られた。
このタイプの符号化は暗号化と符号化が共に必要とされるときに特に有効である。
【０１２９】
ｕを群環ＲＧにおける単位と仮定する。ここで、｜Ｇ｜＝ｎであり、Ｇ＝｛ｇ１，ｇ２，．．．，ｇｎ｝である。まず、Ｗ内の要素が次のフォーム
【数４５】
2008541540.tif 000047
となるようにｇ１，ｇ２，．．．，ｇｒ（ここでｒ＜ｎ）によって生成されたモジュールであると見なす。Ｗ＝｛ｇｉ１，ｇｉ２，．．．，ｇｉｔ｝が同様である状況について、更に以下のように取り扱う。
【数４６】
2008541540.tif 000048
により符号化を行うと、ＷからＲＧへの写像が得られるので、この写像はＲｒからＲｎへの写像となる。
【０１３０】
符号化が
【数４７】
2008541540.tif 000049
によって示されると仮定する。このケースの
【数４８】
2008541540.tif 000050
も同様である。ｃは
【数４９】
2008541540.tif 000051
の場合、およびその場合に限り、コードワードとなる。すなわちｃｕ−１内のｇｒ＋１，．．．ｇｎがゼロの場合、およびその場合に限り、コードワードとなる。
【０１３１】
これら単位群環を符号と称す。次に、生成マトリックスおよびチェックマトリックスをどのように得るかについて説明する。
【０１３２】
ｗ、ｕ−１をＲＧマトリックス（ｗｉｊ）および（ｕｉｊ）とそれぞれ見なす場合、ｇｒ＋１，．．．ｇｎの係数を見ると、次の条件を有する。
【数５０】
2008541540.tif 000052
【０１３３】
これは、チェックマトリックスの条件となる。ｎ−ｒ個の条件が存在し、マトリックスを下に進み、０を選び出すような、より多くのチェック条件が存在するように見えるが、これらは上記のような結果である。
【０１３４】
これら符号は逆数で乗算すると、最初のｒ回のエントリーとして下のデータが得られ、他の（ｎ−ｒ）回のエントリーがチェックマトリックスを与えるという利点も有することに注目されたい。
【０１３５】
群環単位符号を次のようなマトリックスフォームで検討することもできる。群環におけるｕｖ＝１を仮定し、Ｕ、Ｖを、例えばｎ×ｎである対応するＲＧマトリックスとする。
【０１３６】
【数５１】
2008541540.tif 000053
を仮定する。
【０１３７】
次にＵＶ＝ＩはＡＤ＝０であることを意味する。上記記載に正確に対応する群環単位符号に対し、Ａは生成マトリックスであり、Ｄｔはチェックマトリックスであると理解する。Ｄｔがチェックマトリックスであることを理解するために、まずｘ＝ｕＡである場合、明らかにｘＤ＝０であることに注目する。他方、ｘＤ＝０であると仮定し、次のように一部の１×ｒベクトルｕに対し、ｘ＝ｕＡであることを示す。
【数５２】
2008541540.tif 000054
【０１３８】
次に、必要とされるように、ｘＣ＝ｕは１×ｒであり、ｘ＝ｘＶＵ＝ｕＡである。従って、Ｄｔは通常説明されるようなチェックマトリックスであり、Ｄｔｘｔ＝０である場合およびその場合に限り、ｘＤ＝０である場合およびその場合に限り、ｘはコードワードである。
【０１３９】
この単位群環から生成されるチェックマトリックスＤｔがフルの許容可能な階数を有することは、生成マトリックスであるＡが階数ｒを有すれば、Ｄｔ（およびＤ）が階数ｎ−ｒを有することを意味することに注目されたい。
【０１４０】
群環内の１つの単位に対応する特異でない行列から、符号および生成マトリックスおよびチェックマトリックスを構築するこの方法は、ＲＧマトリックスではなく、任意の非特異的（可逆的）マトリックスに対して働くことが理解できよう。この方法は、非特異的マトリックスから符号を生成するための新規な発明である。
【０１４１】
このように、次のように群環単位符号を構築できる。ＲＧを環Ｒ（通常、Ｒは体であるが、体でなくてもよい）を通した群Ｇの群環であるとする。ｕｖ＝１となるような、ＲＧの単位ｕおよびを要素ｖを探す。整数ｒを選択し、Ｗ＝｛ｇ１，ｇ２，．．．，ｇｒ｝（またはＷ＝｛ｇｉ１，ｇｉ２，．．．，ｇｉｒ｝−以下参照）と見なす。次に、単位符号は上記のものであり、ＵおよびＶから生成マトリックスおよびチェックマトリックスを得ることができる。
【０１４２】
ＲＧ内のどの要素もゼロ因子または単位のいずれかであり、特定の要素が単位またはゼロ因子であるかどうかを決定するためのアルゴリズムが存在することは、フィールドを通して既知となっている。
【０１４３】
このように、有効でもある整数
【数５３】
2008541540.tif 000055
を通して符号を構築できることにも注目されたい。望んでいることは、
【数５４】
2008541540.tif 000056
における単位であり、これらを構築するための方法は既知となっている。
【０１４４】
（他のサブモジュール）
Ｗが全ての
【数５５】
2008541540.tif 000057
の集合となるように、要素ｇｋ１，ｇｋ２，．．．，ｇｋｔ（ここで１≦ｋ１＜ｋ２＜．．．＜ｋｒ≦ｎ）によって生成されるモジュールであると仮定する。次に、写像
【数５６】
2008541540.tif 000058
により符号を定義する。
【０１４５】
（ｕが１つの単位であるケース）
次に、ｕを１つの単位と仮定し、ｕｖ＝１およびＵＶ＝Ｉであると仮定する。
【数５７】
2008541540.tif 000059
によって示される符号を検討する。次のように生成マトリックスおよびチェックマトリックスを得る。
【０１４６】
ＡをＵのｋ１，ｋ２，．．．，ｋｒから成るｒ×ｎマトリックスであるとする。ＤをＶのｋ１，ｋ２，．．．，ｋｒ列が削除された（ｎ−ｒ）×ｎマトリックスであるとする。
この場合、Ａは生成マトリックスであり、Ｄｔはチェックマトリックスである。符号
【数５８】
2008541540.tif 000060
に対し、同じようにＶおよびＵから生成マトリックスおよびチェックマトリックスを得る。
各ｉに対し、ｋｉ＝ｉであれば、最初のｒ行およびＵを有す。ここで、ＵはＵのうちの最初のｒ行であり、ＤはＶのうちの最後のｎ−ｒ列であり、これは上記の最初のケースに対応する。
【０１４７】
符号および生成マトリックス並びにチェックマトリックスを生成するこの方法は、単位群環要素に対応する非特異マトリックスに対して働き、単位群環要素に対応する非特異マトリックスではなく、任意の非特異マトリックスに対して働くことが理解できよう。
【０１４８】
（ｕがゼロ因子である）
次に、ｕをゼロ因子であると仮定する。ここで、ｕｖ＝０およびＵＶ＝０を有する。この場合、Ｕが階数ｒを有し、Ｖが階数ｎ−ｒを有すると見なす。符号化は
【数５９】
2008541540.tif 000061
であり、ケース
【数６０】
2008541540.tif 000062
も同様であると仮定する。
【０１４９】
Ｕのｒ個の行が存在し、これら行は線形的に独立していることは既知である。次に、Ｕのうちのｋ１，ｋ２，．．．，ｋｓ行がｓ≦ｒの場合に線形的に独立していると仮定する。行Ｒ’＝｛ｋ１，ｋ２，．．．，ｋｓ，ｗ１，．．．，ｗｒ−ｓ｝を線形的に独立するように選択できる。Ｒが、Ｒ’内の行をＵから取り出した順に置いたマトリックスであるとする。（ｗｉの行は必ずしもｋｊ行の後に続くものではない。）これらを正しい順にはめ込む。Ｕｒを行が順に配列されたＲから形成されたマトリックスであるとする。この場合、Ｕｒは階数ｒおよびサイズｒ×ｎを有する。ＵｒＣ＝Ｉｒとなるようなｎ×ｒのマトリックスＣが存在する。
【０１５０】
Ｕのうちの行ｋ１，．．．，ｋｓからマトリックスを形成し、これをＵｋｓと称す。この場合、我々の生成マトリックスＡはＵｋｓとなる。
【０１５１】
チェックマトリックスを得るためにＣのうちのｋ１，ｋ２，．．．，ｋｓ列を削除し、我々がＣｒ−ｓと称すｎ×（ｒ−ｓ）マトリックスを得る。次に、このＣｎ−ｒマトリックスをＶに加え、Ｄと称すマトリックスを得る。このＤはｎ×（ｎ−ｓ）マトリックスであり、このマトリックスは階数ｎ−ｓも有し、ＵｒＤ＝０を満たす。実際にＤｔｙｔ＝０の場合およびその場合に限り、ｙはコードワードとなる。
従って、我々のチェックマトリックスはＤｔである。
よって、生成マトリックスはＵｋｓであり、チェックマトリックスはＤｔであり、このマトリックスはＣからの所定のｒ−ｓ列をマトリックスＶｎ−ｒに加えることによって得られる。
【０１５２】
（利点）
本例における利点は、ｕｖ＝１およびＵＶ＝Ｉを仮定した場合、必要なタイプの符号または必要な距離を有する符号を我々に与えるような、Ｕの行を選択できることである。一旦、これら行を選択すると、生成マトリックスおよびチェックマトリックスが即座に得られる。
【０１５３】
（符号のタイプ）
本発明の範囲を限定するものではないが、本明細書を読めば、次のタイプの符号が理論的かつ実用上重要な符号であることが理解できよう。
・低密度パリティチェック（ＬＤＰＣ）符号
・セルフデュアルタイプの符号
・直交符号
【０１５４】
群環方法を検討すると、新規で有効なセルフデュアル符号を見つけることは容易であり、これらセルフデュアル符号は群環符号として容易に解釈できる。
ＬＤＰＣ符号は自らの重要性を有し、特別なタイプの群環符号を見ることにより、新規で、かつ有効なＬＤＰＣ符号を探すことが比較的容易である。
【０１５５】
（暗号化と組み合わされた符号化）
１つのシステムにおいて、群環公開鍵暗号化方法と符号とを組み合わせるために、特に単位群環符号が有効となる。例えばアリスしかｕの逆数ｕ−１を知っていないように、ｕをアリスの公開鍵である単位と仮定する。ｕによって決定された符号により、暗号化メッセージｍを送る。メッセージは暗号化されているだけでなく、ｕ−１から得られた復号化マトリックスをアリスしか知らないように、このマップにより暗号化もされている。
１つの演算で誤り訂正と暗号化とを組み合わせることができる。このことは、安価で安全な（および信頼性のある）通信から利点が得られるアプリケーションの数は言うまでもなく、複雑さを低減する点に関して膨大な潜在力を有し、チップの設計に関してコストを節約できる。
【０１５６】
（直交単位符号）
ＵＵｔ＝Ｉとなるように
【数６１】
2008541540.tif 000063
を直交マトリックスであると仮定する。Ｕｔ＝（Ａｔ｜Ｂｔ）であるので、上記記載からこのブロックフォームでこの単位によって生成される符号は生成マトリックスＡ（Ｕの頂部部分）およびチェックマトリックスＢ（Ｕの底部部分）を有することが理解できる。この符号を直交単位符号と称す。このことは、ｕｕｔ＝１となるような群環における単位ｕを探すことに対応する。ｕにおいて、ｇおよびｇ−１の係数が全ての
【数６２】
2008541540.tif 000064
に対して同一である場合、ｕｔ＝ｕである場合、条件はｕ２＝１である。Ｕ内のＡのサイズには制限はない。
【０１５７】
（低密度パリティチェック符号）
群環符号から新規な低密度パリティチェック（ＬＤＰＣ）符号が容易に得られる。チェック要素が短く、すなわち等価的にはマトリックスのサイズと比較して、各行および列にほとんど非ゼロ要素を有しないゼロ因子符号または単位符号を探すことが必要である。
【０１５８】
ｕまたはｕ−１のいずれかが、群のサイズと比較して少数の非ゼロ係数しか有しないように、単位要素ｕ∈ＲＧを探すことによって、疎またはＬＤＰＣ群環符号が得られる。
群環からのかかる符号のシリーズ全体を示すことは容易である。
優れた特性を有し、構築が比較的容易な、双周期的単位と称される非累積的群環単位が存在し、これら単位はほとんどの非累積的群環内に存在する。
【０１５９】
ａが群内に次数ｍを有すると仮定し、
【数６３】
2008541540.tif 000065
を定める。この場合、
【数６４】
2008541540.tif 000066
となる。ｂをａと交換しない群内の任意の要素であるとする。この場合、
【数６５】
2008541540.tif 000067
はα２＝０を満たすので、ｕ＝１＋αは１つの単位となる。ｂがａと交換しないとき、ｕ≠１である。また、ｕ−１＝１−αであり、これらは双周期的単位である。
【０１６０】
ａの次数であるｍはａ、ｂによって生成された群の次数と比較して大きくなくてもよいので、その結果生じるチェックマトリックス（および生成マトリックス）は、ｕ−１およびｕが短いので、疎となる。
正２面体群における双周期的単位を使用するＬＤＰＣ符号の「実施例」にて、これまで説明した例を参照されたい。
【０１６１】
これら例では、優れた距離特性を有する２つの周期的群の直積から形成された単位群環を使ったＬＤＰＣ符号も構築される。このように、新しいＬＤＰＣ符号を生成するために、他の多くの群も使用できる。
【０１６２】
復号のためにＬＤＰＣ符号のガースが重要であり、良好なガースを用いて新しい符号を構築できる。
【０１６３】
本発明を説明する際に、本明細書で用いた［含む」なる用語および「有する／備える」なる用語は、説明した特徴、整数、ステップまたはコンポーネントが存在することを指定するために用いたものであり、１つ以上のその他の特徴、整数、ステップ、コンポーネントまたはそれらの群の存在または追加を排除するものではない。
【０１６４】
明瞭にするために、別々の実施例に関連して説明した本発明の所定の特徴は、単一の実施例と組み合わせて得ることもできることが理解できよう。逆に、簡潔にするために、単一の実施例に関連して説明した本発明の種々の特徴は別々または適当なサブ組み合わせで得ることもできる。
【図面の簡単な説明】
【０１６５】
【図１】本発明の特徴にかかわる符号生成方法を示すフローチャートである。
【図２】図１に示された方法の要素選択プロセスおよび符号生成プロセスを示す。
【図１】
2008541540.tif 000068
【図２】
2008541540.tif 000069
【国際調査報告】
2008541540.tif 000070
2008541540.tif 000071
2008541540.tif 000072
2008541540.tif 000073
2008541540.tif 000074
2008541540.tif 000075