Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [coding-theory]

Use this tag for questions about source coding, error-correcting codes, error-detecting codes, and related algebraic and/or combinatoric constructions.

-1
votes
0answers
13 views

Difference Entropy Output and Input [on hold]

In a ternary channel with same probabilities for all inputs. I have H(X) entrance entropy and H(Y) output entropy. What does the difference of these 2 Entropy tell me?
-2
votes
0answers
19 views

Majority voting 9 Bits Error probability

i have 1 Bit that will send 9 times. Each bit has an error probabiltiy of 1/3. The received Bits will be interpreted with a majority voting. Do anyone have an idea how i do check the probability ...
0
votes
1answer
21 views

Parity check matrix H given; justify that C can correct one error, does a word belong to C and correct an error. [on hold]

I'm trying to learn about error correcting codes, and I have this question from a previous exam. Now I'm a little bit confused because I can't seem to wrap my head around this one, could I please get ...
-3
votes
0answers
15 views

VBA Macro and ActiveX Button Consolidation [on hold]

I have two Active X buttons that work and am trying to make one button that does both actions simulataneously. The first ActiveX button sorts through a data array and hides any rows that do not have ...
4
votes
2answers
44 views

Finding short vectors in $\mbox{GF}(2)$

Suppose we have a system of $n$ linear equations in $m$ unknowns over $\mbox{GF}(2)$ (binary field) $$Av=b$$ Let $V = \mbox{GF}(2)^m$ be the vector space of possible assignments of the variables. For $...
3
votes
2answers
37 views

How many generator matrices does an [n, k]q - linear code have?

So far, I have realised that there exists a unique generator matrix for a $[n,k]_q$-linear code if and only if $n=k=1$ and $q=2$. I also believe that the number of generator matrices is given by the ...
0
votes
1answer
32 views

Catastrophic generator matrix

Given the generator matrix $$G(z) = [z^3+1 \ \ \ \ \ \ \ z^3+z^2+z+1]$$ Why is G(z) catastrophic? I know that a generator matrix for a rate k/n convolutional code is called catastrophic, if there ...
-1
votes
0answers
36 views

Existance of linear code if $q^k\cdot V_q(n, d-2) \le q^n$

Prove that there exist linear code $\sum^k\rightarrow\sum^n$ with distance $d$ if $q^k\cdot V_q(n, d-2) \le q^n$, where $q = |\sum|$. In a book there is such hint: Use the fact that distance of code ...
0
votes
0answers
16 views

Existance of linear code if $q^k\cdot V_q(n, d-2) \le q^n$ [duplicate]

Prove that there exist linear code $\sum^k\rightarrow\sum^n$ with distance $d$ if $q^k\cdot V_q(n, d-2) \le q^n$, where $q = |\sum|$. In a book there is such hint: Use the fact that distance of code ...
0
votes
0answers
24 views

Counting the numbers of codewords of a given weight distribution

I would like to find a closed form for the number of codewords of a given weight distribution, and with 'r' coordinate positions fixed to a specific letter in the alphabet (not zero). If I didn't add ...
0
votes
0answers
24 views

Free distance of given generator matrix

Given the generator matrix $$ G(z) = \begin{bmatrix} 1 & 1 & 1 \\ z-1 & z-2 & 2z-3 \end{bmatrix}$$ I know the rate is 2/3 and that the convolutional code is of degree 1 over $F_5$. ...
-1
votes
1answer
16 views

generator matrix from code words

{0010111, 1110010, 1100101, 1010001, 0100011, 0101110, 0001101, 1111111, 1011100, 1101000, 0111001, 0000000, 1000110, 1001011, 0110100, 0011010} i was given 16 codewords and need to find generator ...
4
votes
1answer
77 views

In Huffman coding, how do I choose the frequency to get the maximum average bit length?

First I want to give you a little summary about the Huffmann code to avoid misunderstandings. Summary begins So we have an alphabet $A$ with $|A| > 1 $. For example $A$= {$a,b,c,d,e$}. Now we ...
0
votes
1answer
58 views

Basic coding theory concepts

I've been working my way through this book on Abstract Algebra, http://abstract.ups.edu/download/aata-20180801.pdf and in particular am getting confused within the section on Algebraic Coding Theory. ...
0
votes
0answers
19 views

How to construct cyclic and self dual code (12,4)

Question is: Construct cyclic and self dual code (12,4). Both codes has 4 bits for data and 12 bits for codeword. Construct generation matrix for both codes. Prove that both codes are equal. I am ...
0
votes
0answers
30 views

Extended Euclidean Algorithm involving a table

Issue in regards to solving the Extended Euclidean Algorithm involving the two numbers 3480 and 1967. Issue only concerns that when the extended euclidean algorithm is needed. To provide context a ...
3
votes
1answer
44 views

Hadamard block design row intersection

If I have a Hadamard design $(4t-1, 2t-1, t-1)$ is it possible that 2 subsets share $t$ or more elements? The text I am working through seems to imply it is obvious that this isnt possible but I seem ...
0
votes
2answers
42 views

Does there exist a binary (10,19,3) code?

The parameters (10,19,3) satisfy the singleton bound because $19 \leq 2^{10-3-1}$, the Gilbert-Varshamov Bound because $19 \geq \frac{2^{10}}{B_2(c)},$ ($B_2(c) = 56$) and the Hamming bound because $...
0
votes
1answer
47 views

Product of generalised Reed-Solomon Codes

I know the definition of a generalised Reed-Solomon Code: $$ GRS_{n,k} (\alpha, v) = \{(v_0 f(\alpha_0), ..., v_{n-1}f(\alpha_{n-1}) ): deg f < k \}.$$ I know also that the product of two GRS ...
1
vote
0answers
27 views

Is there any name of matrix that sub matrix is circulant matrix?

I have studied low-density parity-check (LDPC) codes, which use quasi-cyclic codes whose submatrices are cyclic shifts of the identity matrix or of the zero matrix. For example, Each number means: $-...
0
votes
0answers
37 views

Codes over rings

A linear code of length $n$ on a ring $R$ is an $R$-submodule of the free $R$-module $R^n$. These are of interest in applied mathematics to ensure successful transmission of a message despite ...
2
votes
1answer
43 views

Dimension and cardinality of vector spaces in Coding Theory

Let $V$ be a vector space over $F$, where $\dim(V) = n$. Then $|V| = |F|^{n}$. This is intuitive for me in abstract settings. Consider the standard basis for $V$, $\{e_1,e_2,...,e_n\}$. There are $n$ ...
0
votes
1answer
14 views

How to write the parity-check matrix of Hamming code?

I have read some questions about this topic, but I am still not clear about some concepts about Hamming code. If we want to write a parity-check matrix for $n$ information positions(with single error-...
0
votes
0answers
15 views

Uniquely decodable code and Markov theorem.

There is a code from 20 binary words of length $\le 10$. It's also known that every word with $\le 2013$ symbols is uniquely decodable. Is it true that these code is uniquely decodable code? Is it ...
0
votes
0answers
23 views

Problems on combination of binary sequences

Show that we cannot find 171 binary sequences (sequences of 0’s and 1’s), each of length 12 such that any two of them differ in at least four positions. I assume $S$ to be any set of binary sequences ...
0
votes
0answers
19 views

Construct parity check matrix of binary Goppa Code

I am working out on a problem given in the book Theory of Error-correcting codes by MacWilliams and Sloane. The problem is to construct a parity check matrix for a classical binary $[8,2,5]$ Goppa ...
0
votes
1answer
48 views

Proof of Gray code

Prove that for every $n \in \mathbb N$ with $n \geq 1$ a $1$-step binary code $C_n$ for the inteval $[0, 2^n −1]$ with code words of length $n$ exists. I have to prove it using induction.
0
votes
1answer
19 views

Notation for this quaternary linear code

I've been reading about self dual codes, and the literature says that there is a quaternary self dual code $$i_2 \otimes \mathbb{F}_4$$where $i_2 = {\{00,11}\}$ is a binary self dual code and $\mathbb{...
2
votes
0answers
26 views

Codes that maximize average minimum distance from any tuple?

Inspired by this question. I'd wish to know about binary codes that seek to maximize, not the distance from each codeword to the nearest codeword, but the average distance from any vector ($n-$tuple) ...
0
votes
1answer
21 views

BCH code with received vector

I've got $\alpha$ as a primitive element of $F_{2^4}$ satisfying $\alpha^4 + \alpha + 1 = 0$ and the [15,7,5] binary BCH code given by the generator polynomial $g(x) = x^8 +x^7+x^6+x^4+1 = \prod_{i \...
2
votes
1answer
40 views

$K+2$ events which are $K$-wise mutually independent but never $(K+1)$-wise mutually independent

This question seems so obvious that I wonder if I am just having a brain-melt moment... if so, apologies in advance! :( The difference between pairwise independence and mutual independence is well ...
0
votes
0answers
17 views

Space with hamming distance at least 2. [duplicate]

Let $X=\{0,...,2^n-1\}$. Is there a $Y\subseteq X$ with $|Y|=2^{n-1}$ and such that $d(x,y)\geq 2$ for any $x,y\in Y$, where $d$ is the hamming distance (number of on bits of the xor operation)? I ...
1
vote
1answer
17 views

smallest length code given the generator polynomial

I'm interested in finding, with proof, the smallest length n of a binary linear cyclic code with a generator polynomial of degree 7. I know that since the code is linear and cyclic, the dimension of ...
0
votes
0answers
14 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 ...
7
votes
2answers
116 views

Searching for tagged balls under constraints

(This is a modification of this problem.) You have $k$ white balls and $k$ black balls, and know that exactly one of each color is radioactive. You can place any number of balls of your choosing in ...
0
votes
1answer
33 views

Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)

For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to ...
0
votes
0answers
33 views

Algebra using sage

Can anyone help in writing a code to find the list of idempotent and primitive elements of a group algebra, the examples goes like this. Let $p$ be an odd prime such that $\bar2$ generates $U(\mathbf{...
0
votes
0answers
12 views

BCH code properties

I am a newbie in error correcting codes and interested to understand binary BCH codes. I understand that all the code words are at least in dmin = 2t+1 Hamming distance of each other. But I have the ...
0
votes
1answer
17 views

construct parity check matrix from hamming code (3,4)

So I have this question. let $${F_4} = \{0, 1 , x, x^2 | x^2 = x + 1 \}$$ Use Ham(3,4), with a parity-checkmatrix having columns in lexicographical order, to decode (a) 1111111 1111111 1111111; (...
0
votes
0answers
13 views

Construct parity-check matrix for HAM(3,4)

So I have this question. let $${F_4} = \{0, 1 , x, x^2 | x^2 = x + 1 \}$$ Use Ham(3,4), with a parity-checkmatrix having columns in lexicographical order, to decode (a) 1111111 1111111 1111111; (...
0
votes
1answer
51 views

Parity check matrix for the Hamming code Ham(2,7)

I'm trying to figure out how to construct a parity check matrix for a Ham(2,7) where Ham(2,7) is Ham(r,q). I really don't understand where the columns of matrix come from my Text Book says to list all ...
-1
votes
2answers
43 views

Proving that there doesn't exist a binary code with parameters [6,5,4]

I'm new to code theory and I'm having trouble with proving if a code doesn't exist in general. I found a binary code with the parameters [6,4,4] but I don't really understand why there cant be one ...
1
vote
2answers
35 views

How do I find $\bar{y}$ in this question?

A summary of $20$ observations of $y$ gave the following information $\sum(y-a)=-37$ $\sum(y-a)^2=1529$ Find the mean and standard deviation of $y$. In this question, I was able to ...
0
votes
1answer
25 views

Rate of systematic code that is a combination of two codes over the same information symbols.

Let $I_k$ be the systematic columns and let two codes be defined over the same systematic columns $I_k$ as below. Let $[n_1,k]$ be the first linear systematic code with rate $\frac{k}{n_1} \leq r_1$,...
1
vote
2answers
23 views

Idempotents and cyclic codes

Let $C_1 = \langle e_1(x) \rangle$, $C_2 = \langle e_2(x) \rangle$ cyclic codes, where $e_1(x)$ and $e_2(x)$ are idempotents. I know what cyclic codes and idempotents are, but why can one deduce the ...
0
votes
0answers
18 views

Show that weight of code is equal to the minimal number of rows in the control matrix

Show that weight of code is equal to the minimal number of rows in the control matrix. My solution: Let $a$ is vector, $C^{*}$ is control matrix, $w(a)$ - weight of code. We want to show $a*C^{*} = ...
4
votes
0answers
49 views

Does there always exist a Chebyshev center of three constant weight points in $\mathbb F_2^n$ which is equidistant?

Given three distinct points $x_1,x_2,x_3$ in $\mathbb F_2^n$ (endowed with the Hamming metric $d(\cdot,\cdot)$) with the same (but arbitrary) Hamming weight, the Chebyshev radius of them is defined as ...
2
votes
0answers
21 views

Show that $d=2d_{2}$ if $2d_{2}\le d_{1}$ and $d_{1}\leq d\leq2d_{2}$ if $2d_{2}>d_{1}$.

Assume that $q$ is odd. Let $C_{i}$ be an $\left[n,k_{i},d_{i}\right]-$linear code over $\mathbb{F}_{q}$, for $i=1,2$. Define $$C_{1}\diamondsuit C_{2}=\left\{ \left(c_{1}+c_{2},c_{1}-c_{2}\right):c_{...
1
vote
1answer
102 views

How to create generator matrix from given 8 linear codewords of (7,3).

Four codewords of a linear $(7,3)$ code $C$ are given to me in a question with no other details, which are$$0110101,1001101,1001011,0000000.$$I am asked to write down the missing codewords. I have ...
0
votes
1answer
36 views

Error probability of repetition code

I am very lost. I would like to know how I calculate the probability of finding errors in repetition code. For example say the codewords are 111 or 000 and probability of an error is 0.1. How would I ...