Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
25 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
25 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
20 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
28 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
513 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
36 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
73 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
13 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
284 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
129 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
291 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
74 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
48 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
591 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
411 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
270 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
23 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
42 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
56 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
41 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
53 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
48 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
71 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
241 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
557 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
369 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)$...
6
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
90 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
195 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
169 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
72 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
481 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
624 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
352 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
101 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
262 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
449 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 ...
3
votes
1answer
4k views

Two dimensional parity check

Firstly, I would like to apologize if I misplaced this topic / i think the theory of coding is close to CS / I am little bit confused right now, in the school we were learning about Hamming's code, ...
2
votes
2answers
2k views

Hamming code — identical parity bits for different errors

(7,4) Hamming Code (HC) detects all 2-bit errors and corrects all 1-bit errors. However, there can be 2-, 3- or 4-bit errors that come with the same parity bits as that of 1-bit errors. Eg.: Let ...
-1
votes
1answer
1k views

use of Hamming Distance in Communication Networks

I am trying to put things in places on the use of Hamming Distance (HD) in error detection and correction in Computer Networks. I'm looking for correction/verification on the following: HD is a ...