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
2answers
11 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
12 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
28 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
34 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
25 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
36 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
1answer
36 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
18 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
45 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: ...
1
vote
1answer
52 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
31 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
21 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
40 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
18 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
60 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
729 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
38 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
86 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
15 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
326 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
166 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
344 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
85 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
51 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
713 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
506 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
287 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
26 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 ...
2
votes
1answer
47 views

Analysis of brute force decoder in a $q$-ary erasure channel

Consider the $q$-ary erasure channel with erasure probability $\alpha$, i.e. given $x\in\mathbb{F}_q$ with probability $\alpha$ it outputs $?$ and with probability $1-\alpha$ outputs $x$. For a ...
1
vote
0answers
59 views

Error correction codes - with strong noise [closed]

I was reading this answer on how error-correction works on magnetic tape recorders for the Voyager space probes. After watching one or two youtube videos I understand the principle of Hamming-coding ...
1
vote
0answers
48 views

How an insertion can be decoded in Varshamov and Tenengolts (VT) codes

I have a good idea of how deletion can be decoded in VT codes using Levenshtein algorithm. However, I don't have any idea how can an insertion be decoded? Can anybody give me a small example using a ...
1
vote
0answers
45 views

Soft binary ECC? How to maximize the minimum distance over a channel?

Given that The channel is tiny, it has message size of 72 bits Each bit is probabilistic, meaning that I have a value between 0 and 100 of how likely that bit is on/off1 Only 24 bits of acutal data ...
2
votes
0answers
75 views

Vandermonde matrix and its binary representation

Say one is given a Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) of dimension $2^q \times k$ such that the elements of the first column of it are $\{0,1,2,..,-1+2^q\}$. (This ...
2
votes
0answers
64 views

Error detection code supporting arithmetic

I am looking for error detection codes, which support addition in the encoded domain and are separate (a tuple of ($N$, $R(N)$), where $N$ denotes the functional value and $R(N)$ its redundancy). So ...
2
votes
0answers
55 views

Forward error correction for for long strings of bits

Let $a$ be a large string of bits that is transmitted over a channel that introduces errors (insertions, deletions or substitutions) where the probability of an error happening is $p=0.01$ for each ...
1
vote
0answers
52 views

Hirschberg's algorithm for long strings of bits

Let $a$ be a large string of bits that is transmitted over a channel that introduces errors (insertions, deletions or substitutions) where the probability of an error happening is $p=0.01$ for each ...
2
votes
0answers
80 views

Code families with efficient decoding algorithms

Which families of the error correcting codes have an efficient decoding algorithm? I know that decoding a general linear code is NP hard (the general decoding problem). I also know that Goppa codes ...
3
votes
1answer
265 views

Showing that a binary linear code $C$ is self-dual

Let $C*$ be the length 8 binary code obtained by adding a parity check symbol to each word in $C$. (so a word $c_1, c_2, c_3, c_4, c_5, c_6, c_7$ is extended to the word $c_1, c_2, c_3, c_4, c_5, c_6,...
3
votes
1answer
650 views

Decoding a binary linear code given its generator matrix

Let $C$ be the binary linear code with the following generator matrix $G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & ...
0
votes
1answer
416 views

Support of a codeword in a binary linear code proof

Let $C$ be the binary linear code with the following generator matrix $G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & ...
3
votes
0answers
57 views

Separate arithmetic codes closed under addition

For error detection purpose I am looking for separate arithmetic codes which are closed under integer addition. By separate, I mean the code word $C$ for message $x$ is a tuple $(x,f(x))$ where $f(x)$...
5
votes
2answers
82 views

Protecting data unequally using Error Correction Codes

Say I'd like to transmit a 100-bit packet which has a field containing a continuous value. I'd like to protect this value with an error correction code but an error in the MSB of this value is much ...
0
votes
1answer
94 views

CRC error detection

I know that to find an error in signal we have to divide given signal with given polynomial and if 0 remains there is no error. But if I have received signal: 0000 0101 0101 0000 1010 0101 and ...
8
votes
1answer
202 views

Does there exist a Reed-Solomon-like code over decimal symbols?

A Reed-Solomon error-correcting code consisting of N symbols is guaranteed to detect up to N single-symbol replacements in an arbitrarily long input plus the ECC itself, and is also guaranteed to ...
6
votes
1answer
177 views

Error correcting permutation code

Let's say you have $n$ symbols. You can encode a $\log_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a ...
0
votes
1answer
74 views

Capacity of binary not symmetrical channel

I have to solve this exercise in information theory: A binary not symmetrical channel has probability of transition from 0 to 1 $P(output=1|input=0)=p$ and probability of transition from 1 to 0 $P(...
1
vote
0answers
535 views

How do I compute a “CRC code word” from an information word and CRC polynomial?

I have the CRC polynomial 1101, and my information word is 10001111. How do I find the CRC code word? Disclaimer: This is an assignment problem. I'd appreciate any help, particularly solving the ...
5
votes
1answer
669 views

Correcting two-bit error using a CRC

What algorithm can be used to correct a two-bit error in a message protected by a 32-bit CRC, assuming the CRC polynomial allows that? I'm seeking something for 480-bit payload, able to detect ...
5
votes
1answer
395 views

How to pick Hamming distance

Wikipedia's article Cyclic redundancy check states that for the same n (bits) there are multiple CRCs possible with different polynomial. Then it lists this Best CRC Polynomials article that gives ...
1
vote
0answers
111 views

Training preamble in convolutional codes

as I was examining the VirtualWire library used in Arduino projects, I noticed that the header of the messages that are transmitted begin with a 36 bit "training preamble." What exactly is a training ...