Questions tagged [coding-theory]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
38 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 ...
JoJo P's user avatar
  • 101
0 votes
0 answers
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 ...
user167441's user avatar
1 vote
1 answer
22 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, ...
user1936752's user avatar
1 vote
1 answer
40 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 ...
mutantacule's user avatar
0 votes
1 answer
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 ...
user402525's user avatar
2 votes
0 answers
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 ...
ocksumoron's user avatar
0 votes
0 answers
36 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 ...
StuKers's user avatar
0 votes
0 answers
66 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 ...
Sahil Sharma's user avatar
1 vote
2 answers
188 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 ...
Ally Zane's user avatar
1 vote
2 answers
54 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 ...
ledonter's user avatar
  • 145
0 votes
1 answer
70 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 ...
PTSONIC's user avatar
0 votes
0 answers
42 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 ...
Martin Berger's user avatar
0 votes
0 answers
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 ...
Tarik 's user avatar
1 vote
0 answers
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....
Ali Gholami's user avatar
1 vote
1 answer
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?...
Ali Gholami's user avatar
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 ...
Oleg Dats's user avatar
  • 299
0 votes
1 answer
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 ...
SWarn's user avatar
  • 11
0 votes
1 answer
159 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 ...
Water Lily's user avatar
0 votes
0 answers
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 ...
chaohuang's user avatar
  • 101
-1 votes
1 answer
369 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 ...
kraanasgard's user avatar
1 vote
0 answers
151 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 ...
sayanc2011's user avatar
2 votes
1 answer
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 ...
gen's user avatar
  • 991
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$...
gen's user avatar
  • 991
2 votes
2 answers
626 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 ...
Rico1990's user avatar
  • 125
2 votes
0 answers
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 ...
user1936752's user avatar
0 votes
1 answer
164 views

I'm studying a trie tree, where I want to delete a word, Please make me understand the algorithm

...
Adil Nehal's user avatar
2 votes
0 answers
27 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://...
LambdaBeta's user avatar
0 votes
1 answer
35 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 ...
user267839's user avatar
0 votes
1 answer
123 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 ...
Cat's user avatar
  • 115
1 vote
2 answers
34 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 ...
Moonwalker's user avatar
2 votes
1 answer
55 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$...
Chris's user avatar
  • 123
2 votes
1 answer
57 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 ...
VereX's user avatar
  • 23
0 votes
0 answers
156 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)$,...
roydiptajit's user avatar
1 vote
1 answer
432 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 ...
Powerful blaster's user avatar
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 ...
Black Jack 21's user avatar
2 votes
1 answer
152 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 ...
Rainer P.'s user avatar
  • 842
2 votes
1 answer
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 ...
Black Jack 21's user avatar
1 vote
1 answer
76 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 ...
acupoftea's user avatar
  • 458
1 vote
0 answers
51 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 ...
user3862410's user avatar
2 votes
0 answers
23 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 ...
nyenyu's user avatar
  • 21
1 vote
0 answers
45 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 ...
Rapiz's user avatar
  • 21
1 vote
1 answer
315 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: ...
Paul's user avatar
  • 111
2 votes
1 answer
109 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 ...
Black Jack 21's user avatar
0 votes
1 answer
203 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{...
Mary Star's user avatar
  • 431
1 vote
0 answers
230 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} ...
Rapiz's user avatar
  • 51
2 votes
1 answer
54 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 ...
Mahathi Vempati's user avatar
0 votes
0 answers
27 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 ...
Francesco Lucarelli's user avatar
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 ...
Rapiz's user avatar
  • 51
0 votes
1 answer
148 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 ...
Rapiz's user avatar
  • 51
1 vote
1 answer
48 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 ...
Rohan Joshi's user avatar

1
2 3 4 5