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.

2
votes
0answers
27 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 ...
1
vote
0answers
18 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
51 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
29 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 ...
4
votes
4answers
34 views

Linear codes over rings

I've researched linear codes over finite fields, so, the next step would be to look in to linear codes over rings. I can't find many good sources on this topic? I know that it's fairly new ...
0
votes
3answers
37 views

Show that the distance between vectors is even

Consider two vectors $(a_1, \dots, a_n), (b_1, \dots, b_n) \in \{0,1\}^n$ such that they both contain an even amount of ones. Is there an easy way to see that the set $\{i: a_i \neq b_i\}$ has even ...
2
votes
1answer
18 views

Equivalence of codes defines a symmetric relation

Two codes $C_1, C_2 \subseteq A^n$ are called equivalent (notation: $\sim$) if there are permutations $\pi \in Sym(A)$ and $\sigma_1, \dots, \sigma_n \in S_n$ such that $$C_2 = \{(\sigma_1(a_{\pi(1)}...
1
vote
1answer
21 views

Distance of two concatenated linear codes

Let $A_1$, $A_2$ be two linear codes over $F_q$ with parameters $[n_1, k_1, d_1]$ and $[n_2, k_2, d_2]$. Let $A:= \{ (a_1 || a_2) | a_1 \in A_1, a_2 \in A_2\}$, where || is the sign for ...
-2
votes
1answer
28 views

Number of binary linear codes [closed]

How many binary linear codes with parameters $[n, n-1, 2]$ are there, where $n \geq 2$ ?
-1
votes
1answer
21 views

Is the dimension of a binary linear code the number of codewords it contains? [closed]

For example, would the dimension of the binary linear code $\{0000,1111\}$ be $2$?
0
votes
1answer
29 views

Syndrome decoding

I have a conceptional question to the concept of "syndrome decoding" (i.e. the procedure to decode a received vector). Let's say I'm given a generator matrix G and a received vector v = (1, 1, 1, 0, ...
0
votes
1answer
19 views

Parity check matrix for binary linear code

Let $G = \left( \matrix{ 1 \ 0 \ 1 \ 0 \ 1 \ 1 \\ 0 \ 1 \ 1 \ 1 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1 \ 1 \ 1 } \right)$ be a generator matrix for a $[6,3]$ binary linear code, C. How can I find a parity check ...
0
votes
2answers
24 views

Linear code over $F_q$ exists always

Why is there always an $[n, n-1, 2]$ linear code over $F_q$ for any $n \geq 2$?
1
vote
1answer
31 views

Hypercube Graph Star Coverings

What is the minimum number of star graphs $S_4$ required to fully cover a 4-dimensional hypercube graph $Q_4$? How about the number of $S_5$ star graphs necessary to cover the 5-dimensional hypercube ...
0
votes
1answer
22 views

Non-cyclic Codes

We are now studying all about cyclic codes. We determine when does a code C cyclic. My teacher give an easy example which is the Hamming Code. Then, he gave this question if there a non-cyclic hamming ...
0
votes
1answer
56 views

Guess ball colors

7 people receive either a black or a white ball. They can only see the color of the others balls, but not their own. Both of the colors are equally likely. They play as a team a game of guessing their ...
2
votes
1answer
39 views

Guess the color of the cap - extended

I had here (Guess the color of the cap) the following problem: I have 3 persons which either wear a white or a black cap. They can only see the color of the other caps, but not their own. White and ...
0
votes
0answers
9 views

dual of a Generalized Reed Solomon Code is also a Generalized Reed Solomon Code and usefulness of the property

I have just started learning coding theory and my TA is pretty useless. I am going through Generalised Reed Solomon code from Fundamentals of Error-Correcting Codes By W. Cary Huffman, Vera Pless. ...
3
votes
0answers
74 views

A coding theory/probability puzzle

I thought of the following problem and I am stuck in solving it. Suppose there is a deck of 4 cards with 2 red and 2 blue. I pick 2 cards at random and choose 1 and show the other to my friend. With ...
-2
votes
1answer
32 views

Length of linear code [closed]

Let C be a linear code $\subset F_3^6$ generated by the matrix $$ G = \left[\matrix{0 \ 0 \ 0 \ 1 \ 1 \ 1 \\ 1 \ 1 \ 1 \ 0 \ 1 \ 2} \right]$$ How can I calculate the distance of C, the dimension and ...
1
vote
1answer
66 views

BCH decoding example

Let $\alpha $ be a root of $X^4 + X + 1$, and let C be the BCH code of length 15 with defining set the first four powers of $\alpha $. Determine the error position of the following received word: $1+X^...
0
votes
1answer
11 views

What does it mean to determine the savings over the most efficient fixed length code?

I have some information coding theory questions but I'm asked to determine the savings over the most efficient fixed length code, and I don't know what this means. What is the "savings?" that the ...
1
vote
0answers
19 views

Defining cyclic codes

Let C be the cyclic code defined by a primitive nth root of unity. This is the start of a question I have been given, but I don't understand how this is a valid way to define a cyclic code. The way I ...
1
vote
1answer
86 views

Relation between degree and Hamming distance

Let $\mathbb{F}$ be a finite field. Let $S \subset \mathbb{F}$ be some non-empty set. Define the relative Hamming distance between two function $f,g: S \to \mathbb{F}$ by $$ \Delta_S (f, g) := \frac{...
0
votes
1answer
28 views

A linear code must be able to send $256$ different messages s.t. it corrects one error. What is the least possible length of such a code?

I'm studying for exam that is coming up and I'm reading about correcting errors in linear code and I'm struggling with this problem. Any solutions? Thanks! Suppose we wish to be able to send $256$ ...
0
votes
0answers
22 views

Coding Theory (coset leader)

If $C$ is a $[n,k,d]-$ code and $u\in\mathbb B^n$. Show that $\omega(u)\le\lfloor \frac{d-1}{2}\rfloor$ then $u$ is a unique coset leader in $u+C$. I have to prove this statement, but how to show ...
0
votes
0answers
46 views

Extended Hamming code to cyclic code

Is there any way to present [8, 4] extended Hamming code as a cyclic code? Empirically, it seems not possible; however, I cannot prove or disprove it.
0
votes
0answers
33 views

Hamming code of length $15$. How many code words are there? Which of the following are code words?

Hi I'm trying to solve this problem but have some difficulty. Write down a check matrix for the Hamming code of length $15$. How many code words are there? Assuming that the columns of your matrix ...
0
votes
1answer
40 views

Discrete memoryless channel with 2 linearly dependent columns

Suppose we have a random variable $X$ taking in values in $\{ x_1, .., x_a \}$, and a discrete memoryless channel (DMC), $M$, represented as a matrix, with output alphabet $\{ y_1, .., y_b\}$where its ...
1
vote
0answers
49 views

Distinguishing two channels with known probability distributions

Let $p(\cdot | \cdot)$ and $q(\cdot | \cdot)$ be two known channels from alphabet $X$ to $Y$. What is the optimal strategy to distinguish between them if you are allowed to use the channel only once, ...
0
votes
0answers
13 views

What are dual codes and the codewords denoted by these dual codes in terms of trace?

I am currently reading a research paper (linked below) that mentions "Consider only maps that vanish at 0, their short codes $C_f$ and their duals $C_f^\perp$. The duals can be written as $C_f^\perp = ...
-3
votes
1answer
31 views

Rank of a matrix constructed using the codewords of a linear block code.

Suppose that $[n, k,d]_2$ represents a linear block code. Then we have $2^k$ different codewords. Suppose that $c_1, c_2,....,c_{2^k}$ represents different code vectors. Define a matrix $A$ as, $$A=[...
1
vote
0answers
23 views

Reversible analog coding of strings (mathematical expressions)

Neural coding converts single word or single sentence of words into the vector of real numbers. This coding, while sometimes useful, is not revertible. Are there methods (or at least research effort ...
-2
votes
1answer
168 views

Optimization problem for routes

Let a group of farms each have a p-letter name. No two farms have the same name, however, and they all only consist of x's and z's. For example, if p=2, then xx, zz, xz, zx are the farms in the state. ...
1
vote
0answers
24 views

What does “original degree” of a row mean?

I'm working on an implementation of RFC6330 (https://tools.ietf.org/html/rfc6330), and in section 5.4.2.2 it says, "If r != 2, then choose a row with exactly r nonzeros in V with minimum original ...
0
votes
1answer
24 views

Entropy of a language

Im supposed to calculate the entropy of following language $L=\{x,y,z,w\}$ Symbols have following probability of occurrence: $p(x)=\frac{1}{2},\quad p(y)=\frac{1}{4},\quad p(z)=p(w)=\frac{1}{8}$ ,...
1
vote
2answers
46 views

Prove that $A_3(4,3)=9$ and construct the correspoding code.

$A_q(n,d)$ is the maximum M(number of codewords) such that a q-ary (n, M, d)-code exists. I know that according to Gilbert-Varshamov bound: $A_q(n,d)$ $\bigg\{ \binom {n}{0} + \binom{n}{1} (q-1)+...+...
2
votes
2answers
44 views

Find the elements of the extension field using primitive polynomial over $GF(4)$

Let $p(z) = z^2 + z + 2$ be a primitive polynomial. I want to construct the elements of the extensional field $GF(4^2)= GF(16).$ Since $p(z)$ is primitive polynomial , it should generate the ...
1
vote
1answer
25 views

What is the probability that the sent codeword will be eventually decoded correctly

I seem to be stuck on the following problem: Let $C=\{000,111,222\}$ be a ternary code which is sent over a symmetric channel with symbol-error probability $p$. We use an error detection system, so ...
0
votes
0answers
21 views

Near-Near-MDS codes

I am trying to understand the codes which are not maximum distance separable but are at a distance of 2 from being Maximum Distance Separable. I have trying to find articles specifically related to ...
6
votes
1answer
47 views

Verifying if a given polynomial is primitive polynomial

Given a polynomial: $f(x) = x^2 + 2x + 2$ over $GF(3)$. I want to know if i can use it to construct $GF(3^2)$. My approach: This equation satisfies first condition: A primitive polynomial is ...
0
votes
1answer
26 views

Creating the generator matrix of the linear block-code

How can i create a generator matrix for $(5,3)$ Linear block-code over $GF(2^2)$. Most of the books mention the operations on this matrix and also that the choice of the basis vector is not unique ...
0
votes
1answer
16 views

Simplification with exponents

I'm currently revising an exam about channel coding in telecommunications and we have a question where we need to isolate a variable $u$ in terms of another variable $q$. Currently, I am stuck with a ...
2
votes
2answers
66 views

Binary matrix with fixed inner product.

Suppose that $m,\ n$ are two positive integers such that $m<<n$. Let $a,\ b,\ c$ be the three positive integers such that $a\leq b < c$. Consider a binary matrix $A\in \{0,1\}^{m\times n}$, ...
0
votes
0answers
19 views

Method to find the maximum amount of codewords such that there exists a $q$-ary $(n,M,d)$-code

I just answered a question asking to prove that $A_{2}(4, 3) = 2$ and the only strategy I have really is a bit of trial and error. I was just wondering if there is an easy step-by-step method to find ...
0
votes
1answer
17 views

How to compute the syndrome polynomial? BCH code

I just copy the notation quickly. A variable with a space and then a number it means is a power. I have BCH cyclic code like that: B = BCH(7) of length 15 = 2 4 − 1. F 16 = F 2 [x]/(x 4 + x + 1), α ...
3
votes
1answer
48 views

Optimal code for simple game

Setup: Alice and Bob are playing a cooperative game. Alice chooses a number $y \in \{1, 2, 3, 4\}$ uniformly at random. Bob doesn't observe $y$; his goal is to guess $y$. Alice can send Bob a message $...
0
votes
1answer
29 views

What is the theory behind seeding a CRC?

The basic CRC check is a polynomial division in this form: $$ Q(x)Gen(x) + Rem(x) = \frac {x^nMsg(x) } { Gen(x) } $$ It's recommended that the polynomial is seeded so that an all-zero message does ...
1
vote
2answers
100 views

Find the smallest positive integer $\ell$ such that $3 \cdot \left(4^m + 1\right)$ divides $2^\ell-1$

Find the smallest positive integer $\ell$ such that $3 \cdot \left(4^m + 1\right)$ divides $2^\ell-1$ Hint: The sought $\ell$ is the multiplicative order of $2$ in the ring of integer residues ...
0
votes
1answer
77 views

q-ary symmetric channel error probability

Why is it valid to assume that $0< p < (q-1)/q$, where $p$ is the probability of symbol error. When $(q-1) / q< p <1$, why are we able to flip it? We are not in binary channel, so we are ...