# Questions tagged [coding-theory]

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

207 questions
Filter by
Sorted by
Tagged with
214 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{...
1 vote
42 views

### Why is the block size chosen to be q-1 for Reed-Solomon codes?

Consider a Reed-Solomon code over a finite field of $\mathbb{F}_q$. Why is the typical block size chosen to be $q-1$ [1][2][3]? The reasoning I saw around this is ...
47 views

### Implementing algorithms from online courses in code to solidify understanding

I came across the online course Design And Analysis Of Algorithms and the assignments have several questions that ask you to design algorithms, but you are not asked to implement them in code. I think ...
1 vote
203 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) $\{x_1\dots x_n\}$ $\{y_1\dots y_n\}$ I want to pair them up optimally, one from each array, so that the pairs come ...
39 views

### How are non-binary codes implemented in practice, i.e. codes over $\mathbb{F}_q^n$ for $q\neq 2$?

I am only familiar with binary implementations of information, though I am aware other implementations (ternary etc.) exist. I was wondering, if a code over $\mathbb{F}_q^n$ is used in practice, where ...
1 vote
312 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 ...
12 views

### LT Codes encoding with replacement

I have read a Luby’s paper and understand basic idea of the LT codes, but I want to figure out the analysis when encoding symbols can choose their neighbors with replacement during the encoding ...
69 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 ...
1 vote
23 views

### Why, for Reed-Solomon codes, does the alphabet size depend on block length?

I'm learning about Reed-Solomon codes so apologies if this is a basic question. The alphabet size $q$ in RS codes grows with the block length $n$ - in particular, we have $q \geq n$. But intuitively, ...
155 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 ...
87 views

### Data structure for prefix covering

I have a list $[1, 2, \ldots, T]$. I want to create a collection of subsets, such that: each element belongs to a small number of subsets each prefix is a union of small number of subsets (these ...
6k 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?
37 views

### Multi Edge Type LDPC codes - How to construct H?

I need to create a parity-check matrix, H, for a MET-LDPC code. I know that H will still be two-dimensional and have only 0s and 1's, just like "normal" LDPC codes. I am aware of the ...
1 vote
297 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. ...
71 views

### Calculation of compression ratio using arithmetic encoding?

Arithmetic encoding is one of the most famous entropy encoding techniques, and I am using it to encode an image. For this, I am using the built-in function of Matlab that also gives other values such ...
1 vote
57 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 ...
72 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 ...
774 views

### Using Data Compression on the output of Data Compression

Context: Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy) Questions Is there a data compression method/algorithm that uses another data ...
43 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 ...
49 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 vote
323 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
33 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....
1 vote
28 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?...
1 vote
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 ...
98 views

### Complexity of nearest codeword in cyclic codes

Is it $NP$-complete given $c(x),g(x)\in\mathbb{F}_2[x]$ where $g$ generates a cyclic code of length $n$ (so $g\mid x^n-1$), and $\deg c<n$ to find the nearest codeword to $c$? This is related to ...
72 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 ...
160 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 ...
92 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 ...
371 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
438 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 ...
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$...
1 vote
156 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 ...
23 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 ...
646 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 ...
30 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 ...
1 vote
135 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 ...
31k 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 ...
756 views

### How can I estimate Bhattacharyya parameter for BSC channel, used for Polar codes

In polar codes, the frozen bits in each message are determined through the worst channel, where the relevant parameter is the Bhattacharyya . How can I estimate Bhattacharyya parameter for BSC ...