Questions tagged [coding-theory]
The study of data representations that enable error detection, error correction and/or compression.
48
questions with no upvoted or accepted answers
4
votes
0
answers
78
views
Find the actual codeword
Let $ C $ be a reed solomon code with length $6$, dimension $2$ and distance $5$.
Suppose that we are over $\mathbb{F}_7$ and we have the genrator polynomial $g(x)=(x- \alpha)(x- \alpha^2) (x- \alpha^...
- 317
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$...
- 991
3
votes
0
answers
60
views
Separate arithmetic codes closed under addition
For error detection purpose I am looking for separate arithmetic codes which are closed under integer addition.
By separate, I mean the code word $C$ for message $x$ is a tuple $(x,f(x))$ where $f(x)$...
- 31
3
votes
0
answers
61
views
How to apply insights from the theory of codes to alternating codes?
The book Theory of codes by J. Berstel and D. Perrin from 1985 studies variable-length codes. The focus is less on error-correction and compression, but more on algebraic properties, synchronization ...
- 5,390
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 ...
- 21
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 ...
- 274
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://...
- 163
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 ...
- 199
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 ...
- 21
2
votes
0
answers
28
views
Media Codec Error Resilience
I'm an entire outsider to computer science eventhough I've been programming for so many years.
As we know, modern audio-visual media codecs are essentially entropy codings of subjective preceptual ...
- 352
2
votes
0
answers
38
views
Are there codes that detect the position of an error?
I am looking for code that detect an error and it's position (or an aproximation of it), this is more than an error detector code but a little less than a correcting code.
Do you know something like ...
- 133
2
votes
0
answers
110
views
Vandermonde matrix and its binary representation
Say one is given a Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) of dimension $2^q \times k$ such that the elements of the first column of it are $\{0,1,2,..,-1+2^q\}$. (This ...
- 493
2
votes
0
answers
66
views
Error detection code supporting arithmetic
I am looking for error detection codes, which support addition in the encoded domain and are separate (a tuple of ($N$, $R(N)$), where $N$ denotes the functional value and $R(N)$ its redundancy).
So ...
- 21
2
votes
0
answers
106
views
Code families with efficient decoding algorithms
Which families of the error correcting codes have an efficient decoding algorithm? I know that decoding a general linear code is NP hard (the general decoding problem). I also know that Goppa codes ...
- 313
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 ...
- 111
1
vote
2
answers
187
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 ...
- 11
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....
- 21
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 ...
- 11
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 ...
- 141
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 ...
- 21
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} ...
- 51
1
vote
0
answers
35
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,101
1
vote
0
answers
40
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
3
answers
307
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 ...
- 11
1
vote
0
answers
22
views
Showing that a source is not Markov
If I have some source sending codewords and I take a large sample of codewords in order to construct an empirical distribution of the codewords sent. Using this empirical distribution, what methods ...
- 121
1
vote
0
answers
92
views
Difference between a regular and a stationary source?
As far as I understand a stationary source is a regular source but it's not necessarily true the other way around.
And a stationary source is a source for which its distribution is unaffected by a "...
- 333
1
vote
0
answers
16
views
LT codes with constant degree on information symbols
I have just read a Luby’s paper on the very basic idea of the LT codes, which may be of interest for me.
For my application, encoding k information symbols is done in a process that generates a big ...
- 111
1
vote
0
answers
60
views
Is there a database of linear codes with "small" covering radius
Does anyone keep a database of (or including) linear codes with small covering radius? I'm specifically interested in the smallest-dimension codes known of covering radius R ($2\le R \le 4$ say) for ...
- 201
1
vote
0
answers
194
views
Hamming code extension with additional parity bit
Let $Ham$ be the $[7,4,3]_2$ Hamming code.
It is known that $\{w(c):c\in Ham\}\subseteq\{0,3,4,7\}$, where $w(c)$ is the Hamming weight of the word $c$.
A code $C$ of length $n$ is called cyclic if ...
- 742
1
vote
0
answers
49
views
Soft binary ECC? How to maximize the minimum distance over a channel?
Given that
The channel is tiny, it has message size of 72 bits
Each bit is probabilistic, meaning that I have a value between 0 and 100 of how likely that bit is on/off1
Only 24 bits of acutal data ...
- 111
1
vote
0
answers
45
views
Decode Reed Muller codes efficiently given only a syndrome
So given some erroneous Reed Muller code-word's syndrome as well as the Parity-Check/Generator Matrix how would one find the error vector?
The approach I took naively was to build the syndrome table, ...
- 111
1
vote
0
answers
975
views
Efficiency of arithmetic coding
I think I know how the arithmetic coding works but what I don't understand is the reasoning about efficiency.
I have read in this pdf that the number of bits required to specify a range is greater ...
- 267
1
vote
0
answers
79
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 ...
- 111
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 ...
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 ...
- 101
0
votes
0
answers
35
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
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 ...
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 ...
- 8,308
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 ...
- 1
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 ...
- 101
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)$,...
- 246
0
votes
1
answer
202
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{...
- 431
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 ...
0
votes
0
answers
58
views
finding the overhead and distance of an unknown code based on message making algorithm
for an information word M with m bits that is coded as following:
M is coded into a word A using an unknown code that allows detection of not more than one error.
the code word is the word obtained ...
- 101
0
votes
0
answers
85
views
arithmetic coding for generating random number with desired distribution
Hi i want to convert random number with uniform distribution to desired distribution using arithmetic coding. It has been done in the following research paper called arithmetic distribution coding ...
0
votes
0
answers
93
views
Simplification of Sum of Hamming Weight Sets
Let $k,n,K,m \in \mathbb{N}$ such that $k<n$. Let $l\in \mathbb{R}$, such that $0 \leq l \leq 1$. I am analyzing an algorithm and I need $O(N)$. Could you help me with the reduction of the ...
- 503
0
votes
0
answers
36
views
Error Detection Distance of Residue Codes
Given a residue code representing a number N with the tuple (N, R(N))where R(N) equals ...
- 13
0
votes
0
answers
63
views
Efficient algorithm to expand $(x+a)^n$
im looking for efficient algorithm to expand $(x+a)^n$ without using binomial theorem
is the repeating square method efficient for that problem with the help of binary representation of n ?
- 247