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
1answer
13 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
32 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
16 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
29 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
45 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
26 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
34 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
16 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
36 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
594 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
75 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
14 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
307 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
145 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
311 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
79 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
630 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
459 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
274 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
24 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
45 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
57 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
46 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
44 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
71 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
61 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
54 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
49 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
73 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
247 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
606 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
395 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
79 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
91 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
196 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
171 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
73 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
495 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
638 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
369 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
105 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 ...
3
votes
0answers
3k views

Merits and demerits of convolutional and linear block codes

Continuing on from my previous post... Both convolution and linear block codes can be used for error correction. The main benefits I gathered from using convolutional codes is that, it's easy to ...
1
vote
1answer
268 views

Convolutional and Linear block codes

Both convolution and linear block codes can be used for error correction. The main benefits I gathered from using convolutional codes is that, it's easy to implement and does better (than linear codes)...
5
votes
2answers
7k views

Difference between CRC and Hamming Code

I am a bit confused on the difference between Cyclic Redundancy Check and Hamming Code. Both add a check value attached based on the some arithmetic operation of the bits in the message being ...
-1
votes
2answers
1k views

Conditions that should be satisfied by the Generator Function to detect odd number of bits in error

"Let $G\left ( x \right )$ be the generator polynomial used for CRC checking.What is the condition that should be satisfied by $G\left ( x \right )$ to detect odd number of bits in error? a) $G\...
1
vote
2answers
473 views

Why is Hamming Weight (in the CRC context) independent from the data?

I'm designing a communication protocol for 24 to 52 bits (typically 32 bits) data including the CRC-8 for error detection. I'm trying to select the best polynomial for this kind of application. In ...