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
0
votes
0answers
14 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
32 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
20 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
41 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
28 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
29 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
2answers
75 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
26 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
46 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
357 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
40 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
11 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
54 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
23 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
60 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
40 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
23 views

MDS codes with a given proportion of weights

I was trying to understand the hamming weight distribution of codewords in MDS codes. I read (https://wiki.cse.buffalo.edu/cse545/content/mds-codes) the following: Let C be a $[n, k, d]$ MDS code . ...
0
votes
0answers
31 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
37 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
48 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
133 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
43 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
20 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
73 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
87 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
40 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
27 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
52 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
22 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
164 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
42 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
130 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
432 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
211 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
438 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
105 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
59 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
978 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
717 views

What is the error-detection-probability of CRC

I have a table which stores all serial numbers of devices in my system: ...
-1
votes
1answer
340 views

Hamming distance [duplicate]

I have some difficulties in computing Hamming distance in following example: 11100000 00011100 10010010 01001001 I know the definition of Hamming distance (in case of two codewords) but how to ...
2
votes
0answers
29 views

Claimed issue with polynomial interpolation for Reed Solomon

The wiki article for Reed Solomon error correction includes the following statement near the end of this section: https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Syndrome_decoding ...