1. HOME
  2. 電気・情報関連(専門)
  3. 研究情報(登録番号655)

線形符号の重み構造解析とスペクトル拡散通信への応用

  • 写真なし嵩 忠雄
2元 (2[sup]m[/sup]-1, k) 巡回符号に関連する周期 2[sup]m[/sup]-1 の拡散符号のパラメータ

表1 2元 (2m-1, k) 巡回符号に関連する周期 2m-1 の拡散符号のパラメータ

符号長2[sup]m[/sup]-1の2重誤り訂正2元原始BCH符号の双対符号の重み分布

表2 符号長2m-1の2重誤り訂正2元原始BCH符号の双対符号の重み分布

符号長2[sup]m[/sup]-1の3重誤り訂正2元原始BCH符号の双対符号の重み分布

表3 符号長2m-1の3重誤り訂正2元原始BCH符号の双対符号の重み分布

 通信通信における高信頼化技術として、 伝送誤りを訂正する誤り訂正符号化技術がある。実用的な誤り訂正符号はほとんどすべて線形符号である。線形符号では、その最小距離(最小重み)が、ランダム誤りの検出訂正能力を表す重要な指標となるが、最小重みを求めることは一般に容易ではなく、最もよく研究されている2元原始BCH符号でも、部分的にしかわかっていない。記憶をもたない対称通信路において、線形符号を誤り検出・訂正に利用するとき、誤りを見逃すか誤って訂正する確率を求めるには、一般に重み分布を知る必要がある。重み分布についてかなりよくわかっていなければ、伝送効率を犠牲にした安全側への過剰設計が避け難い。このように重み分布は重要であるが、分布公式の導出は容易でなく、代数的符号理論における代表的な難問題である。

 BCH符号とRM符号(リード・マラー符号)は代表的な線形符号のクラスである。本研究では、RM符号のビット位置を適当に並べ換え、最初のビットを省くと、巡回符号になることを発見し、どのような巡回符号になるかを明らかにして、巡回RM符号とBCH符号の包含関係を明らかにした。このように、二つの代表的符号のクラスを関連づけることに成功し、更に、両者を含む多項式符号の導入へと発展した。本研究では、さらに、巧妙な方法を考案し、(1) 一般のRM符号について、d≤n<2.5d(d最小重み)に対して、重みwの符号語数Awの公式を導出した。Aw≠0、 w<2.5dである重みはまばらであることを明かにし、以下の成果を得た。(2a) BCH符号の設計距離は最小重みの下界であるが、2元原始BCH符号の無限の部分クラスにおいて一致しないことを示し、また、両者が一致するためのいくつかの十分条件を与えた。 (2b) 2次巡回RM符号の広範囲の部分符号とその双対符号の分布公式を導出した。このクラスには、2重および3重誤り訂正原始BCH符号、(0、2)次ユークリッド幾何符号等重要な符号を含む。

 さらに、(2a)、 (2b)に含まれる符号のうち、生成多項式が二つの既約多項式の積である符号の重み分布公式から、そのような多項式に対応する最大長系列間の相互相関関数を導出した。この系列は嵩系列または嵩符号と呼ばれ、スペクトル拡散通信方式に応用されている。嵩系列は、ゴールド系列を特殊ケースとして含み、発表時期もゴールドより若干早い。 長さ256のL-嵩符号(the large set of Kasami Sequences) は、国際電気通信連合(ITU)が定めた第3世代高速移動通信の国際標準規格(IMT-2000)における広帯域符号分割多重アクセス方式(W-CDMA)のアップリンク(端末->基地局)用の短い方の拡散符号に採用された。

 また、2元線形符号の重み分布が、一定の条件のもとで、2項分布に漸近的に近づくことは知られていたが、1980年代には、2元原始BCH符号などでは、それほど大きくないパラメータについても2項分布でかなりよく近似できることを、相対誤差の上界式を与えて示した。

電子情報通信学会情報理論研究専門委員会編集

 本研究の成果に対して、電子情報通信学会は、1987年、嵩 忠雄に業績賞を贈った。

文献

[1] Tadao Kasami、Weight Distributions of Bose-Chaudhuri-Hocquenghem Codes、1969年、Combinatorial Mathematics and Its Applications, R.C.Bose and T.A.Dowling, eds.
[2] Tadao Kasami and Nobuki Tokura、On the Weight Structure of Reed-Muller Codes、1970年、IEEE Transaction on Information Theory, IT-16, 6, 752--759
[3] Tadao Kasami、Weight distribution formula for some classes of cyclic codes、1966年、Cordinated Sci. Lab., Univ. Illinois, Urbana, Tech. Rep. R-285

関連する研究を検索

分野のカテゴリ

情報処理
(その他(情報処理))

関連する出来事

1964年11月
重み分布問題に着手
1965年
BCH符号とリードマラー符号の関係解明
1966年
BCH符号などの重み分布解明
2000年
嵩符号がIMT-2000に採用される。

世の中の出来事

1987
国鉄が分割民営化され、JRが発足する。
1987
利根川進がノーベル医学・生理学賞を受賞する。

Webページ

データなし

博物館等収蔵品

データなし

キーワード

線形符号、重み構造、スペクトル拡散通信、符号分割多元接続、拡散符号
Page Top