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

learn more… | top users | synonyms

0
votes
1answer
46 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 ...
3
votes
1answer
39 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
33 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
23 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
22 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
35 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
27 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
80 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
33 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
30 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
45 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
49 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
116 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
57 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
59 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. ...
3
votes
1answer
172 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
167 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
129 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
171 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
56 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
144 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
192 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
173 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
57 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
34 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
30 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
59 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
43 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
53 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 ...
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?
42
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
58 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
369 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
8k 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
64 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
67 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 ...
1
vote
1answer
51 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 ...
3
votes
1answer
162 views

Error-correction code for transmission only with bit-flipping from 0 to 1

I am using a transmission system that uses a Bloom filter (this part is out of my control). I want to send a small amount of data (32 bits) using this system. For each bit [0,31], I add its index to ...
0
votes
0answers
16 views

How to decode multiple-digit gamma codes and get the gap sequence? [duplicate]

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
2
votes
2answers
686 views

How to decode multiple-digit gamma codes and get the gap sequence?

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
3
votes
1answer
31 views

Lexicographical position of a string in its type class

I have the following problem: Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists ...
5
votes
1answer
160 views

Are Lie theoretic codes impractical?

I have been recently studying Lie theory. I discovered that there is a family of Lie theoretic error correcting codes. I did not find any information except this paper: “Representations of Lie ...