講演名 1999/3/11
貪欲法に基づく順序付基底を構成するアルゴリズムと生成される線形符号について
和田山 正, 知久 真理子, 弓場 芳治,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 本稿では, 順序付基底の構成アルゴリズムを提案する. 本アルゴリズムは, 与えられた有限体F_q, 符号長n, 次元kに対して, 大きなFeng-Rao設計距離d_を与える線形符号の構成を目的とするものである. Feng-Rao設計距離の大きい符号を構成する問題は, 良好な順序付基底を構成する問題に帰着できる. ここで, 順序付基底とは, 番号付けされているF^n_qの基底である. 本稿では, 代数幾何に基づく手法とは異なる観点から順序付基底構成問題へのアプローチを試みる. 提案する基底構成アルゴリズムは, 初期基底を順次, 改良していく手法に基づいており, その時間計算量はO(n^4)である. 本アルゴリズムは, 任意の有限体, 符号長に対して適用可能である. そのため従来, 符号構成が困難であったパラメータにおいても符号を構成できる. また, このアルゴリズムにより得られる符号は, Feng-Rao復号法により, ⌊(d_-1)/2⌋までの限界距離復号がO(n^3)で可能である.
抄録(英) The paper presents an algorithm for generating an ordered basis of F^n_q, where F_q is the finite field with q-elements. The purpose of the algorithm is to construct a linear code with a large Feng-Rao designed distance d_. In order to obtain a linear code with a large d_, we need to construct a good ordered basis. The ordered basis is an indexed basis of F^n_q. The proposed algorithm improves an initial basis for each step of the algorithm according to a heuristic rule. The time complexity of the algorithm is O(n^4). The algorithm can work for arbitrary finite field, length, dimension. The linear codes obtained from the algorithm can be decoded up to ⌊(d_-1)/2⌋ with time complexity O(n^3). Some high rate codes obtained by the algorithm are comparable to the improved Geometric Goppa codes.
キーワード(和) 線形符号 / 順序付基底 / Feng-Rao設計距離
キーワード(英) Linear code / Ordered basis / Feng-Rao designed distance
資料番号 IT98-103
発行日

研究会情報
研究会 SST
開催期間 1999/3/11(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Spread Spectrum Technology (SST)
本文の言語 JPN
タイトル(和) 貪欲法に基づく順序付基底を構成するアルゴリズムと生成される線形符号について
サブタイトル(和)
タイトル(英) On a Greedy Algorithm for Generating Ordered Basis and Linear Codes Generated by the Algorithm
サブタイトル(和)
キーワード(1)(和/英) 線形符号 / Linear code
キーワード(2)(和/英) 順序付基底 / Ordered basis
キーワード(3)(和/英) Feng-Rao設計距離 / Feng-Rao designed distance
第 1 著者 氏名(和/英) 和田山 正 / Tadashi WADAYAMA
第 1 著者 所属(和/英) 岡山県立大学情報通信工学科
Okayama Prefectural University
第 2 著者 氏名(和/英) 知久 真理子 / Mariko CHIKU
第 2 著者 所属(和/英) 岡山県立大学情報通信工学科
Okayama Prefectural University
第 3 著者 氏名(和/英) 弓場 芳治 / Yoshiharu YUBA
第 3 著者 所属(和/英) 岡山県立大学情報通信工学科
Okayama Prefectural University
発表年月日 1999/3/11
資料番号 IT98-103
巻番号(vol) vol.98
号番号(no) 658
ページ範囲 pp.-
ページ数 6
発行日