The search functionality is under construction.

The search functionality is under construction.

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 2*n* adder and 2*n* memory elements.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.9 pp.2345-2359

- Publication Date
- 2009/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E92.A.2345

- Type of Manuscript
- PAPER

- Category
- Coding Theory

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.

Copy

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 2*n* adder and 2*n* memory elements.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.2345/_p

Copy

@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 2*n* adder and 2*n* memory elements.},

keywords={},

doi={10.1587/transfun.E92.A.2345},

ISSN={1745-1337},

month={September},}

Copy

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 2*n* adder and 2*n* memory elements.

ER -