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.
122
questions
1
vote
1
answer
26
views
How can a fault tolarent Distributed Data Saving Algorithm can be developed?
I am trying to design an algorithm. For now, I am trying to give myself a large overview.
Assume I have K (for example, K can ...
- 155
0
votes
1
answer
50
views
What are the best parameters possible from a binary linear LDPC code where each parity-check matrix is the incidence matrix of a graph?
There is an obvious construction of linear codes from graphs, where each codeword is a cycle in the graph. Physical bits are edges in the graph, and constraints are vertices.
This has been used in the ...
- 1
0
votes
0
answers
24
views
Multi Edge Type LDPC codes - How to construct H?
I need to create a parity-check matrix, H, for a MET-LDPC code.
I know that H will still be two-dimensional and have only 0s and 1's, just like "normal" LDPC codes.
I am aware of the ...
- 1
1
vote
0
answers
16
views
Error correcting codes for stream of unkown size
Is there any algorithms like Reed Solomon that work for a stream of unknown data? The stream is finite but size is unknown until the stream ends.
I found some information about sliding window reed-...
- 111
1
vote
0
answers
30
views
Name for class of error-correction codes
I'm considering a binary error-correction scheme, but I'm missing the correct terms to dig further into it.
The idea is to decide the code-rate during encoding, but for the decoder to decide how that'...
- 111
3
votes
0
answers
19
views
Binary codes with analog like qualities
I want to transmit values over an error prone channel. When transmitting analog values, the precision degrades smoothly when the transmission becomes worse. But when transmitting binary integers, an ...
- 131
0
votes
0
answers
22
views
How is this code derived from the concatenated Walsh-Hadamard Reed-Solomon code?
Background
Let $n, m \in \mathbb{N}$ with $n < m$. We call $C : \{0, 1\}^n \rightarrow \{0, 1\}^m$ an error correcting code of distance $\delta \in [0,1]$ if for any distinct $x^1, x^2 \in \{0,1\}^...
- 353
3
votes
0
answers
71
views
Lights-out! on a hex grid with buttons on nodes and lights on faces
Consider a truncated hexagonal grid, with some hexagons lit up, such as the one shown below:
Here the red hexagons are lit up while the dark gray hexagons are not lit up. The grid has buttons (small ...
- 5,802
0
votes
0
answers
31
views
Encoding and Decoding
I am trying to find an encoding function e:{0,1}^20→{0,1}^10 and a decoding function d:{0,1}^10→{0,1}^20. Goal is to find d and e so that maxBdH(d(e(B)),B) is as small as possible. Here, dH denotes ...
1
vote
2
answers
51
views
Am I right that Reed-Solomon codes can be used to implement arbitrary-parity RAID schemes?
I guess the question does not apply just to CS as I'm trying to understand how it applies to RAIDs, but I guess it's maybe the most suitable place to ask anyway.
There's a lot of info that RS codes ...
- 145
1
vote
0
answers
25
views
Chien search complexity
I am working on Reed-Solomon decoding, where Chien search is used to determine the roots of the so-called locator polynomial. From my understanding, Chien search consists in trying every possible ...
user16034
-2
votes
1
answer
43
views
Consider a Hamming(7, 4) code and the word 1111111 received at the output of a noisy binary channel
Why is it possible that this word can have 4 errors but not 2?
- 5
4
votes
0
answers
27
views
Error correcting codes for transmitting a real value $x$ in [0,1], minimizing the reconstructed distance to the original $x$
I have been thinking a bit about error correcting codes, in particular the following problem:
Consider the problem of transmitting a single real number $x \in [0,1]$ over a lossy connection, where ...
- 41
1
vote
2
answers
215
views
Why does a CRC detect burst errors of longer than r+1 bits independently of burst length?
In this question it is stated that a CRC detects burst errors of length greater than the CRC length with probability $1-2^{-r}$, where $r$ is the length of the CRC.
Why is there no dependence on the ...
- 113
0
votes
0
answers
40
views
Algebra of error models and error correcting codes?
In coding theory we typically consider the situation where we have a
channel that connects a sender and receiver. The messages flowing from
the sender to the receiver are corrupted by an error source ...
- 8,308
3
votes
0
answers
123
views
Verify if array is orthogonal
Orthogonal arrays often appear in probabilistic algorithms. They can be efficiently constructed from, e.g., BCH codes.
But is there an efficient algorithm that can verify if an array is orthogonal? I ...
- 125
1
vote
0
answers
117
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 ...
- 11
2
votes
1
answer
23
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 ...
- 991
1
vote
0
answers
28
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 ...
- 111
2
votes
1
answer
61
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 ...
- 11.5k
3
votes
1
answer
36
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, ...
- 33
1
vote
2
answers
33
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 ...
- 155
2
votes
1
answer
50
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$...
- 123
0
votes
0
answers
118
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)$,...
- 246
3
votes
2
answers
238
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 ...
1
vote
1
answer
47
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 ...
- 121
2
votes
1
answer
274
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 ...
- 41
2
votes
1
answer
116
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 ...
- 732
1
vote
0
answers
40
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 ...
- 21
1
vote
1
answer
204
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:
...
- 111
1
vote
2
answers
83
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
1
answer
222
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 ...
0
votes
2
answers
222
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
1
answer
45
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
1
answer
66
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
3
answers
127
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
0
answers
229
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} ...
- 51
2
votes
2
answers
119
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
1
answer
37
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 ...
- 213
2
votes
1
answer
526
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 ...
- 1,637
3
votes
1
answer
3k
views
Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code
I found a highly optimized CRC-16 implementation originally intended for microcontrollers. It is noticeably faster than the traditional method, but is hard-coded to model the specific unreflected ...
- 185
1
vote
3
answers
277
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 ...
- 11
1
vote
0
answers
26
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?
- 11
0
votes
1
answer
136
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 (...
- 73
0
votes
0
answers
42
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 ...
- 55
1
vote
1
answer
44
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 ...
- 125
2
votes
0
answers
19
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 ...
- 121
3
votes
2
answers
197
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$.
...
- 31
1
vote
2
answers
306
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 ...
- 125
0
votes
0
answers
41
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:...
