Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [coding-theory]

Use this tag for questions about source-coding and channel-coding in information theory, error-correcting codes, error-detecting codes, and related algebraic and/or combinatoric constructions. This tag should not be used for questions about programming.

Coding theory is the study of the properties of codes and their fitness for specific applications.

In Information theory, developed by Claude Shannon, coding theory is traditionally split into Source coding and Channel coding. The former studies for example methods for presenting data from a continuous source using a discrete alphabet of symbols (e.g. binary). Data compression is also a part of source coding. For its part, channel coding studies methods for adding redundancy to a message, aiming to protect it from errors caused by a communication channel.

Many authors also use terms including the word coding to describe problems related to the design of signal constellations = finite sets of signals (with form depending on the characteristics of a given channel) the choice of which then conveys the piece of information to be transmitted. For example the medium of data storage places constraints on the set of signals to be used, applications in a radio channel OTOH calls for methods of designing sets of waveforms aiming to combat various sources of errors (thermal noise, signal fading, interference of other users etc) and or adding diversity to the signal.

A somewhat related area of study is cryptography.

1802 questions
10
votes
2 answers

Generating a binary code with maximized Hamming distance

I have a (seemingly) simple question about coding theory. I feel like the answer to this should be very obvious, but I'm having some troubles with it. I'm trying to create binary code which is $N$ bits in length and consists of $M < 2^N$ codewords,…
Matt K
  • 201
9
votes
5 answers

Help understanding why a block code can correct up to (d-1)/2 errors.

THEOREM: Let d be a block code with odd minimum distance d. Then C can correct up to (d-1)/2 errors. Proof from wikipedia: If no more than (d-1)/2 transmission errors occur, the receiver can uniquely decode the received word to a codeword as…
ryang
  • 38,879
  • 14
  • 81
  • 179
7
votes
3 answers

Why the only binary MDS codes are trivial ones?

Why the only binary MDS codes are trivial ones? I have been thinking how to draw a contradiction by assuming the MDS code is not trivial. Thank you very much!
user200977
  • 71
6
votes
1 answer

A property of the Golay codes

I've been reading about Golay codes, and I found an interested property that I am having trouble showing. The property says: If the $[24, 12, 8]$ binary Golay code $\mathcal{G}$ is punctured in any coordinate and the resulting code is extended in…
josh
  • 4,041
6
votes
1 answer

Gilbert-Varshamov bound

I am looking at the proof of the theorem of the Gilbert-Varshamov bound and I have a question. This is the theorem: The proof is the following: Why is the number of vectors in the linear span of $d-2$ or fewer of $c_1, \dots, c_{j-1}$ given by…
Evinda
  • 1,460
5
votes
1 answer

A question about optimal codes

Recall that a code attaining any bound is called an optimal code. Is the dual code of an optimal code also an optimal code?
taubetasigma
  • 304
5
votes
0 answers

Understanding Reed-Solomon as it applies to Shamir secret sharing

I'm working on trying to understand how to use Reed-Solomon decoding to make Shamir secret sharing robust to cheaters as mentioned here. I'm following the setup shown at the bottom of page 40 in this paper. So, here is my simple example. I'm working…
mikeazo
  • 412
5
votes
2 answers

Constructing the binary Golay code from the extended binary Golay code

I am studying a construction of the binary Golay code using the extended binary Golay code $\mathcal{G}$. It is well known that the extended Golay code is a $[24,2^{12},8]_2$-code and can be constructed from the generating matrix $$ {I} \choose {A}…
Thomas Connor
  • 2,393
5
votes
1 answer

Binary code for expected 1-bit errors

Consider a code $C$ that uniquely maps each k-digit binary number $P=p_1 p_2 \cdots p_k$ to some k-digit binary number $Q=q_1 q_2 \cdots q_k$. I.e., the code is $C(P) = Q$ and $C^{-1}(Q) = P$. There are $2^k!$ such codes. Now consider that code…
rodion
  • 151
  • 2
5
votes
1 answer

Behaviour of an extended binary Hamming code when 3 errors have occurred

Take the [8,4] extended code for example. Note that extended binary Hamming codes are 3-error-detecting. All single-bit errors are correctly decoded, while double-bit errors are detected but not correctable. But how exactly does the code behave when…
ryang
  • 38,879
  • 14
  • 81
  • 179
5
votes
4 answers

Huffman optimal code

I can solve similar problem with 4 symbols. But I cannot solve it when the number of symbols is more than 4. However, here is the probability of the symbols: I need to develop optimal code with the Huffman method. The tree which I got looks like…
user61810
  • 135
5
votes
1 answer

Spherical codes and their applications

I am in the middle of preparing a seminar lecture about spherical codes and as the source literature, I started reading “Codes on Euclidean Spheres” by Thomas Ericson and Victor Zinoviev. I really like the subject which leads to this question: I…
user239922
5
votes
1 answer

Uniquely Decodable Code

Given a code $c:S\rightarrow T^*$ let $n_i$ denote the number of symbols in S that are encoded by strings of length $i$ in $T^*$ If we want to construct a uniquely decodable code for 12 symbols using binary words of length less than or equal to 4.…
hmmmm
  • 5,616
5
votes
1 answer

Distance of bch code

I want to show that a binary , narrow-sense BCH code of length $n=2^m-1 $ and designed distance $ \delta=2t+1 $ has minimum distance $ \delta$ , given that $ \sum_{i=0}^{t+1} \binom{2^m-1}{i}> 2^{mt} $. We know that: A BCH code with designed…
Evinda
  • 1,460
4
votes
3 answers

Find the neighbors in Gray Code sequence

I want to find a way to figure out what are the most closest neighbors in a Gray Code sequence. For example I have 010110, and I need to figure out which are its neighbors. I can apply the binary reflection algorithm from Wikipedia, I know. I did it…
ADDA
  • 43
  • 1
  • 3
1
2 3
…
32 33