# 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.

98 questions
Filter by
Sorted by
Tagged with
14 views

It is given in the book by El Gamal that The capacity region of the DM-BC depends on the channel conditional pmf $p(y_1 , y _2 |x)$ only through the conditional marginal pmfs $p(y_1 |x)$ and $p(y_ 2 |... 0answers 32 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 ... 0answers 32 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: ... 2answers 20 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 ... 1answer 26 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 ... 1answer 41 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 ... 1answer 28 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 ... 1answer 29 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 ... 2answers 75 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 ... 0answers 198 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} ... 2answers 26 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 ... 1answer 25 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 ... 1answer 46 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 ... 0answers 357 views ### Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code I have some highly optimized code for a CRC-16 implementation. It focuses on speed rather than flexibility, and as a result, it is hard-coded to model the specific unreflected polynomial ... 2answers 40 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 ... 0answers 20 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? 0answers 11 views ### distance of a code name in scheme i wonder: is it true that if we take a information word, call it M(with m bits) for example, and code it by first coding M using a code, that we don't know anything about, except of it a length of k, ... 1answer 54 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 (... 0answers 23 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 ... 1answer 18 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 ... 0answers 14 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 ... 2answers 60 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$. ... 2answers 40 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 ... 0answers 23 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 . ... 0answers 31 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:... 1answer 37 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 (... 2answers 48 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]:...
133 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 ...
43 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 ...
20 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 ...
73 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: ...
87 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 ...
40 views

717 views

### What is the error-detection-probability of CRC

I have a table which stores all serial numbers of devices in my system: ...