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

learn more… | top users | synonyms

3
votes
1answer
60 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
25 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
20 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 ...
16
votes
4answers
3k 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 ...
4
votes
0answers
47 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
32 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
31 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?
3
votes
0answers
29 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 communicate a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. ...
0
votes
2answers
22 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?
36
votes
8answers
9k 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
40 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 ...
0
votes
1answer
1k 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
40 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
58 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
50 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
97 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
385 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
24 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
141 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 ...
2
votes
2answers
70 views

How to determine letter boundaries in Huffman encoded strings?

I'm trying to understand the Huffman compression algorithm. Lets assume the word : YESSSS According to Huffman tree we will get : S : 4 times -> Code : 0 Y : once -> Code : 01 E : once -> ...
9
votes
0answers
353 views

Huffman tree and maximum depth

Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?
1
vote
1answer
68 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 ...
4
votes
1answer
61 views

How many sequences in a prefix code can be compressed by m bits?

I have a little understanding problem with Appendix A ("Universal Codes") in the paper "Shannon Information and Kolmogorov complexity" by Gründwald and Vitanyi (Link). At the end of page 50, they ...
2
votes
1answer
242 views

Compute minimum hamming distance of a code

How do you find the minimum hamming distance of a code? A naive way is computing the distance of each pair of codewords in our code. It becomes hard when the code is sufficiently large. Is there a ...
-1
votes
1answer
71 views

Information of a stream of bits

Here is my problem. I have to compute the amount of information that is possible to encode in a string of bits. This string of bits represent a stream. Let us call such stream as ...
6
votes
2answers
100 views

Efficiently map different codes to rotation-different codes

Let $\mathbb{F}^n_2$ denote the set of $n$-bit 0-1 strings. How to construct an efficiently computable function $f:\mathbb{F}^n_2\to \mathbb{F}^m_2 (m>n)$ satisfying that $\forall u\neq ...
-1
votes
2answers
641 views

Network modem question

How would I solve the following can anyone help me.I know MIPS is basically how many instruction the processor can do per second but what should I do? Assume that we are receiving a message across a ...
4
votes
1answer
319 views

Algorithm for determining minimal set of covering prefixes

I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set. For instance, if my set is: ...
5
votes
1answer
100 views

Application of Expander Codes

I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon ...
5
votes
4answers
462 views

No compression algorithm can compress all input messages?

I just started reading a book called Introduction to Data Compression, by Guy E. Blelloch. On page one, he states: The truth is that if any one message is shortened by an algorithm, then some ...
5
votes
2answers
471 views

What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?

I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary. The standard binary golden ratio notation works but is horribly space inefficient. The Balanced ...
7
votes
1answer
124 views

Prove fingerprinting

Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c ...
3
votes
1answer
619 views

Encoding the sequence 0110 and determining parity, data bit and value

I've been struggling with several Hamming code/error detection questions because the logic behind it doesn't seem to make sense. eg.1 eg.2 I don't really understand the above two examples and ...
8
votes
1answer
158 views

Error-correcting rate is misleading

In coding theory, 'how good a code is' means how many channel errors can be corrected, or better put, the maximal noise level that the code can deal with. In order to get better codes, the codes are ...