The Experts below are selected from a list of 132 Experts worldwide ranked by ideXlab platform
Seiichi Mita - One of the best experts on this subject based on the ideXlab platform.
-
GLOBECOM - A Class of Generalized Quasi-Cyclic LDPC Codes: High-Rate and Low-Complexity Encoder for Data Storage Devices
2010 IEEE Global Telecommunications Conference GLOBECOM 2010, 2010Co-Authors: Hajime Matsui, Seiichi MitaAbstract:In this paper, we study no 4-cycle, high-rate LDPC codes based on finite geometries for use in data storage devices and prove that these codes cannot be classified as quasi-cyclic (QC) codes but should be considered as broader generalized quasi-cyclic (GQC) codes. Because of the GQC structure of such codes, they can be systematically encoded using Groebner bases and their encoder can be implemented using simple feedback-shift registers. In order to demonstrate the efficiency of the encoder, we show that the hardware complexity of the serial-in serial-out encoder architecture of these codes is of linear order O(n). To encode a Binary Codeword of length n, less than 2n adders and 3n memory elements are required. Furthermore, we evaluated the error performances of these codes with sum product algorithm (SPA) decoding over additive white Gaussian noise (AWGN) channels. At a bit error rate (BER) of 10^-5, they perform 1-dB away from the Shannon limit after 10 decoding iterations.
-
GLOBECOM - A Class of Generalized Quasi-Cyclic LDPC Codes: High-Rate and Low-Complexity Encoder for Data Storage Devices
2010 IEEE Global Telecommunications Conference GLOBECOM 2010, 2010Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:In this paper, we study no 4-cycle, high-rate LDPC codes based on finite geometries for use in data storage devices and prove that these codes cannot be classified as quasi-cyclic (QC) codes but should be considered as broader generalized quasi-cyclic (GQC) codes. Because of the GQC structure of such codes, they can be systematically encoded using Groebner bases and their encoder can be implemented using simple feedback-shift registers. In order to demonstrate the efficiency of the encoder, we show that the hardware complexity of the serial-in serial-out encoder architecture of these codes is of linear order O(n). To encode a Binary Codeword of length n, less than 2n adders and 3n memory elements are required. Furthermore, we evaluated the error performances of these codes with sum product algorithm (SPA) decoding over additive white Gaussian noise (AWGN) channels. At a bit error rate (BER) of 10^-5, they perform 1-dB away from the Shannon limit after 10 decoding iterations.
-
Generalized quasi-cyclic low-density parity-check codes based on finite geometries
2009 IEEE Information Theory Workshop, 2009Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:In this study, we proved that several promising classes of codes based on finite geometries cannot be classified as quasi-cyclic (QC) codes but should be included in broader generalized quasi-cyclic (GQC) codes. Further, we proposed an algorithm (transpose algorithm) for the computation of the Grobner bases from the parity check matrices of GQC codes. Because of the GQC structure of such codes, they can be encoded systematically using Grobner bases and their encoder can be implemented using simple feedback-shift registers. In order to demonstrate the efficiency of our encoder, we proved that the number of circuit elements in the encoder architecture is proportional to the code length for finite geometry (FG) LDPC codes. For codes constructed using points and lines of finite geometries, the hardware complexity of the serial-in serial-out encoder architecture of the codes is linear order O(n). To encode a Binary Codeword of length n, less than 2n adder and 3n memory elements are required.
-
ICC - Low Complexity Encoder for Generalized Quasi-Cyclic Codes Coming from Finite Geometries
2009 IEEE International Conference on Communications, 2009Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:We define generalized quasi-cyclic (GQC) codes as linear codes with nontrivial automorphism groups. Therefore, GQC codes, unlike quasi-cyclic codes, can include many important codes such as Hermitian and projective geometry (PG) codes; this capability is important in practical applications. Further, we propose the echelon canonical form algorithm for computing Grobner bases from their parity check matrices. Consequently, by applying Grobner base theory, GQC codes can be systematically encoded and implemented with simple feedback shift registers. Our algorithm is based on Gaussian elimination and requires a sufficiently small number of finite-field operations, which is related to the third power of code-length. In order to demonstrate our encoder's efficiency, we prove that the number of circuit elements in the encoder architecture is proportional to the code-length for finite geometry (FG) LDPC codes (a class of GQC codes). We show that the hardware complexity of a serial-in-serial-out encoder architecture for FG-LDPC codes is related to the linear order of the code-length; less than 2n adder and 2n memory elements are required to encode a Binary Codeword of length n.
-
Computation of Grobner basis for systematic encoding of generalized quasi-cyclic codes
arXiv: Information Theory, 2008Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract: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: 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 the second algorithm is based on a novel formula and is faster than the first one for high-rate codes. 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: automorphism group, Buchberger's algorithm, division algorithm, circulant matrix, finite geometry low density parity check (LDPC) codes.
Vo Tam Van - One of the best experts on this subject based on the ideXlab platform.
-
GLOBECOM - A Class of Generalized Quasi-Cyclic LDPC Codes: High-Rate and Low-Complexity Encoder for Data Storage Devices
2010 IEEE Global Telecommunications Conference GLOBECOM 2010, 2010Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:In this paper, we study no 4-cycle, high-rate LDPC codes based on finite geometries for use in data storage devices and prove that these codes cannot be classified as quasi-cyclic (QC) codes but should be considered as broader generalized quasi-cyclic (GQC) codes. Because of the GQC structure of such codes, they can be systematically encoded using Groebner bases and their encoder can be implemented using simple feedback-shift registers. In order to demonstrate the efficiency of the encoder, we show that the hardware complexity of the serial-in serial-out encoder architecture of these codes is of linear order O(n). To encode a Binary Codeword of length n, less than 2n adders and 3n memory elements are required. Furthermore, we evaluated the error performances of these codes with sum product algorithm (SPA) decoding over additive white Gaussian noise (AWGN) channels. At a bit error rate (BER) of 10^-5, they perform 1-dB away from the Shannon limit after 10 decoding iterations.
-
Generalized quasi-cyclic low-density parity-check codes based on finite geometries
2009 IEEE Information Theory Workshop, 2009Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:In this study, we proved that several promising classes of codes based on finite geometries cannot be classified as quasi-cyclic (QC) codes but should be included in broader generalized quasi-cyclic (GQC) codes. Further, we proposed an algorithm (transpose algorithm) for the computation of the Grobner bases from the parity check matrices of GQC codes. Because of the GQC structure of such codes, they can be encoded systematically using Grobner bases and their encoder can be implemented using simple feedback-shift registers. In order to demonstrate the efficiency of our encoder, we proved that the number of circuit elements in the encoder architecture is proportional to the code length for finite geometry (FG) LDPC codes. For codes constructed using points and lines of finite geometries, the hardware complexity of the serial-in serial-out encoder architecture of the codes is linear order O(n). To encode a Binary Codeword of length n, less than 2n adder and 3n memory elements are required.
-
ICC - Low Complexity Encoder for Generalized Quasi-Cyclic Codes Coming from Finite Geometries
2009 IEEE International Conference on Communications, 2009Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:We define generalized quasi-cyclic (GQC) codes as linear codes with nontrivial automorphism groups. Therefore, GQC codes, unlike quasi-cyclic codes, can include many important codes such as Hermitian and projective geometry (PG) codes; this capability is important in practical applications. Further, we propose the echelon canonical form algorithm for computing Grobner bases from their parity check matrices. Consequently, by applying Grobner base theory, GQC codes can be systematically encoded and implemented with simple feedback shift registers. Our algorithm is based on Gaussian elimination and requires a sufficiently small number of finite-field operations, which is related to the third power of code-length. In order to demonstrate our encoder's efficiency, we prove that the number of circuit elements in the encoder architecture is proportional to the code-length for finite geometry (FG) LDPC codes (a class of GQC codes). We show that the hardware complexity of a serial-in-serial-out encoder architecture for FG-LDPC codes is related to the linear order of the code-length; less than 2n adder and 2n memory elements are required to encode a Binary Codeword of length n.
-
Computation of Grobner basis for systematic encoding of generalized quasi-cyclic codes
arXiv: Information Theory, 2008Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract: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: 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 the second algorithm is based on a novel formula and is faster than the first one for high-rate codes. 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: automorphism group, Buchberger's algorithm, division algorithm, circulant matrix, finite geometry low density parity check (LDPC) codes.
Hajime Matsui - One of the best experts on this subject based on the ideXlab platform.
-
GLOBECOM - A Class of Generalized Quasi-Cyclic LDPC Codes: High-Rate and Low-Complexity Encoder for Data Storage Devices
2010 IEEE Global Telecommunications Conference GLOBECOM 2010, 2010Co-Authors: Hajime Matsui, Seiichi MitaAbstract:In this paper, we study no 4-cycle, high-rate LDPC codes based on finite geometries for use in data storage devices and prove that these codes cannot be classified as quasi-cyclic (QC) codes but should be considered as broader generalized quasi-cyclic (GQC) codes. Because of the GQC structure of such codes, they can be systematically encoded using Groebner bases and their encoder can be implemented using simple feedback-shift registers. In order to demonstrate the efficiency of the encoder, we show that the hardware complexity of the serial-in serial-out encoder architecture of these codes is of linear order O(n). To encode a Binary Codeword of length n, less than 2n adders and 3n memory elements are required. Furthermore, we evaluated the error performances of these codes with sum product algorithm (SPA) decoding over additive white Gaussian noise (AWGN) channels. At a bit error rate (BER) of 10^-5, they perform 1-dB away from the Shannon limit after 10 decoding iterations.
-
GLOBECOM - A Class of Generalized Quasi-Cyclic LDPC Codes: High-Rate and Low-Complexity Encoder for Data Storage Devices
2010 IEEE Global Telecommunications Conference GLOBECOM 2010, 2010Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:In this paper, we study no 4-cycle, high-rate LDPC codes based on finite geometries for use in data storage devices and prove that these codes cannot be classified as quasi-cyclic (QC) codes but should be considered as broader generalized quasi-cyclic (GQC) codes. Because of the GQC structure of such codes, they can be systematically encoded using Groebner bases and their encoder can be implemented using simple feedback-shift registers. In order to demonstrate the efficiency of the encoder, we show that the hardware complexity of the serial-in serial-out encoder architecture of these codes is of linear order O(n). To encode a Binary Codeword of length n, less than 2n adders and 3n memory elements are required. Furthermore, we evaluated the error performances of these codes with sum product algorithm (SPA) decoding over additive white Gaussian noise (AWGN) channels. At a bit error rate (BER) of 10^-5, they perform 1-dB away from the Shannon limit after 10 decoding iterations.
-
Generalized quasi-cyclic low-density parity-check codes based on finite geometries
2009 IEEE Information Theory Workshop, 2009Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:In this study, we proved that several promising classes of codes based on finite geometries cannot be classified as quasi-cyclic (QC) codes but should be included in broader generalized quasi-cyclic (GQC) codes. Further, we proposed an algorithm (transpose algorithm) for the computation of the Grobner bases from the parity check matrices of GQC codes. Because of the GQC structure of such codes, they can be encoded systematically using Grobner bases and their encoder can be implemented using simple feedback-shift registers. In order to demonstrate the efficiency of our encoder, we proved that the number of circuit elements in the encoder architecture is proportional to the code length for finite geometry (FG) LDPC codes. For codes constructed using points and lines of finite geometries, the hardware complexity of the serial-in serial-out encoder architecture of the codes is linear order O(n). To encode a Binary Codeword of length n, less than 2n adder and 3n memory elements are required.
-
ICC - Low Complexity Encoder for Generalized Quasi-Cyclic Codes Coming from Finite Geometries
2009 IEEE International Conference on Communications, 2009Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract:We define generalized quasi-cyclic (GQC) codes as linear codes with nontrivial automorphism groups. Therefore, GQC codes, unlike quasi-cyclic codes, can include many important codes such as Hermitian and projective geometry (PG) codes; this capability is important in practical applications. Further, we propose the echelon canonical form algorithm for computing Grobner bases from their parity check matrices. Consequently, by applying Grobner base theory, GQC codes can be systematically encoded and implemented with simple feedback shift registers. Our algorithm is based on Gaussian elimination and requires a sufficiently small number of finite-field operations, which is related to the third power of code-length. In order to demonstrate our encoder's efficiency, we prove that the number of circuit elements in the encoder architecture is proportional to the code-length for finite geometry (FG) LDPC codes (a class of GQC codes). We show that the hardware complexity of a serial-in-serial-out encoder architecture for FG-LDPC codes is related to the linear order of the code-length; less than 2n adder and 2n memory elements are required to encode a Binary Codeword of length n.
-
Computation of Grobner basis for systematic encoding of generalized quasi-cyclic codes
arXiv: Information Theory, 2008Co-Authors: Vo Tam Van, Hajime Matsui, Seiichi MitaAbstract: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: 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 the second algorithm is based on a novel formula and is faster than the first one for high-rate codes. 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: automorphism group, Buchberger's algorithm, division algorithm, circulant matrix, finite geometry low density parity check (LDPC) codes.
Venkatesan Guruswami - One of the best experts on this subject based on the ideXlab platform.
-
ISAAC - On 2-query Codeword testing with near-perfect completeness
Algorithms and Computation, 2006Co-Authors: Venkatesan GuruswamiAbstract:A Codeword tester is a highly query-efficient spot checking procedure for ascertaining, with good confidence, proximity of a given string to its closest Codeword. We consider the problem of Binary Codeword testing using only two queries. It is known that three queries suffice for non-trivial Codeword testing with perfect completeness (where Codewords must be accepted with probability 1). It is known that two queries are not enough for testing with perfect completeness, whereas two queries suffice if one relaxes the requirement of perfect completeness (this is akin to the polynomial-time decidability of 2SAT and the APX-hardness of Max 2SAT, respectively). In this work, motivated by the parallel with 2-query PCPs and the approximability of near-satisfiable instances of Max 2SAT, we investigate 2-query testing with completeness close to 1, say 1–e for e→0. Our result is that, for codes of constant relative distance, such testers must also have soundness 1– O(e) (and this is tight up to constant factors in the O(e) term). This is to be contrasted with 2-query PCPs, where assuming the Unique Games Conjecture, one can have completeness 1–e and soundness $1-O(\sqrt{\varepsilon})$. Hence the ratio (1–s)/(1–c) can be super-constant for 2-query PCPs while it is bounded by a constant for 2-query LTCs. Our result also shows a similar limitation of 2-query PCPs of proximity, a notion introduced in [1].
-
On 2-Query Codeword Testing with Near-Perfect Completeness
Lecture Notes in Computer Science, 2006Co-Authors: Venkatesan GuruswamiAbstract:A Codeword tester is a highly query-efficient spot checking procedure for ascertaining, with good confidence, proximity of a given string to its closest Codeword. We consider the problem of Binary Codeword testing using only two queries. It is known that three queries suffice for non-trivial Codeword testing with perfect completeness (where Codewords must be accepted with probability 1). It is known that two queries are not enough for testing with perfect completeness, whereas two queries suffice if one relaxes the requirement of perfect completeness (this is akin to the polynomial-time decidability of 2SAT and the APX-hardness of Max 2SAT, respectively). In this work, motivated by the parallel with 2-query PCPs and the approximability of near-satisfiable instances of Max 2SAT, we investigate 2-query testing with completeness close to 1, say 1 - e for e → 0. Our result is that, for codes of constant relative distance, such testers must also have soundness 1 - O(e) (and this is tight up to constant factors in the O(e) term). This is to be contrasted with 2-query PCPs, where assuming the Unique Games Conjecture, one can have completeness 1-e and soundness 1-O(√e). Hence the ratio (1-s)/(1-c) can be super-constant for 2-query PCPs while it is bounded by a constant for 2-query LTCs. Our result also shows a similar limitation of 2-query PCPs of proximity, a notion introduced in [1].
Mikael Skoglund - One of the best experts on this subject based on the ideXlab platform.
-
Rate of Prefix-free Codes in LQG Control Systems
2016 IEEE International Symposium on Information Theory (ISIT), 2016Co-Authors: Takashi Tanaka, Karl Henrik Johansson, Tobias J. Oechtering, Henrik Sandberg, Mikael SkoglundAbstract:In this paper, we consider a discrete time linear quadratic Gaussian (LQG) control problem in which state information of the plant is encoded in a variable-length Binary Codeword at every time step, and a control input is determined based on the Codewords generated in the past. We derive a lower bound of the rate achievable by the class of prefix-free codes attaining the required LQG control performance. This lower bound coincides with the infimum of a certain directed information expression, and is computable by semidefinite programming (SDP). Based on a technique by Silva et al., we also provide an upper bound of the best achievable rate by constructing a controller equipped with a uniform quantizer with subtractive dither and Shannon-Fano coding. The gap between the obtained lower and upper bounds is less than $0.754r+1$ bits per time step regardless of the required LQG control performance, where $r$ is the rank of a signal-to-noise ratio matrix obtained by SDP, which is no greater than the dimension of the state.