The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Kod kuasi-kitaran umum (GQC) membentuk kelas kod linear yang luas dan berguna yang merangkumi kod kuasi-kitaran menyeluruh, kod semakan pariti ketumpatan rendah (LDPC) geometri terhingga (FG) dan kod Hermitian. Walaupun diketahui bahawa pengekodan sistematik kod GQC adalah bersamaan dengan algoritma pembahagian dalam teori modul asas Grobner, tidak ada algoritma yang mengira asas Grobner untuk semua jenis kod GQC. Dalam makalah ini, kami mencadangkan dua algoritma untuk mengira asas Grobner untuk kod GQC daripada matriks semakan pariti mereka; kami memanggilnya algoritma bentuk kanonik eselon dan algoritma transpose. Kedua-dua algoritma memerlukan bilangan operasi medan terhingga yang cukup kecil dengan susunan kuasa ketiga panjang kod. Setiap algoritma mempunyai ciri tersendiri. Algoritma pertama terdiri daripada kaedah asas dan sesuai untuk kod kadar rendah. Algoritma kedua adalah berdasarkan formula baru dan mempunyai kerumitan pengiraan yang lebih kecil daripada yang pertama untuk kod kadar tinggi dengan bilangan orbit (bahagian kitaran) kurang daripada separuh panjang kod. Selain itu, kami menunjukkan bahawa seni bina pengekod bersiri masuk bersiri untuk kod FG LDPC terdiri daripada daftar anjakan maklum balas linear dengan saiz tertib linear panjang kod; untuk mengekodkan kata kod binari panjang n, ia mengambil masa kurang daripada 2n penambah dan 2n elemen ingatan.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Vo TAM VAN, Hajime MATSUI, Seiichi MITA, "Computation of Grobner Basis for Systematic Encoding of Generalized Quasi-Cyclic Codes" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 9, pp. 2345-2359, September 2009, doi: 10.1587/transfun.E92.A.2345.
Abstract: Generalized quasi-cyclic (GQC) codes form a wide and useful class of linear codes that includes thoroughly quasi-cyclic codes, finite geometry (FG) low density parity check (LDPC) codes, and Hermitian codes. Although it is known that the systematic encoding of GQC codes is equivalent to the division algorithm in the theory of Grobner basis of modules, there has been no algorithm that computes Grobner basis for all types of GQC codes. In this paper, we propose two algorithms to compute Grobner basis for GQC codes from their parity check matrices; we call them echelon canonical form algorithm and transpose algorithm. Both algorithms require sufficiently small number of finite-field operations with the order of the third power of code-length. Each algorithm has its own characteristic. The first algorithm is composed of elementary methods and is appropriate for low-rate codes. The second algorithm is based on a novel formula and has smaller computational complexity than the first one for high-rate codes with the number of orbits (cyclic parts) less than half of the code length. Moreover, we show that a serial-in serial-out encoder architecture for FG LDPC codes is composed of linear feedback shift registers with the size of the linear order of code-length; to encode a binary codeword of length n, it takes less than 2n adder and 2n memory elements.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2345/_p
Salinan
@ARTICLE{e92-a_9_2345,
author={Vo TAM VAN, Hajime MATSUI, Seiichi MITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computation of Grobner Basis for Systematic Encoding of Generalized Quasi-Cyclic Codes},
year={2009},
volume={E92-A},
number={9},
pages={2345-2359},
abstract={Generalized quasi-cyclic (GQC) codes form a wide and useful class of linear codes that includes thoroughly quasi-cyclic codes, finite geometry (FG) low density parity check (LDPC) codes, and Hermitian codes. Although it is known that the systematic encoding of GQC codes is equivalent to the division algorithm in the theory of Grobner basis of modules, there has been no algorithm that computes Grobner basis for all types of GQC codes. In this paper, we propose two algorithms to compute Grobner basis for GQC codes from their parity check matrices; we call them echelon canonical form algorithm and transpose algorithm. Both algorithms require sufficiently small number of finite-field operations with the order of the third power of code-length. Each algorithm has its own characteristic. The first algorithm is composed of elementary methods and is appropriate for low-rate codes. The second algorithm is based on a novel formula and has smaller computational complexity than the first one for high-rate codes with the number of orbits (cyclic parts) less than half of the code length. Moreover, we show that a serial-in serial-out encoder architecture for FG LDPC codes is composed of linear feedback shift registers with the size of the linear order of code-length; to encode a binary codeword of length n, it takes less than 2n adder and 2n memory elements.},
keywords={},
doi={10.1587/transfun.E92.A.2345},
ISSN={1745-1337},
month={September},}
Salinan
TY - JOUR
TI - Computation of Grobner Basis for Systematic Encoding of Generalized Quasi-Cyclic Codes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2345
EP - 2359
AU - Vo TAM VAN
AU - Hajime MATSUI
AU - Seiichi MITA
PY - 2009
DO - 10.1587/transfun.E92.A.2345
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2009
AB - Generalized quasi-cyclic (GQC) codes form a wide and useful class of linear codes that includes thoroughly quasi-cyclic codes, finite geometry (FG) low density parity check (LDPC) codes, and Hermitian codes. Although it is known that the systematic encoding of GQC codes is equivalent to the division algorithm in the theory of Grobner basis of modules, there has been no algorithm that computes Grobner basis for all types of GQC codes. In this paper, we propose two algorithms to compute Grobner basis for GQC codes from their parity check matrices; we call them echelon canonical form algorithm and transpose algorithm. Both algorithms require sufficiently small number of finite-field operations with the order of the third power of code-length. Each algorithm has its own characteristic. The first algorithm is composed of elementary methods and is appropriate for low-rate codes. The second algorithm is based on a novel formula and has smaller computational complexity than the first one for high-rate codes with the number of orbits (cyclic parts) less than half of the code length. Moreover, we show that a serial-in serial-out encoder architecture for FG LDPC codes is composed of linear feedback shift registers with the size of the linear order of code-length; to encode a binary codeword of length n, it takes less than 2n adder and 2n memory elements.
ER -