Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Asia-Pacific Conference on Communications (APCC)

Optimal generator matrices of binary cyclic codes over the binary symmetric channel

Houshou Chen

Published Oct 1, 2007• 0 citations
Publisher

Abstract

This paper considers the optimal generator matrices of a binary cyclic code over a binary symmetric channel with crossover probability p rarr 0 when the goal is to minimize the probability of an information bit error. A given code has many encoder realizations and the information bit error probability is a function of this realization. We derive some sufficient conditions for a binary cyclic code to have systematic optimal generator matrices under bounded distance decoding and determine many binary cyclic codes satisfying these properties.

DOI
10.1109/apcc.2007.4433455

Related papers

Optimal information bit encoding of linear block codes

Houshou Chen, J.T. Coffey

This paper examines the problem of finding an optimal generator matrix of a linear block code C over a binary symmetric channel in the quiet region (i.e., crossover probability p/spl rarr/0) when the goal is to minimize the probability of an information bit error. We present an infinite class of cyclic codes whose optimal generator matrices are nonseparable. The problem is linked to whether the minimum weight codewords form a basis of C.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•0 citations

Optimal information bit decoding of linear block codes

Aaron B. Kiely, J.T. Coffey, Mark R. Bell

We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>

IEEE Transactions on Information Theory•Jan 1, 1995•11 citations

An algorithm for calculating the exact bit error probability of a binary linear code over the binary symmetric channel

T. Wadayama

An efficient algorithm for calculating the i-th bit error probability of a binary linear code over the binary symmetric channel (BSC) are presented. It is proved that the exact i-th bit error probability of maximum likelihood (ML) decoding, bounded distance decoding, symbolwise maximum a posteriori probability (MAP) decoding and symbolwise MAP decoding with erasure can be obtained with time complexity O(n2/sup n-k/), where n, k denote length and dimension of the target code.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•0 citations

An Algorithm for Calculating the Exact Bit Error Probability of a Binary Linear Code Over the Binary Symmetric Channel

Tadashi Wadayama

An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.

IEEE Transactions on Information Theory•Feb 1, 2004•4 citations

Estimates of the bit error probabilities for linear block codes and symmetric binary-input memoryless channels

Vladimir B. Balakirsky

A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.

IEEE Information Theory Workshop (ITW)•Aug 27, 2003•1 citation

Information-theoretic lower bounds on the bit error probability of codes on graphs

Igal Sason, Rudiger L. Urbanke

We present lower bounds on the bit error probability of binary linear block codes, and on the gap between the channel capacity and the rate of these codes for which reliable communica- tion is achievable. The results are valid for memo- ryless binary-input output-symmetric (MBIOS) chan- nels. The lower bounds provide a quantitative mea- sure for the number of cycles of bipartite graphs which represent good error-correcting codes. The tightness of the lower bounds is especially pronounced for the binary erasure channel (BEC); to this end, we analyze a sequence of ensembles of low-density parity-check (LDPC) codes which closely approach these bounds. I. Introduction If a linear block code can be represented by a cycle-free fac- tor graph which only includes variable nodes and parity-check nodes, then maximum-likelihood soft decision decoding can be performed with low complexity (1). Theorem 5 in (1) indicates that these graphs represent codes with very poor minimum distance. The bounds in (1) only refer to the minimum dis- tance of cycle-free codes, and in this work we derive lower bounds on the bit error probability and the gap to capacity for codes on graphs which are represented by bipartite graphs (with or without cycles). We derive in this work information- theoretic lower bounds on the bit error probability of a binary linear code used over MBIOS channels. The bounds are ex- pressed in terms of the density of an arbitrary parity-check matrix which represents the binary linear code (i.e., the num- ber of ones in the matrix normalized per information bit), and they are valid for codes whose bipartite graphs are with or without cycles. We introduce a quantitative measure for the cycles in a bipartite graph which represents a binary lin- ear code (where the graph only includes variable nodes and parity-check nodes). The bounds provide an interpretation for the tradeofi which exists between the bit error proba- bility and gap to capacity of an arbitrary LDPC code (i.e., its performance limitations), and the density of an arbitrary parity-check matrix which represents the code (where the lat- ter afiects the decoding complexity per information bit and per iteration, under a message-passing iterative decoding al- gorithm). We present in this work quantitative results which indicate that in order to approach the channel capacity with vanishing bit error probability, LDPC codes should not have too sparse parity-check matrices, as otherwise their inherent gap to capacity becomes large. In fact, we show that the density of any parity-check matrix and the fundamental num- ber of cycles of the graph which represents the code should increase at least like log 1 where designates the gap to ca- pacity under iterative message-passing decoding (see (2), (3)). The tightness of the lower bounds which are derived in this work (and whose validity is for any sequence of codes with 1 1.5 2 2.5 3 3.5 4 4.5

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2003•4 citations
This paper considers the optimal generator matrices of a binary cyclic code over a binary symmetric channel with crossover probability p rarr 0 when the goal is to minimize the probability of an information bit error. A given code has many encoder realizations and the information bit error probability is a function of this realization. We derive some sufficient conditions for a binary cyclic code to have systematic optimal generator matrices under bounded distance decoding and determine many binary cyclic codes satisfying these properties.
We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>
An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.
A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.
We present lower bounds on the bit error probability of binary linear block codes, and on the gap between the channel capacity and the rate of these codes for which reliable communica- tion is achievable. The results are valid for memo- ryless binary-input output-symmetric (MBIOS) chan- nels. The lower bounds provide a quantitative mea- sure for the number of cycles of bipartite graphs which represent good error-correcting codes. The tightness of the lower bounds is especially pronounced for the binary erasure channel (BEC); to this end, we analyze a sequence of ensembles of low-density parity-check (LDPC) codes which closely approach these bounds. I. Introduction If a linear block code can be represented by a cycle-free fac- tor graph which only includes variable nodes and parity-check nodes, then maximum-likelihood soft decision decoding can be performed with low complexity (1). Theorem 5 in (1) indicates that these graphs represent codes with very poor minimum distance. The bounds in (1) only refer to the minimum dis- tance of cycle-free codes, and in this work we derive lower bounds on the bit error probability and the gap to capacity for codes on graphs which are represented by bipartite graphs (with or without cycles). We derive in this work information- theoretic lower bounds on the bit error probability of a binary linear code used over MBIOS channels. The bounds are ex- pressed in terms of the density of an arbitrary parity-check matrix which represents the binary linear code (i.e., the num- ber of ones in the matrix normalized per information bit), and they are valid for codes whose bipartite graphs are with or without cycles. We introduce a quantitative measure for the cycles in a bipartite graph which represents a binary lin- ear code (where the graph only includes variable nodes and parity-check nodes). The bounds provide an interpretation for the tradeofi which exists between the bit error proba- bility and gap to capacity of an arbitrary LDPC code (i.e., its performance limitations), and the density of an arbitrary parity-check matrix which represents the code (where the lat- ter afiects the decoding complexity per information bit and per iteration, under a message-passing iterative decoding al- gorithm). We present in this work quantitative results which indicate that in order to approach the channel capacity with vanishing bit error probability, LDPC codes should not have too sparse parity-check matrices, as otherwise their inherent gap to capacity becomes large. In fact, we show that the density of any parity-check matrix and the fundamental num- ber of cycles of the graph which represents the code should increase at least like log 1 where designates the gap to ca- pacity under iterative message-passing decoding (see (2), (3)). The tightness of the lower bounds which are derived in this work (and whose validity is for any sequence of codes with 1 1.5 2 2.5 3 3.5 4 4.5