Skip to main content

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
0 answers
22 views

Recovering Examples Tanner Code Constructions

I've been trying to understand how the construction of Tanner codes works. The only example that I've found is in Tanner's original paper. However, I can't recover the claimed code parameters, and I ...
DaftWullie's user avatar
0 votes
1 answer
40 views

How are non-binary codes implemented in practice, i.e. codes over $\mathbb{F}_q^n$ for $q\neq 2$?

I am only familiar with binary implementations of information, though I am aware other implementations (ternary etc.) exist. I was wondering, if a code over $\mathbb{F}_q^n$ is used in practice, where ...
JoJo P's user avatar
  • 101
0 votes
0 answers
11 views

Determining the benefit from increasing bits available in base 32 checksum

I'm looking at using something like Crockford Base-32 encoding in a situation where people have to manually write IDs in a very compact space. Crockford Base-32 describes a simple checksum algorithm ...
anjama's user avatar
  • 181
1 vote
1 answer
29 views

Why, for Reed-Solomon codes, does the alphabet size depend on block length?

I'm learning about Reed-Solomon codes so apologies if this is a basic question. The alphabet size $q$ in RS codes grows with the block length $n$ - in particular, we have $q \geq n$. But intuitively, ...
user1936752's user avatar
1 vote
1 answer
43 views

Why is the block size chosen to be q-1 for Reed-Solomon codes?

Consider a Reed-Solomon code over a finite field of $\mathbb{F}_q$. Why is the typical block size chosen to be $q-1$ [1][2][3]? The reasoning I saw around this is ...
mutantacule's user avatar
2 votes
0 answers
17 views

Are there any forward error correcting code algorithms for a partially reliable channel?

There exist plenty or practical FEC algorithms - RS, Golay, convolutional codes of all sorts. All of them assume that the original data and the FEC code are sent over the same channel with the same ...
Andrey L's user avatar
1 vote
1 answer
28 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 ...
Sean's user avatar
  • 155
0 votes
1 answer
61 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 ...
AKC's user avatar
  • 1
0 votes
0 answers
41 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 ...
StuKers's user avatar
1 vote
0 answers
18 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-...
Miguel Ping's user avatar
1 vote
0 answers
31 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'...
cloudfeet's user avatar
  • 111
3 votes
0 answers
20 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 ...
Wolfgang Brehm's user avatar
3 votes
0 answers
82 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 ...
Craig Gidney's user avatar
  • 5,862
0 votes
0 answers
53 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 ...
Ahsan Ali's user avatar
1 vote
2 answers
62 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 ...
ledonter's user avatar
  • 145
-2 votes
1 answer
81 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?
PTSONIC's user avatar
4 votes
0 answers
28 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 ...
almostuseful's user avatar
1 vote
2 answers
428 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 ...
ose's user avatar
  • 113
0 votes
0 answers
43 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 ...
Martin Berger's user avatar
3 votes
0 answers
124 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 ...
yarchik's user avatar
  • 125
1 vote
0 answers
160 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 ...
sayanc2011's user avatar
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 ...
gen's user avatar
  • 991
1 vote
0 answers
32 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 ...
Lukas Räpple's user avatar
2 votes
1 answer
74 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 ...
nir shahar's user avatar
  • 11.6k
3 votes
1 answer
41 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, ...
J Bausch's user avatar
1 vote
2 answers
35 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 ...
Moonwalker's user avatar
2 votes
1 answer
55 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$...
Chris's user avatar
  • 123
0 votes
0 answers
161 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)$,...
roydiptajit's user avatar
3 votes
2 answers
342 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 ...
Powerful blaster's user avatar
1 vote
1 answer
48 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 ...
dohmatob's user avatar
  • 121
2 votes
1 answer
403 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 ...
Road's user avatar
  • 41
2 votes
1 answer
156 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 ...
Rainer P.'s user avatar
  • 852
1 vote
0 answers
46 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 ...
Rapiz's user avatar
  • 21
1 vote
1 answer
334 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: ...
Paul's user avatar
  • 111
1 vote
2 answers
104 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 ...
Nurin Izzati Jafri's user avatar
1 vote
1 answer
282 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 ...
Nurin Izzati Jafri's user avatar
0 votes
2 answers
316 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 ...
Nurin Izzati Jafri's user avatar
1 vote
1 answer
52 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 ...
Nurin Izzati Jafri's user avatar
2 votes
1 answer
75 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 ...
Nurin Izzati Jafri's user avatar
0 votes
3 answers
129 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 ...
Jack Fleming's user avatar
1 vote
0 answers
230 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} ...
Rapiz's user avatar
  • 51
2 votes
2 answers
156 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 ...
Nurin Izzati Jafri's user avatar
3 votes
1 answer
40 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 ...
introspec's user avatar
  • 213
2 votes
1 answer
808 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 ...
RajS's user avatar
  • 1,677
4 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 ...
bryc's user avatar
  • 205
1 vote
3 answers
320 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 ...
Hamming's user avatar
  • 11
1 vote
0 answers
32 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?
Turingable's user avatar
0 votes
1 answer
206 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 (...
NoNeural's user avatar
0 votes
0 answers
49 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 ...
alberto123's user avatar
1 vote
1 answer
57 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 ...
user2723984's user avatar