Questions tagged [error-correcting-codes]

Error correcting codes are used to transmit information through a noisy channel. They also have applications in theoretical computer science and combinatorics. Some well known error correcting codes are Hamming codes, Reed–Solomon codes, and Reed–Muller codes.

Filter by
Sorted by
Tagged with
1
vote
1answer
20 views

Upper bound on size of minimal binary coverage code

Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X_n$ such that ...
2
votes
1answer
34 views

Calculate number of error-correcting code check bits

To design a code with $m$ data bits and $r$ check bits which allow all single-bit errors to be corrected, the formula $$(n + 1) 2^m \leq 2^n$$ with $n = m + r$ and $(m + r + 1) \leq 2^r$ is used. Why ...
2
votes
1answer
34 views

Error correction code without error detection

Error detection and correction codes require many bits of redundancy for correcting even a modest number of erroneous bits. However, we often have out-of-band methods to determine when and where the ...
0
votes
0answers
18 views

Capacity of broadcast channels

It is given in the book by El Gamal that The capacity region of the DM-BC depends on the channel conditional pmf $p(y_1 , y _2 |x)$ only through the conditional marginal pmfs $p(y_1 |x)$ and $p(y_ 2 |...
1
vote
0answers
32 views

How do I decode a received polynomial code with an error?

As a message I get (5,0,1,3), which is coding a sequence of numbers of length 2 in $\mathbb{F}_7$ as polynom with the 4 support points a1 = 0, a2 = 1, a3 = 2, a4 = 6. In the transimission occured an ...
1
vote
0answers
35 views

Understanding a CRC32 Implementation

I'm currently trying to understand an implementation of CRC32 about which I have a question. On this page at section 6, there is the following code: ...
1
vote
2answers
21 views

Why frame must be longer than generator polynomial?

Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213: When the polynomial code method is employed, the sender and receiver must ...
1
vote
1answer
26 views

Why high and lower bit of generator must be 1?

Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213: When the polynomial code method is employed, the sender and receiver must ...
1
vote
1answer
55 views

How to read Nasa Convolutional code?

Here is a picture from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 207(English Version)/Page 206(Japanese Version): I want to verify whether my ...
1
vote
1answer
30 views

Why Convolutional codes is easy to factor/handle the uncertainty of a bit being a 0 or a 1 into the decoding?

Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208: My question is about this part. [Convolutional codes have been popular in ...
2
votes
1answer
31 views

When is Viterbi's algorithm practical?

Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208: The internal state is kept in six memory registers. Each time another bit is ...
0
votes
3answers
98 views

Undetectable error correcting codes

I have a 256 bit string (indistinguishable from random) which I wish to encode into a greater length string using an error correction code. The result must also be indistinguishable from random. It ...
1
vote
0answers
198 views

Channel coding and Error probability. Where are these probabilities from?

From where are the following probabilities? We consider BSCε with ε = 0,1 and block code C = {c1, c2} with the code words c1 = 010 and c2 = 101. On the received word y we use the decoder D = {D1,D2} ...
2
votes
2answers
27 views

Why double error correction and quadruple error detection cannot occur at the same time?

What does [ we cannot both correct double errors and detect quadruple errors because this would require us to interpret a received codeword in two different ways] means? I understand how double error ...
3
votes
1answer
25 views

What would be a natural generalization of a byte parity check?

Suppose that we have a group of N bytes. One can add a very basic (and not particularly reliable) check of the consistency of this data by storing an additional (N+1)th byte containing exclusive XOR ...
1
vote
1answer
65 views

Understanding connection between length of codeword and hamming distance in Hamming code

I came across following in Huffman coding: Minimum Hamming distance to correct up to s errors is $2s + 1$ because that way the legal codewords are so far apart that even with $s$ changes the ...
3
votes
0answers
513 views

Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code

I have some highly optimized code for a CRC-16 implementation. It focuses on speed rather than flexibility, and as a result, it is hard-coded to model the specific unreflected polynomial ...
1
vote
2answers
47 views

Effects of parity bit on odd code length regarding its size after alternation

I am trying to understand code distance, but I am not sure regarding the following scenario: Assume that you have an information word M with m bits, that You code into a coding word using the ...
1
vote
0answers
20 views

finding amount of errors that can be fixed based on code length [closed]

i tried to look online and search this site and others but haven't found any good explanation to the following simple question: how many errors can a code with length k(k>2)fix?
0
votes
0answers
12 views

distance of a code name in scheme

i wonder: is it true that if we take a information word, call it M(with m bits) for example, and code it by first coding M using a code, that we don't know anything about, except of it a length of k, ...
0
votes
1answer
61 views

Probability of detecting errors in codewords

I have been struggling with the below question for quite some time, and I don't have a pointer to move forward. A certain Error Control Coding scheme using block codes takes an input block (...
0
votes
0answers
24 views

minimal distance of a self correcting code

i wonder: how can i find minimal distance of a self correcting code in following situation: if we know that a code can fix every 3 errors(if not more than 3 errors, the word is recovered) and can ...
1
vote
1answer
18 views

Decoding problem and conditional probabilities

I'm reading the book by MacKay "Information theory, inference and learning algorithms" and I'm confused by how he introduces the decoding problem for LDPC codes (page 557). given a channel ...
1
vote
0answers
14 views

Is an error-correcting code where the parity symbols are interleaved with the data symbols considered systematic?

According to the Wikipedia entry, a systematic code is one in which the input data is embedded in the encoded output. Conversely, in a non-systematic code the output does not contain the input ...
3
votes
2answers
68 views

$2d+1$ threshold for error detection

Why is the threshold for detecting errors $2d+1$? I am aware that the question has been asked before, for example here, but the answers provided didn't really justify why the formula contains $+1$. ...
1
vote
2answers
43 views

Example of a code that can be decoded using bounded distance decoder

In the book Information theory, Inference and Learning Algorithm, in chapter 13, MacKay defines bounded distance decoding A bounded distance decoder is a decoder that returns the closest codeword ...
0
votes
0answers
32 views

Most likely error with Hamming distance

I have a basic question about Hamming distances, something confuse me in the book I'm reading about it. Let's assume we have a codeword $y$ that received an error $e$. Thus we had the following event:...
0
votes
1answer
42 views

Basic classical linear error correcting code for bits exercice (from Nielsen & Chuang)

I am learning about quantum error correction which is for a part based on classical linear error correcting code. There is a very basic answer on an exercice I do not understand. Here is the problem (...
0
votes
2answers
56 views

Linear codes : why has the parity check matrix dimensions $(n-k)*k$?

I am studying Quantum error correction that is based on some aspects on classical error correction. I am reading some very basics around linear error correcting codes. I consider a linear code [n,k]:...
0
votes
1answer
174 views

Hamming code distance and error detection

Suppose that data are transmitted in blocks of sizes 1000 bits. What is the maximum error rate under which error detection and retransmission mechanism (1 parity bit per block) is better than using ...
1
vote
2answers
45 views

How to construct a random error-correcting code (its generator matrix) according to the code parameters?

I need to construct a random code which corrects T errors, has R check bits and has N maximum bits in the transmitting word. I have researched the topic and found a few theorems about the bounds (The ...
2
votes
1answer
21 views

What are the sufficient conditions for weighted binary code to be self compliementary?

I was going through binary codes and found out that if the weighted binary code is self complimentary then it's weights addition will be equal to 9. Is the converse true? If not then what are the ...
1
vote
1answer
84 views

when can i detect the position of error in hamming code

I have 4-bit data with the hamming code 0010011. the parity parameters are: p1=0 , p2=0 , p3=0 and the check codes are: ...
6
votes
2answers
90 views

Is Reed Solomon also a Fountain code?

Once you encode your message as a polynomial you can effectively generate and stream an endless number of points on that polynomial of which only a finite subset would be required to recover the ...
1
vote
1answer
41 views

Sphere packing inequality for error-correcting codes

i am wondering if the following inequality is correct: if a code allows repairing of no more than k errors (inclusive, included) and m is the number of information bits and r the check bits, then $$∑^...
0
votes
1answer
31 views

Confusing notation in concatenation of error correcting codes

Define an $(m,q,d,k)$-(block) code $C$ to be a code with block size $m$, alphabet $0\ldots ,q-1$, and (non-relative) rate $k$. Meaning: $k=log_q (|C|)$ (if we think of $C$ as a set of legal codewords) ...
0
votes
1answer
56 views

Decoding cyclic code, assuming we have no errors

Assuming the coded data is errorless and given generator polynomial coefficients. By what algorithm can I decode the data coded by matrix constructed by given generator polynomial?
1
vote
1answer
25 views

Determining properties of linear code from generator matrix

I have a problem in error-correcting codes. Say we have a generator matrix of a linear binary code $$g=\begin{pmatrix} 10011 \\ 01101 \end{pmatrix} $$ Q1: How many different codeword do we have? ...
1
vote
1answer
170 views

what does the redundancy of a code means?

I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $\log(6n-3)$ bits. But what does that means? I was ...
4
votes
1answer
1k views

How can I correct this Hamming code?

I'm trying to decode the following Hamming sequence (using EVEN parity and knowing there is a 1-bit error), which contains an ASCII value: 01100110101 I've tried ...
0
votes
1answer
43 views

Improving heading measurements from low cost compass module

I have heading measurements of two Sensors (BNO055 and HMC6343) and also accurate measurements from better sensors for comparison from a rotating platform. Most of the measurements are with some kind ...
1
vote
1answer
131 views

How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?

I am trying to find the frame check sequence in cyclic redundancy check(CRC). Given that the generator polynomial is $\ g(x)= (x+1)(x^3 + x^2 + 1)$. Let's say the data sequence is $\ 10110001$. In ...
1
vote
0answers
16 views

What is the motivation for the defining smooth locally decodable codes?

I am interested to understand why smooth locally decodable codes were defined historically as they were (I believe it may be because they make for easier analysis in obtaining lower bounds on locally ...
1
vote
1answer
436 views

Bit errors and hamming distance

I'm trying to learn for my exam and had the following practice question: Take a code with the following code words. 101100010111 110001001001 101110111011 Errors of how many bits can be corrected? ...
3
votes
1answer
232 views

What's the error-correcting capacity (randomly errors, or burst errors) of polar code?

Polar codes, invented by Arikan, with low encoding and decoding complexity. But the minimum distance of polar codes is not great. The normalized minimum distance goes to 0 with the block size. Yet, ...
0
votes
0answers
495 views

Minimum Hamming Distance of code for ASCII strings

I couldn't figure out how to answer the following question: Suppose we want to transmit a string of 3 ASCII characters, and in order to be able to detect or correct the message, we append the sum of ...
-1
votes
1answer
106 views

In the Hamming code, how many control bits are needed to be able to correct an error in 15-bits transmited

i don't know if right answer is 4 or 5 ! what did you understand from this question if it was a QCM ? thanks
1
vote
0answers
60 views

Reed Solomon - why the interest in original view decoders?

As seem in the history section of the Wiki Reed Solomon article: https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#History Efficient decoders for BCH / fixed generator polynomial ...
1
vote
1answer
1k views

Hamming distance and parity

For an Hamming code of $n$ bit there are $k$ bit reserved for the data and $p$ bit for the parity where $p$ is the minimum integer for which the following inequation is satisfied: $$2^p \geqslant p + ...
2
votes
1answer
765 views

What is the error-detection-probability of CRC

I have a table which stores all serial numbers of devices in my system: ...