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

Bounds and Constructions for Codes Protecting Against Asymmetric Errors

J. Martin Borden

We study binary error-correcting and error-detecting codes suitable for use on a completely asymmetric or Z channel. This channel accepts inputs of 0 and 1 and reproduces these faithfully as outputs, except that occasionally the input of a 1 will erroneously result in the output of a 0. We construct block codes protecting against this error and bound the performance of the best possible codes.

University Microfilms International eBooks•Jan 1, 1981•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

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•7 citations

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•49 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
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.