Questions tagged [coding-theory]
The study of data representations that enable error detection, error correction and/or compression.
183
questions
1
vote
1answer
20 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 ...
1
vote
1answer
44 views
Which algorithm to detect errors in 32bit data with 8bit parity
I want to transmit a 32bit message in eight groups of 5bit each. This leaves me with 8bits to use for error checking.
Overall, a group is likely transmitted without error, but when there is an error ...
1
vote
1answer
25 views
Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source?
The product of 2 independent sources $(S_A,P_A)$ and $(S_B,P_B)$ is defined as
$$
(S,P)\text{ s.t. }S = \{s_As_B|s_A\in S_A,s_B\in B\}\text{ and }\ P(s_As_B) = P_A(s_A)\cdot P_B(s_B)\,\forall s_A\in ...
1
vote
1answer
178 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 ...
1
vote
1answer
34 views
Gray-like code with maximum value <= maximum value of original symbol
I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit. I'm going to be using each number as an index ...
1
vote
1answer
84 views
Properties of coset
Let $C$ be a linear code with minimum distance $2k$. I want to show that there is a coset of $C$ that contains at least two vectors of weight $k$.
Firstly, it holds that the minimum distance of the ...
1
vote
1answer
15 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 ...
1
vote
1answer
38 views
“pure” explanation of Reed-Solomon?
I encountered two applications of RS codes - one in group testing, and another time someone said that a solution to an interview question was using it. But when I search for explanations, it's all ...
1
vote
1answer
25 views
Worked out example of Slepian-Wolf Theorem
Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic.
The Slepian-Wolf theorem states that sequences of outputs from two ...
1
vote
1answer
16 views
Number of independent parity checks satisfied by a code
I have been studying quantum error correction codes and as background, I am currently studying the theory of classical linear codes. Despite many efforts, I am unable to understand the following ...
1
vote
1answer
50 views
Underlying codes for Niederreiter cryptosystems
Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$.
The minimum distance $d$ is given by
$d := min\lbrace k \text{ such that there are $k$ linearly ...
1
vote
1answer
80 views
using 2 short CRC(s) VS one longer CRC
I'm doing some research on the CRCs, but i can't find informations about the use of two (or more) short CRCs compared to the use of a longer CRC:
Suppose that i have a dataword A of some length and 3 ...
1
vote
2answers
50 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 ...
1
vote
1answer
65 views
Trouble understanding theory for error detection and correction in repetition code
Question 1
Consider a repetition code to detect $m$ errors. What is the smallest repetition parameter $k$ (i.e., the number of repetitions per bit) it should be used so that the code can always ...
1
vote
1answer
108 views
How to compare the efficiency of two encoding schemes or hypothesis languages?
My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have ...
1
vote
1answer
35 views
Two definitions of the Reed-Muller code
I found two definitions Reed-Muller codes being used in literature. More specifically for any $n \in \mathbb{Z}^+$ and $1 \leq d \leq n$ we define the set $RM(d,n)$ in two possible ways,
1.
$RM(d,n) =...
1
vote
1answer
516 views
How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer
The LZ77 compression algorithm uses a sliding window technique, where the window consists of a look-ahead puffer and a search-buffer. What I am wondering is how the algorithm handles the case if the ...
1
vote
1answer
117 views
Lower limit on the number of check bits needed to correct single errors
I was going through Andrew S. Tannenbaum's computer networks book, and on page 206 of it, he has derived the number of check bits needed to correct single bit errors. The derivation goes as follows:
...
1
vote
1answer
39 views
Problems with the proof of Huffman Optimality in Cover's book
There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me.
First question is why he assumes that we can "Consider an optimal code $C_m$. ...
1
vote
1answer
318 views
The extension of a code is itself a code
I'm reading Cover's "Elements of Information Theory" and I have a problem with the definition of uniquely decodable code.
A code is said to be singular if there exist two elements that map to
...
1
vote
1answer
835 views
Properties of self-dual code
Let $C $ be a self-dual binary $[n,k,d]$ code.
I want to show that if $ c=(c_1, \dots, c_n) \in C $ then $ \sum_{i=1}^n c_i=0$ and that all the words of the code have an even weight.
We know that $ ...
1
vote
2answers
116 views
Is there a deterministic algorithm to construct $(n,k)$-universal set of minimum size?
Let $S\subseteq \{0,1\}^n$, $S$ is a $(n,k)$-universal set if for every subset of indices $I$ of size $k$, projecting $S$ to $I$ yield the $2^k$ binary strings (all the possible strings of $I$). $S$ ...
1
vote
1answer
2k views
Compute the Hamming code with odd parity for the memory word 1101 1001 0001 1011
This is the problem I have:
Compute the Hamming code with odd parity for the memory word 1101 1001
0001 1011 (2 pts.). In your solution, mark the parity bits as in the
following example, where ...
1
vote
1answer
100 views
Algorithm for designing a binary code with predefined distance
Suppose I have a matrix $A$ with its entry $A_{ij}$ denoting some kind of distance between class $i$ and $j$, is there a feasible algorithm for computing a binary coding for all the classes, such that ...
1
vote
1answer
230 views
Error detection/correction algorithm
We have 2 stations that communicate with each other, but we need to detect (or even correct) when something is wrong.
We use 8 binary words: each consisting of 3 bits and to send it we code it as
...
1
vote
0answers
47 views
Algorithm suggestion to order data with specific condition
Suppose, we want to rearrange all possible $n$-bit binary strings (i.e., we have $2^{n}-1$ possible strings) in a 1-D array $X$; given that stings with smaller hamming distance should be placed as ...
1
vote
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 ...
1
vote
0answers
44 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:
...
1
vote
0answers
201 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} ...
1
vote
0answers
22 views
Complexity of maximization of entropy of Hamming distance of bitstrings
We have a set of possible "key"s $S$ represented by bitstrings of length $k$. In other words, $S$ contains an arbitrary subset of all bitstrings of length $k$. For example, when $k=3$, it can be $S = \...
1
vote
0answers
27 views
Minimum basis for the nullspace of sparse matrices
Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted ...
1
vote
1answer
32 views
Encoding System that Assign Same Number of Bits for Each Character
I am trying to get a binary string that has been converted from text of a text file, I am able to get that but the problem is, I need each character to be represented by same number of bits, but that ...
1
vote
2answers
68 views
Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?
With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is ...
1
vote
3answers
72 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 ...
1
vote
0answers
21 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?
1
vote
0answers
17 views
Where can I find someone that will sit with me and explain the analytics reports from my iPhone and computer? [closed]
This may seem like a dumb question to most people, BUT PLEASE READ THIS!! I AM BEYOND DESPERATE to get rid of a hacker that is digitally stalking me and terrorizing me. I picked your forum because ...
1
vote
2answers
51 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 ...
1
vote
0answers
19 views
Showing that a source is not Markov
If I have some source sending codewords and I take a large sample of codewords in order to construct an empirical distribution of the codewords sent. Using this empirical distribution, what methods ...
1
vote
0answers
49 views
Difference between a regular and a stationary source?
As far as I understand a stationary source is a regular source but it's not necessarily true the other way around.
And a stationary source is a source for which its distribution is unaffected by a "...
1
vote
0answers
12 views
LT codes with constant degree on information symbols
I have just read a Luby’s paper on the very basic idea of the LT codes, which may be of interest for me.
For my application, encoding k information symbols is done in a process that generates a big ...
1
vote
1answer
52 views
How many prefix code we can find for a given distribution of probability?
A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the ...
1
vote
0answers
57 views
Is there a database of linear codes with “small” covering radius
Does anyone keep a database of (or including) linear codes with small covering radius? I'm specifically interested in the smallest-dimension codes known of covering radius R ($2\le R \le 4$ say) for ...
1
vote
0answers
118 views
Hamming code extension with additional parity bit
Let $Ham$ be the $[7,4,3]_2$ Hamming code.
It is known that $\{w(c):c\in Ham\}\subseteq\{0,3,4,7\}$, where $w(c)$ is the Hamming weight of the word $c$.
A code $C$ of length $n$ is called cyclic if ...
1
vote
0answers
72 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
46 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 ...
1
vote
1answer
105 views
What should be the way to design code for such a situation?
I have a graph as given below:
Let us assume one node as transmitter and another as receiver.
We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The ...
1
vote
0answers
39 views
Decode Reed Muller codes efficiently given only a syndrome
So given some erroneous Reed Muller code-word's syndrome as well as the Parity-Check/Generator Matrix how would one find the error vector?
The approach I took naively was to build the syndrome table, ...
1
vote
0answers
226 views
Number of unique prefixes in canonical huffman tree
I am trying to implement decompression algorithm based on huffman trees. I am trying to validate my assumptions.
Assume that you have alphabet of 350 symbols. Maximum encoded code length is 15 bits. ...
1
vote
0answers
695 views
Efficiency of arithmetic coding
I think I know how the arithmetic coding works but what I don't understand is the reasoning about efficiency.
I have read in this pdf that the number of bits required to specify a range is greater ...
1
vote
0answers
56 views
How many parity syndromes are there?
In RAID 6, there is a parity scheme that allows 2 concurrent disk failures. This requires 2 ‘syndromes’, one of which is simply XOR, as used for RAID 5's only parity. In trying to find out whether ...
