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

IEEE International Symposium on Information Theory (ISIT)

Minimal error-trellises for linear block codes

M. Ariel, Jakov Snyders

Published Nov 27, 2002• 1 citation
Publisher

Abstract

An error-trellis is an efficient means to accomplish maximum likelihood decoding of a linear (n,k) block code C over GF(q). It represents the coset of C that contains the symbol-by-symbol detected version of the received vector. The trellis we construct has only n-k sections and the structure of each section is determined solely by the value of an associated q-ary symbol of the syndrome. Hence, the entire set of q/sup n-k/ trellises for all the cosets of C is formed by a set of q(n-k) distinct sections. The error-trellis is invariant under permutation of coordinates and attains the vertex count of a minimal code-trellis with the same sectionalization.

DOI
10.1109/isit.1998.708831

Related papers

Optimal encoding, trellis structure, and normalized weight of linear block codes.

Houshou Chen

This thesis concentrates on studying three problems in error-correcting codes: optimal encoding, trellis structure, and normalized weight of linear block codes. In general, the research in error-correcting codes can be roughly classified into coding practice and coding theory. The problems in coding practice focus on codes and decoders with more attention on the subject of the tradeoffs between performance and complexity, e.g., soft-decision decoding, bit error probability, or trellis of the codes. On the other hand, coding theory concentrates on the structure of codes based on sophisticated mathematical techniques, with little concern for the decoding complexity, e.g., coset weight distribution, algebraic constructions, or bounds on possible parameters of the codes. In this dissertation, we will present three fundamental topics in coding practice: optimal encoding of linear block codes for bit error probability, trellis structure of linear block codes for trellis-based decoding, and normalized weight of block coded modulation for bandwidth efficient communication systems. The central theme of the thesis is to transform the problems of the above three topics in coding practice into problems in coding theory and to develop the theory associated with the problems. Much of this thesis is devoted to studying what 'optimal' means in different contexts. In summary, we investigated the optimal information bit encoding of a given linear block code for minimizing the probability of an information bit error, with the goal of determining an optimal generator matrix by using the structure of the code. We showed that many natural codes have systematic optimal generator matrices in the quiet region. We analyzed the trellis structure of a self-dual code C to minimize the trellis complexity of the code by considering all equivalent codes of C, with the goal of reducing the soft-decision decoding complexity via permutations on the codeword coordinates. We determined the length/dimension profile of all eight [32, 16, 8] self-dual codes, and find their corresponding optimum permutations. We examined the performance gains achievable by adding interblock memory to block coded modulation systems, with the goal of finding the best codes for normalized distance rather than Hamming distance. We found a large number of best codes for normalized distance for the cases of practical interest.

•Jan 1, 1999•3 citations

Construction of minimal trellises for quantum stabilizer codes

Xiao Fang

The size of vertex set of quantum trellises affects the efficiency of decoding algorithms,which can be improved by reducing the number of vertices.Based on the standard check matrix of stabilizer codes,an algorithm to construct trellis-oriented generators for quantum stabilizer codes is presented.By using this algorithm,the trellises with minimal vertex set can be constructed.In addition,an algorithm to construct trellises iteratively for quantum stabilizer codes is also introduced.The algorithm proposed in this paper is more efficient and less complex than the one proposed by Olliver,and so is more suitable for the applications of larger scale and stricter timeliness.

Science China Information Sciences•Jan 1, 2013•0 citations

Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs

Ari Trachenberg

We consider two graph-based techniques for correcting the errors introduced into a transmission by a noisy channel. In the first technique, which is based on decoding with a layered graph known as a trellis, we examine a generalization of heuristically good codes called lexicodes. We propose and analyze a method for designing generalized lexicodes that minimize or constrain various trellis decoding parameters. The second technique is based on decoding with factor graphs, which Are typically smaller than trellis representations and have enjoyed Much attention in the recent literature. We look at a specific type of factor graphs known as Tanner graphs, for which a decoding algorithm is known. This decoding algorithm has been proven to converge always to a maximum-likelihood decoding if and only if the corresponding Tanner graph is cycle-free. However, we show that cycle-free Tannergraphs cannot support good codes, because of their weak structure. This weakness has a direct affect on codes of Tanner graphs with cycles, which we analyze as well.

•Dec 1, 1999•2 citations

Error -Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs

Ari Trachtenberg

We consider two graph-based techniques for correcting the errors introduced into a transmission by a noisy channel. In the first technique, which is based on decoding with a layered graph known as a trellis, we examine generalization of heuristically good codes called lexicodes. We propose and analyze a method for designing generalized lexicodes that minimize or constrain various trellis decoding parameters. The second technique is based on decoding with factor graphs, which are smaller than trellis representations and have enjoyed much attention in the recent literature. We look at a specific type of factor graphs known as Tanner graphs, for which a decoding algorithm is known. This decoding algorithm is proven to always converge to a maximum-likelihood decoding if and only if the corresponding Tanner graph is cycle-free. However, we show that cycle-free Tanner graphs cannot support good codes, because of their weak structure. This weakness has a direct affect on codes of Tanner graphs with cycles, which we analyze as well.

•Jan 1, 2000•0 citations

Trellises for stabilizer codes: Definition and uses

Harold Ollivier, Jean–Pierre Tillich

Trellises play an important theoretical and practical role for classical codes. Their main utility is to devise complexity-efficient error estimation algorithms. Here, we describe trellis representations for quantum stabilizer codes. We show that they share the same properties as their classical analogs. In particular, for any stabilizer code it is possible to find a minimal trellis representation. Our construction is illustrated by two fundamental error estimation algorithms.

arXiv:quant-ph/0512041•Physical Review A•Sep 7, 2006•10 citations

Trellises and Trellis-Based Decoding Algorithms for Linear Block Codes. Part 3; A Recursive Maximum Likelihood Decoding

Shu Wen Lin, M.P.C. Fossorier

•Apr 20, 1998•0 citations
An error-trellis is an efficient means to accomplish maximum likelihood decoding of a linear (n,k) block code C over GF(q). It represents the coset of C that contains the symbol-by-symbol detected version of the received vector. The trellis we construct has only n-k sections and the structure of each section is determined solely by the value of an associated q-ary symbol of the syndrome. Hence, the entire set of q/sup n-k/ trellises for all the cosets of C is formed by a set of q(n-k) distinct sections. The error-trellis is invariant under permutation of coordinates and attains the vertex count of a minimal code-trellis with the same sectionalization.
This thesis concentrates on studying three problems in error-correcting codes: optimal encoding, trellis structure, and normalized weight of linear block codes. In general, the research in error-correcting codes can be roughly classified into coding practice and coding theory. The problems in coding practice focus on codes and decoders with more attention on the subject of the tradeoffs between performance and complexity, e.g., soft-decision decoding, bit error probability, or trellis of the codes. On the other hand, coding theory concentrates on the structure of codes based on sophisticated mathematical techniques, with little concern for the decoding complexity, e.g., coset weight distribution, algebraic constructions, or bounds on possible parameters of the codes. In this dissertation, we will present three fundamental topics in coding practice: optimal encoding of linear block codes for bit error probability, trellis structure of linear block codes for trellis-based decoding, and normalized weight of block coded modulation for bandwidth efficient communication systems. The central theme of the thesis is to transform the problems of the above three topics in coding practice into problems in coding theory and to develop the theory associated with the problems. Much of this thesis is devoted to studying what 'optimal' means in different contexts. In summary, we investigated the optimal information bit encoding of a given linear block code for minimizing the probability of an information bit error, with the goal of determining an optimal generator matrix by using the structure of the code. We showed that many natural codes have systematic optimal generator matrices in the quiet region. We analyzed the trellis structure of a self-dual code C to minimize the trellis complexity of the code by considering all equivalent codes of C, with the goal of reducing the soft-decision decoding complexity via permutations on the codeword coordinates. We determined the length/dimension profile of all eight [32, 16, 8] self-dual codes, and find their corresponding optimum permutations. We examined the performance gains achievable by adding interblock memory to block coded modulation systems, with the goal of finding the best codes for normalized distance rather than Hamming distance. We found a large number of best codes for normalized distance for the cases of practical interest.
The size of vertex set of quantum trellises affects the efficiency of decoding algorithms,which can be improved by reducing the number of vertices.Based on the standard check matrix of stabilizer codes,an algorithm to construct trellis-oriented generators for quantum stabilizer codes is presented.By using this algorithm,the trellises with minimal vertex set can be constructed.In addition,an algorithm to construct trellises iteratively for quantum stabilizer codes is also introduced.The algorithm proposed in this paper is more efficient and less complex than the one proposed by Olliver,and so is more suitable for the applications of larger scale and stricter timeliness.
We consider two graph-based techniques for correcting the errors introduced into a transmission by a noisy channel. In the first technique, which is based on decoding with a layered graph known as a trellis, we examine a generalization of heuristically good codes called lexicodes. We propose and analyze a method for designing generalized lexicodes that minimize or constrain various trellis decoding parameters. The second technique is based on decoding with factor graphs, which Are typically smaller than trellis representations and have enjoyed Much attention in the recent literature. We look at a specific type of factor graphs known as Tanner graphs, for which a decoding algorithm is known. This decoding algorithm has been proven to converge always to a maximum-likelihood decoding if and only if the corresponding Tanner graph is cycle-free. However, we show that cycle-free Tannergraphs cannot support good codes, because of their weak structure. This weakness has a direct affect on codes of Tanner graphs with cycles, which we analyze as well.
We consider two graph-based techniques for correcting the errors introduced into a transmission by a noisy channel. In the first technique, which is based on decoding with a layered graph known as a trellis, we examine generalization of heuristically good codes called lexicodes. We propose and analyze a method for designing generalized lexicodes that minimize or constrain various trellis decoding parameters. The second technique is based on decoding with factor graphs, which are smaller than trellis representations and have enjoyed much attention in the recent literature. We look at a specific type of factor graphs known as Tanner graphs, for which a decoding algorithm is known. This decoding algorithm is proven to always converge to a maximum-likelihood decoding if and only if the corresponding Tanner graph is cycle-free. However, we show that cycle-free Tanner graphs cannot support good codes, because of their weak structure. This weakness has a direct affect on codes of Tanner graphs with cycles, which we analyze as well.