The study of data representations that enable error detection, error correction and/or compression.

learn more… | top users | synonyms

-1
votes
1answer
32 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
1
vote
0answers
44 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. ...
0
votes
1answer
53 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(...
0
votes
0answers
97 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 ...
3
votes
0answers
44 views

Find the actual codeword

Let $ C $ be a reed solomon code with length $6$, dimension $2$ and distance $5$. Suppose that we are over $\mathbb{F}_7$ and we have the genrator polynomial $g(x)=(x- \alpha)(x- \alpha^2) (x- \alpha^...
0
votes
0answers
10 views

How to analysis the relationship between the accuracy of erasure and the probability of decoding in RS code [closed]

As we all know, in RS code, when provide erasure (the position of error symbol), the decoding capacity of RS code is stronger. Specifically, *2*e+v <= (n-k)*, where e is the number of errors, v ...
0
votes
1answer
57 views

How do I calculate MDS codes?

We are given $n, m$ with $n - m > 1$. Let $S$ be the set of all $n$-bit words. Form $2^{n-m}$ disjoint subsets of $S$ of size $2^m$, denote a typical one of them by $A$, and let $B = S \setminus A$....
3
votes
1answer
43 views

Property of cyclic codes

Let $C$ be a $[n,k]$ cyclic code over $\mathbb{F}_q$ with $(n,q)=1$. I want to show that $(1, \dots, 1)$ is a codeword iff $X-1 \nmid g(X)$. $g(x)$ is the generator polynomial. We suppose that $(1, ...
5
votes
1answer
42 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 ...
0
votes
0answers
11 views

Encoding the clock signal in ldpc codes

I am aware that with convolutional coding, it is possible to encode the clock signal into the packet. However, is the same possible for linear block codes such as LDPC? I am not so sure it is, because ...
0
votes
1answer
26 views

Relation between covering radius and columns of parity check matrix

Let $C$ be a $[n,k]$ linear Code over $\mathbb{F}_q$ . I want to show that each vector of $\mathbb{F}_q^{n-k} $ is written as a linear combination of $m$ columns of $H$ iff $\rho \leq m$. I have ...
0
votes
1answer
25 views

Covering radius of code

Let $C$ be a $[n, k]$ linear code over $\mathbb{F}_q$. I want to calculate the covering radius of the Hamming codes. I have thought the following: Since the Hamming distance is $3$, the coverig ...
2
votes
1answer
37 views

Lower bound on the covering radius of a code

Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$. Suppose that $\rho$ is the covering radius . I want to show that $\rho \geq \frac{n-k}{1+ \log_q{(n)}}$. Could you give me a hint how we could ...
0
votes
1answer
29 views

Upper bound on the covering radius of a code

Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$. Suppose that $\rho$ is the covering radius . I want to show that $\rho \leq n-k$. Could you give me a hint how we could show this? The ...
1
vote
1answer
89 views

Existence of Hamming code

We are given a number $n \geq 3$ and we know that the Hamming bound is satisfied. Does this imply that there is a Hamming code with length $\frac{q^r-1}{q-1}$, dimension $\frac{q^r-1}{q-1}-r$ and ...
1
vote
1answer
36 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 $ ...
3
votes
1answer
32 views

How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme ...
3
votes
1answer
18 views

Compactly representing integers when allowed a multiplicative error

Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$. Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits. In contrast, assume we are ...
1
vote
2answers
48 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
51 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 ...
4
votes
1answer
122 views

Huffman Coding and Depth Calculation?

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without ...
1
vote
2answers
63 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 ...
4
votes
1answer
62 views

Number of words within Hamming distance $\delta$

This is a problem I'm having reading Arora & Barak's book, page 378-379. They define: For two words $x, y \in \{0, 1\}^m$, the fractional Hamming distance of $x$ and $y$ is equal to the ...
3
votes
1answer
61 views

Need help understanding textbook solution

I am studying for my final exam in coding-theory class, and as textbook provides poorly written solution to the exercise question, I decided to ask the question here, hoping for more clarification. ...
4
votes
1answer
197 views

Is there a generalization of Huffman Coding to Arithmetic coding

In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of fuffman coding to be related to the problem of fractional ...
2
votes
1answer
171 views

coding theory- perfect codes

I'm new to stackoverflow so please bear with me. A tutorial question I got given was as follows: You are given that $C \subseteq D \subseteq F^n_q$ where $|C| < |D|$ and $C$ is a perfect code. ...
2
votes
1answer
175 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, ...
6
votes
1answer
205 views

What is the algorithm for Shannon-Fano code? am I correct?

I am wondering what is the true algorithm for the Shannon-Fano code? The the result I am getting based on the Algorithm in Wikipedia page contradicts the supposed/expected length of the produced code. ...
-1
votes
1answer
57 views

Communication Complexity and Prefix Codes [closed]

I need an advice. There is in section "V. CONCLUDING REMARKS" of the paper [1], a term that only the autho's paper use: "PREFIX CODING COMMUNICATION". I googled the expression and the only result ...
2
votes
2answers
190 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
226 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 ...
6
votes
3answers
175 views

Binary code with constraint

Suppose I have an alphabet of n symbols. I can efficiently encode them with $\lceil \log_2n\rceil$-bits strings. For instance if n=8: A: 0 0 0 B: 0 0 1 C: 0 1 0 D: 0 1 1 E: 1 0 0 F: 1 0 1 G: 1 1 0 H: ...
2
votes
1answer
58 views

What does feedforward inversion mean in the context of convolution and catastrophic codes?

i'm reading the article of J. L. Massey and M. K. Sain, "Inverses of Linear Sequential Circuits" (Date of Publication - April 1968) (here) and i cannot understand - what is "feedforward inversion"? ...
3
votes
1answer
35 views

How is the Varshamov-Tenegolts code decoded?

For $0 \leq a \leq n$ the VT code $VT_a(n)$ consists of all tuples $(x_1,x_2,..,x_n) \in \{ 0,1\}^n$ such that $ \sum_{i=1}^{n} ix_i = a (mod (n+1))$ For example $VT_0(4) = \{ 0000,1001,0110,1111 \}$ ...
3
votes
1answer
66 views

About codes over $\mathbb{F}_2$

I was looking through these notes but I am not sure I can locate the answer to these questions of mine - it would be great if someone can just even point out what to look for! So any set of binary ...
2
votes
0answers
28 views

Looking for some lossless compression theory [duplicate]

I'll apologize in advance if anything in here is ineloquent. Suppose we have a pair of lossless compression (C) and decompression (...
1
vote
0answers
32 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 ...
17
votes
4answers
7k views

Is Morse Code binary, ternary or quinary?

I am reading the book: "Code: The Hidden Language of Computer Hardware and Software" and in Chapter 2 author says: Morse code is said to be a binary (literally meaning two by two) code because ...
5
votes
1answer
60 views

Do correlated inputs imply existence of efficient communication protocols?

Suppose that I have 2 parties Alice and Bob. Alice gets an input $X$ and Bob gets input $Y$ where $X, Y$ are $n$-bit strings. In the classic communication complexity world, computing a function such ...
1
vote
0answers
46 views

What is the theory foundation of the binary encoding of data digits into an EAN-13 barcode? [closed]

In the Wikipedia, there is explanation about EAN-13 and several table, which are called "Structure of EAN-13" and "Encoding of the digits", but I did not know what theory the contents of the two ...
0
votes
1answer
56 views

Hamming and BCH codes

Why are Hamming codes the best 1-error-correcting codes? I need references. I know that hamming codes are the best 1-error-correcting codes but I want to know why they are best?
5
votes
0answers
47 views

Name of a type of code similar to block codes

I've encountered a system where I need to construct a sort of quasi block code: We want to encode a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. The $i^{...
0
votes
2answers
25 views

Why are long block lengths commonly assumed/used in channel coding proofs?

As the title states, why are long block lengths commonly assumed or used in channel coding proofs?
43
votes
8answers
13k views

Is Morse code without spaces uniquely decipherable?

Are all Morse code strings uniquely decipherable? Without the spaces, ......-...-..---.-----.-..-..-.. could be Hello World ...
2
votes
1answer
62 views

Is the Source Coding Theorem straightforward for uniformly distributed random variables?

Shannon's source coding theorem states the following: $n$ i.i.d. random variables $X_1,\dots,X_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of ...
1
vote
1answer
381 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
9k views

Hamming distance required for error detection and correction

I have already asked a pair of questions on the hamming distance, hamming code, valid and invalid codewords on this website, because I cannot understand those concepts fully, and in a few weeks or ...
2
votes
1answer
65 views

Typical set in Shannon's source coding theorem

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of $N$ $i.i.d$ random ...
2
votes
1answer
68 views

Source Coding Theorem: what happen when go below N⋅H(x) bits?

I was following the text book by David Mackay: information theory inference and learning algorithms, this could be found online on his website. I have question on the source coding theorem (emphasis ...