Questions tagged [coding-theory]
The study of data representations that enable error detection, error correction and/or compression.
202
questions
1
vote
2
answers
63
views
How do I find the most even combination for two arrays
I have two arrays that both contain n elements (positive,non zero, not negative)
{x1....xn}
{y1....yn}
I want to pair them up optimally, one from each array, so that the pairs come out as even as ...
- 11
2
votes
2
answers
45
views
Am I right that Reed-Solomon codes can be used to implement arbitrary-parity RAID schemes?
I guess the question does not apply just to CS as I'm trying to understand how it applies to RAIDs, but I guess it's maybe the most suitable place to ask anyway.
There's a lot of info that RS codes ...
- 155
0
votes
1
answer
30
views
Consider a ternary channel with the following channel matrix:
\begin{bmatrix}
1-\alpha & 3\alpha/4 & \alpha/4\\
\alpha/4 & 1-\alpha & 3\alpha/4\\
3\alpha/4 & \alpha/4 & 1-\alpha\\
\end{bmatrix}
I was told that the probability of error of ...
- 5
0
votes
0
answers
11
views
Optimality of coding scheme and entropy reduction
I attempted to draw some connection between coding schemes and how decision tree does splitting. One way that decision tree does splitting is using the split corresponding to maximum information gain ...
- 163
0
votes
0
answers
35
views
Is backslash-escaping a kind of prefix code?
I've been reading about prefix codes and it brought to mind the common practice of backslash-escaping.
In C, C++, and JavaScript, a backlash always starts an escape sequence. For example, ...
- 101
0
votes
0
answers
39
views
Algebra of error models and error correcting codes?
In coding theory we typically consider the situation where we have a
channel that connects a sender and receiver. The messages flowing from
the sender to the receiver are corrupted by an error source ...
- 8,268
0
votes
0
answers
34
views
DJNZ command in Universal Register Machine
How do I represent DJNZ command of counting machine via commands of Universal Register Machine, those commands are CLR JNE INC and TR, via this commands i have to represent DJNZ command, any help ...
- 1
1
vote
0
answers
31
views
matching vector families that form a group
Is there any research/information on matching vector family sets (the U list or the V list or both) that form a group (under addition)?
You can find the definition of MV families here:
https://homes....
- 21
1
vote
1
answer
24
views
Number of binary words that form a group of Hamming weight at most d
Consider binary words in {0,1}^n whose Hamming weight is at most some constant d. We want to select some of these words such that they form a group under addition. How many words can we choose at most?...
- 21
1
vote
4
answers
1k
views
What is the name of the following binary encoding?
S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...]
I want to encode / decode natural numbers with the following scheme:
Encoding N: For ...
- 299
0
votes
1
answer
71
views
How to show that $A(3k, 2k)=4$?
Denote by $A(n,d)$ the maximal size of a binary code of length $n$ with distance $d$.
How to show that $A(3k, 2k)=4$? From Plotkin bound: $$2k > \dfrac{3k}{2} \Rightarrow A(3k, 2k) \leq 4$$ But I ...
- 11
0
votes
1
answer
101
views
Upper bound of sum of codewords lengths
I need to show that for any binary optimal code for $n$-letter source the following inequality
holds:
$$\sum_{i=1}^n l_i \leq 0.5(n + 2)(n −1).$$
By $l_i$ denoted the length of the sequence ...
- 13
0
votes
0
answers
67
views
temporal compression of binary data
I have a sequence of source files that are very similar (akin to frames in a video), and each file can be compressed by a codec independently, but there is no temporal compression.
I want to further ...
- 101
-1
votes
1
answer
273
views
What does zsh: suspended ./a.out mean? [closed]
I was writing a program to count lines from an input text stream.
This is the program. It compiles perfectly but when I execute ./a.out to get the output my ...
1
vote
0
answers
66
views
How to decode shortened Reed-Solomon code?
I am working with a shortened version of $[n,k,d]$ Reed-Solomon code. I am encoding a message of size $k−l$ which gives a shortened code of size $n−l$ (this is equivalent to encoding the same message ...
- 11
2
votes
1
answer
22
views
Number of signatures of each type in a fixed column set of the Hadamard matrix
Consider a $2^n \times 2^n$ Walsh-Hadamard matrix (via Sylvester's construction). Fix a set $S \subset [2^n]$ of $k\leq 2^{n-1}$ columns.
Consider the rows in the $2^n \times k$ submatrix $H'$ that's ...
- 981
3
votes
0
answers
44
views
Bound on the number of signed sums of a non-zero vector that can all equal zero
Let $u$ be a real vector of $m$ entries, and $A$ be a $\pm 1$ matrix of dimension $N\times m$, and real rank $\operatorname{rank}(A) = r$.
What are some conditions on $A$ (e.g. in terms of its rank $r$...
- 981
1
vote
2
answers
283
views
Huffman Coding as optimal
In our lecture, the Huffman coding was described as optimal. Optimal with regard to the minimum information content. When asked, the professor explained to me that the length of a fixed code word ...
- 115
2
votes
0
answers
23
views
Information theory - Expurgation step to go from average error to worst case error in the large error regime
Consider a discrete memoryless channel $N$. We use a code to send messages over this channel.
Shannon showed that if we have a code $C$ with a finite number of codewords $|C|$ such that the average ...
- 262
0
votes
1
answer
110
views
2
votes
0
answers
22
views
Asymptotically Optimal Universal Code In Other Bases
Universal codes are fairly well studied, and many asymptotically optimal universal codes exist for binary data (see https://en.wikipedia.org/wiki/Universal_code_(data_compression) especially https://...
- 163
0
votes
1
answer
33
views
Example on Referential transparency (wikipedia)
I have a rather foolish question on an example
explaining the idea behind Referential transparency
Here is given an example i not understand:
Consider a function that returns the input from some ...
- 213
0
votes
1
answer
72
views
Maximal prefix codes and maximal length
Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true ...
- 115
1
vote
2
answers
33
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 ...
- 155
2
votes
1
answer
48
views
On the definition of Error-Correcting Codes
Let us start with the following well-known definition:
Definition 1. Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer. We say that the code $C$ is
$\boldsymbol t$...
- 123
2
votes
1
answer
55
views
Unique decipherability of infinite regular language
Can we design an algorithm to test if a infinite regular language is a code?
We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular ...
- 23
0
votes
0
answers
104
views
Epsilon balanced Code
A linear code is termed as an $\epsilon -$balanced code if all the codewords are having fractional hamming weight $\in (1/2-\epsilon,1/2+\epsilon)$. I want to show that for every $\epsilon\in (0,1/2)$,...
- 248
0
votes
1
answer
244
views
How to build 4 codewords with a code distance of 5?
I wonder how can I construct 4 (distinct) codewords given the fact that code distance is 5. As far as I know that the code distance is the number of distinct bits between any 2 codewords. How to ...
1
vote
1
answer
41
views
Converse proof for random coding capacity of AVC
I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof ...
- 199
2
votes
1
answer
94
views
Error correction code without error detection
Error detection and correction codes require many bits of redundancy for correcting even a modest number of erroneous bits. However, we often have out-of-band methods to determine when and where the ...
- 732
2
votes
1
answer
50
views
Intuitive explanation on why stochastic encoding performs better in channel coding
I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can ...
- 199
1
vote
1
answer
55
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 ...
- 438
1
vote
0
answers
49
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 ...
- 141
2
votes
0
answers
21
views
Does RLNC (Random Linear Network Coding) still need interaction from the other side to overcome packet loss reliably?
I'm looking into implementing RLNC as a project, and while I understand the concept of encoding the original data with random linear coefficients, resulting in a number of packets, sending those ...
- 21
1
vote
0
answers
37
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 ...
- 21
1
vote
1
answer
163
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:
...
- 111
2
votes
1
answer
74
views
Why is channel capacity of AWGN infinite?
My professor taught us that channel capacity of AWGN channel is infinite without any input power constraints. The noise is $Z \sim \mathcal{N}(0,\sigma^2) $. There is no constraint on input signal. I ...
- 199
0
votes
0
answers
105
views
Total weight of Huffman Code
We are given the following letters with the respective frequencies:
\begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{...
- 421
1
vote
0
answers
224
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} ...
- 51
2
votes
1
answer
39
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 ...
- 213
0
votes
0
answers
25
views
Typical sets size
I am currently studying Shannon's entropy and I have just come across an exercise related to typical sets. More specifically, given a certain type $t$ for the set, the exercise asks to demonstrate ...
2
votes
1
answer
30
views
Bob has to find Alices hidden gold by questioning yes/no questions
Suppose that Alice has $n$ places to hide the gold $v_1, ..., v_n$ and that
Bob knows the probability of each place.
Bob has to ask Alice a series of yes/no questions to find the gold.
I have done ...
- 51
0
votes
1
answer
83
views
Coding Theory Optimal Code with given max length
Why do we need at least 2 Code Words of the max length in optimal Codes?
Any why do they just differ in their Prefix?
Could someone give me more insight into this?
Have to proof that for a given ...
- 51
1
vote
1
answer
43
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 ...
- 11
1
vote
0
answers
27
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,071
3
votes
1
answer
125
views
Smallest set of balls under hamming distance that covers all $n$-bit strings
Suppose we defined a set $S = \{x\mid0 \leq x \leq 2^n-1\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S_i$ such that,
$$S_{y_i} = \{y \in S\...
- 141
2
votes
3
answers
253
views
Name of binary encoding scheme for integer numbers
I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log_2n$ average bits/symbol, thanks to a simple to compute ...
- 150
1
vote
2
answers
180
views
Data Compression :Compress a Compressed File
Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D ...
- 291
1
vote
0
answers
32
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 ...
- 11
1
vote
1
answer
49
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 ...
- 291