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.

109 questions
Filter by
Sorted by
Tagged with
21 views

...
21 views

How to decode shortened Reed-Solomon code?

I am working with a shortened version of $[n,k,d]$ Reed-Solomon code. I am encoding a message of size $k−l$ which gives a shortened code of size $n−l$ (this is equivalent to encoding the same message ...
22 views

Number of signatures of each type in a fixed column set of the Hadamard matrix

Consider a $2^n \times 2^n$ Walsh-Hadamard matrix (via Sylvester's construction). Fix a set $S \subset [2^n]$ of $k\leq 2^{n-1}$ columns. Consider the rows in the $2^n \times k$ submatrix $H'$ that's ...
11 views

What is the difference between erasure coding and RAID if your erasure code is parity check?

I'm reading about erasure coding and saw that one of the erasure codes is parity check. As far as I can tell this is just a generalization of something like RAID5. If you select something like parity ...
22 views

Even parity applied on bits, that don't follow the rules of even parity

The following example is given: The sender and receiver are using 1 bit even parity The sender is sending 1110 1010 over a noisy channel. in case 1 the receiver gets 1110 1100 in case 2 the receiver ...
45 views

Existence of good error correcting codes

I recently asked this question and got an answer from Yuval Filmus stating that we can build a solution using error-correcting codes. More specifically, I'm looking for error correcting codes (for ...
31 views

Is an AND gate which is noisy 1/3 of the time on only one of its inputs universal?

Imagine you have a noise-free NOT gate, and an AND gate with the usual truth table 00 0 01 0 10 0 (*) 11 1 but such that the case (*) is wrong 1/3 of the time, ...
30 views

Error correction for windowed reads from cyclic tapes

I have an array of N symbols written on a cyclic tape. I read a sequence of M symbols starting from a random place on the tape. What error correcting scheme and even a coding scheme should I use for ...
36 views

On the definition of Error-Correcting Codes

Let us start with the following well-known definition: Definition 1. Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer. We say that the code $C$ is $\boldsymbol t$...
73 views

Epsilon balanced Code

A linear code is termed as an $\epsilon -$balanced code if all the codewords are having fractional hamming weight $\in (1/2-\epsilon,1/2+\epsilon)$. I want to show that for every $\epsilon\in (0,1/2)$,...
99 views

How to recognise the number of errors that can be detected and corrected of a large set of codewords (k) each having a specified number of bits (n)?

I am struggling to find how can I know the number of errors that can be corrected and detected using (n=10) bit code with a (k=550) codewords. As far as I know, to calculate the number of errors to be ...
28 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 ...
115 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 ...
50 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 ...
33 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 ...
71 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: ...
54 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 ...
122 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 ...
110 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 ...
36 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 ...
42 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 ...
115 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 ...
205 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} ...
58 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 ...
31 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 ...
248 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 ...
1k 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 ...
125 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 ...
23 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?
79 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 (...
26 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 ...
21 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 ...
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 ...
111 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$. ...
92 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 ...
39 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:...
55 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 (...
161 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]:...
399 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 ...
65 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 ...
32 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 ...
102 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: ...
113 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 ...
55 views

218 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 ...