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

arXiv:1706.04540 · IEEE Communications Letters

On Error Detection in Asymmetric Channels

Mladen Kovačević

Published Jun 19, 2017• 2 citations
arXivHTMLPDF

Abstract

We study the error detection problem in q-ary asymmetric channels, wherein every input symbol xiis mapped to an output symbol yisatisfying yi≥xi. A general setting is assumed, where the noise vectors are (potentially) restricted in: 1) the amplitude, yi-xi≤a, 2) the Hamming weight, Σi=1n1{yi≠xi}≤ h, and 3) the total weight, Σi=1n(yi-xi)≤t. Optimal codes detecting these types of errors are described for certain sets of parameters a, h, t, both in the standard and in the cyclic (mod q) version of the problem. It is also demonstrated that these codes are optimal in the large alphabet limit for every a, h, t and every block-length n.

DOI
10.1109/lcomm.2017.2716972

Related papers

Error detection, correction and decoding

San Ling, Chaoping Xing

We saw in Chapter 1 that the purpose of channel coding is to introduce redundancy to information messages so that errors that occur in the transmission can be detected or even corrected. In this chapter, we formalize and discuss the notions of error-detection and error-correction. We also introduce some well known decoding rules, i.e., methods that retrieve the original message sent by detecting and correcting the errors that have occurred in the transmission. Communication channels We begin with some basic definitions. Definition 2.1.1 Let A = { a 1 , a 2 , …, a q } be a set of size q , which we refer to as a code alphabet and whose elements are called code symbols . (i) A q-ary word of length n over A is a sequence w = w 1 w 2 … w n with each w i ∈ A for all i . Equivalently, w may also be regarded as the vector ( w 1 , …, w n ). (ii) A q-ary block code of length n over A is a nonempty set C of q -ary words having the same length n . (iii) An element of C is called a codeword in C . (iv) The number of codewords in C , denoted by ∣ C ∣, is called the size of C . (v) The (information) rate of a code C of length n is defined to be (log q ∣ C ∣)/ n . (vi) A code of length n and size M is called an (n, M)-code .

Cambridge University Press eBooks•Feb 12, 2004•0 citations

Weighted-Hamming Metric for Parallel Channels

Sebastian Bitzer, Alberto Ravagnani, Violetta Weger

Independent parallel q-ary symmetric channels are a suitable transmission model for several applications. The weighted-Hamming metric is tailored to this setting and enables optimal decoding performance. We show that some weighted-Hamming-metric codes exhibit the unusual property that all errors beyond half the minimum distance can be corrected. Nevertheless, a tight relation between the error-correction capability of a code and its minimum distance can be established. Generalizing their Hamming-metric counterparts, upper and lower bounds on the cardinality of a code with a given weighted-Hamming distance are obtained. Finally, we propose a simple code construction with optimal minimum distance for specific parameters.

arXiv:2401.17801•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•1 citation

Concerning a bound on undetected error probability (Corresp.)

S. Leung-Yan-Cheong, Martin E. Hellman

In the past, it has generally been assumed that the probability of undetected error for an(n,k)block code, used solely for error detection on a binary symmetric channel, is upperbounded by2^{-(n-k)}. In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.

IEEE Transactions on Information Theory•Mar 1, 1976•51 citations

The capacity of online (causal) q-ary error-erasure channels

Zitan Chen, Sidharth Jaggi, Michael Langberg

In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, . . . , xn) ∈ {0, 1, . . . , q - 1}nsymbol-by-symbol via a channel limited to at most p*n errors (symbol changes) and p*n erasures. The channel is "online" (i.e., "causal") in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not only based on its view of the symbols (x1,. . . , xi). This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword x. In this work we extend the results obtained in [1]-[4] (in which the capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels were characterized). We here extend those prior results in two important ways. First, we obtain the capacity of q-ary online channels for general q (rather than just q = 2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries. The extensions in this paper require novel approaches for both optimal code designs, and matching information-theoretic converse arguments.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•8 citations

Generalized Bose–Lin Codes, a Class of Codes Detecting Asymmetric Errors

Irina Naydenova, Torleiv Kløve

Bose and Lin introduced a class of systematic codes for detection of binary asymmetric errors. In this note, we describe a generalization to q-ary asymmetric error detecting codes. For these codes, the possible undetectable errors are characterized and the undetectable errors of minimum weight are determined

IEEE Transactions on Information Theory•Mar 1, 2007•10 citations

Maximum Likelihood Decoding of Codes on the Asymmetric Z-channel

Susanna Spinsante, Ángela I. Barbero

AbstractThe aim of this paper is to extend some basic concepts related to the MaximumLikelihood decoding of codes on the Z-channel, which is a particular, but very important,example of an asymmetric channel. We study distance properties of linear codes overthe Z-channel, in order to de ne a suitable metric for the implementation of a MaximumLikelihood decoder on the channel. A combinatorial expression for an upper bound on theprobability of incorrect Maximum Likelihood decoding is also provided, and comparisonsare given to evaluate the tightness of the bound, when a Hamming code, a Turbo codeand an LDPC code are decoded on the asymmetric channel. 1 Introduction Errors induced by communications on a noisy channel or storage medium can be reduced to anydesired level by proper encoding of the information, as long as the information rate is less thanthe capacity of the channel. This fact was shown in a landmark paper by Shannon, in 1948 [1];since that time, much work has been devoted to the problem of devising ecient encoding anddecoding methods for error control in a noisy environment.In a block-coded system, the source output u represents a k-bit message, the encoder outputc represents an n-symbol codeword, the demodulator output r represents the correspondingbinary received n-tuple and the decoder output u^ represents the k-bit estimate of the encodedmessage. The decoder must produce an estimate u^ of the information sequence u based onthe received sequence r. Equivalently, since there is a one-to-one correspondence between theinformation sequence u and the codeword c, the decoder can produce an estimate ^c of thecodeword c. Obviously, u^ = u if and only if ^c = c. The strategy adopted for choosing an

•Jan 1, 2005•3 citations
We study the error detection problem in q-ary asymmetric channels, wherein every input symbol xiis mapped to an output symbol yisatisfying yi≥xi. A general setting is assumed, where the noise vectors are (potentially) restricted in: 1) the amplitude, yi-xi≤a, 2) the Hamming weight, Σi=1n1{yi≠xi}≤ h, and 3) the total weight, Σi=1n(yi-xi)≤t. Optimal codes detecting these types of errors are described for certain sets of parameters a, h, t, both in the standard and in the cyclic (mod q) version of the problem. It is also demonstrated that these codes are optimal in the large alphabet limit for every a, h, t and every block-length n.
We saw in Chapter 1 that the purpose of channel coding is to introduce redundancy to information messages so that errors that occur in the transmission can be detected or even corrected. In this chapter, we formalize and discuss the notions of error-detection and error-correction. We also introduce some well known decoding rules, i.e., methods that retrieve the original message sent by detecting and correcting the errors that have occurred in the transmission. Communication channels We begin with some basic definitions. Definition 2.1.1 Let A = { a 1 , a 2 , …, a q } be a set of size q , which we refer to as a code alphabet and whose elements are called code symbols . (i) A q-ary word of length n over A is a sequence w = w 1 w 2 … w n with each w i ∈ A for all i . Equivalently, w may also be regarded as the vector ( w 1 , …, w n ). (ii) A q-ary block code of length n over A is a nonempty set C of q -ary words having the same length n . (iii) An element of C is called a codeword in C . (iv) The number of codewords in C , denoted by ∣ C ∣, is called the size of C . (v) The (information) rate of a code C of length n is defined to be (log q ∣ C ∣)/ n . (vi) A code of length n and size M is called an (n, M)-code .
Independent parallel q-ary symmetric channels are a suitable transmission model for several applications. The weighted-Hamming metric is tailored to this setting and enables optimal decoding performance. We show that some weighted-Hamming-metric codes exhibit the unusual property that all errors beyond half the minimum distance can be corrected. Nevertheless, a tight relation between the error-correction capability of a code and its minimum distance can be established. Generalizing their Hamming-metric counterparts, upper and lower bounds on the cardinality of a code with a given weighted-Hamming distance are obtained. Finally, we propose a simple code construction with optimal minimum distance for specific parameters.
In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, . . . , xn) ∈ {0, 1, . . . , q - 1}nsymbol-by-symbol via a channel limited to at most p*n errors (symbol changes) and p*n erasures. The channel is "online" (i.e., "causal") in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not only based on its view of the symbols (x1,. . . , xi). This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword x. In this work we extend the results obtained in [1]-[4] (in which the capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels were characterized). We here extend those prior results in two important ways. First, we obtain the capacity of q-ary online channels for general q (rather than just q = 2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries. The extensions in this paper require novel approaches for both optimal code designs, and matching information-theoretic converse arguments.
AbstractThe aim of this paper is to extend some basic concepts related to the MaximumLikelihood decoding of codes on the Z-channel, which is a particular, but very important,example of an asymmetric channel. We study distance properties of linear codes overthe Z-channel, in order to de ne a suitable metric for the implementation of a MaximumLikelihood decoder on the channel. A combinatorial expression for an upper bound on theprobability of incorrect Maximum Likelihood decoding is also provided, and comparisonsare given to evaluate the tightness of the bound, when a Hamming code, a Turbo codeand an LDPC code are decoded on the asymmetric channel. 1 Introduction Errors induced by communications on a noisy channel or storage medium can be reduced to anydesired level by proper encoding of the information, as long as the information rate is less thanthe capacity of the channel. This fact was shown in a landmark paper by Shannon, in 1948 [1];since that time, much work has been devoted to the problem of devising ecient encoding anddecoding methods for error control in a noisy environment.In a block-coded system, the source output u represents a k-bit message, the encoder outputc represents an n-symbol codeword, the demodulator output r represents the correspondingbinary received n-tuple and the decoder output u^ represents the k-bit estimate of the encodedmessage. The decoder must produce an estimate u^ of the information sequence u based onthe received sequence r. Equivalently, since there is a one-to-one correspondence between theinformation sequence u and the codeword c, the decoder can produce an estimate ^c of thecodeword c. Obviously, u^ = u if and only if ^c = c. The strategy adopted for choosing an