
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Computation of Grobner Basis for Systematic Encoding of Generalized QuasiCyclic Codes
Vo TAM VAN Hajime MATSUI Seiichi MITA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E92A
No.9
pp.23452359 Publication Date: 2009/09/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E92.A.2345 Print ISSN: 09168508 Type of Manuscript: PAPER Category: Coding Theory Keyword: automorphism group, Buchberger's algorithm, division algorithm, circulant matrix, finite geometry low density parity check (LDPC) codes,
Full Text: PDF>>
Summary:
Generalized quasicyclic (GQC) codes form a wide and useful class of linear codes that includes thoroughly quasicyclic 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 finitefield operations with the order of the third power of codelength. Each algorithm has its own characteristic. The first algorithm is composed of elementary methods and is appropriate for lowrate codes. The second algorithm is based on a novel formula and has smaller computational complexity than the first one for highrate codes with the number of orbits (cyclic parts) less than half of the code length. Moreover, we show that a serialin serialout encoder architecture for FG LDPC codes is composed of linear feedback shift registers with the size of the linear order of codelength; to encode a binary codeword of length n, it takes less than 2n adder and 2n memory elements.

