error-correcting codes, error-detecting codes and related algebraic and/or combinatorial constructions

learn more… | top users | synonyms

1
vote
0answers
9 views

How to model a coding problem with Poisson Distribution

I've met a problem in information theory that deals with probability and number of occurrence. It states that: The probability of a single bit being corrupted is p. Now I have an error-correction ...
1
vote
1answer
12 views

One hypothesis concerning Hamming distance matrix

Suppose $a_1, a_2, \ldots, a_m$ are different strings of the same length n. And let $V = [v_1, v_2, \ldots, v_n]$ be a matrix such that $V_{i, j}$ is a Hamming distance between $a_i$ and $a_j$. ...
1
vote
0answers
24 views

finding subsets up to isomrphism

Let $C_n$ be a code of length $n$ of digits $0$ or $1$. How can one find all subsets of $C_n$ up to isomorphism?. A numerical example can be also very helpful. Thanks.
0
votes
0answers
11 views

How to make parity-check matrix

I'm working on exercise I found in book. There is a coding matrix, which elements are given as logarithm's values. Here is a matrix. $$G_c =\left( \begin{matrix} 2 & 1 & 1 & 0 & 1 ...
1
vote
0answers
17 views

Hat puzzle with non-standard number of players

I'm referring to the Ebert's version where the solution is closely related to Hamming codes. What happens if there are not 2^^K-1 players ? I wrote an algorithm to try to find how many N long ...
-1
votes
0answers
12 views

$Mod 3$ or $mod 5$ for for an $N5(3, 5)$ is a $[5, 2, 4]5$ Reed Solomon code.

I am trying to reduce a matrix to the form $G = [I|-B^T]$ but I just cannot get my solution to match the solution in my notes. I am reducing it Mod 3 as it is part of a coding theory question in ...
0
votes
0answers
22 views

Problem reducing a matrix modular 3

I am trying to reduce a matrix to the form $G = [I|-B^T]$ but I just cannot get my solution to match the solution in my notes. I am reducing it Mod 3 as it is part of a coding theory question. So my ...
0
votes
0answers
18 views

Reducing generator matrices for the codes $N_5(3,5)$ and $N_5(3,5)^\perp$ to a standard form $[IB]$ or $[BI]$

I am just covering a chapter on MDS codes and am attempting a question but not getting the same solution as in the notes. Here is the question: Write out the generator matrices for the codes ...
0
votes
1answer
29 views

a question about entropy of run length coding

I'm doing an exercise from chapter two of $\textit {elements of information theory}$. Here is the problem and its solution, . I'm not very clear about the equation 2.36 or say why does the equation ...
-1
votes
0answers
33 views

Generator matrix for Reed-solomon Code 2

kindly explain how to write generator matrix for Reed-Solomon code $(3,5)$ which is the same as the $[5,2,4]$ $5$-ary code. Also, how do I write it in standard form [IB] and prove that every minor of ...
1
vote
0answers
28 views

Latin Squares and Olderogge Code

So I have two Latin Squares, $A$ and $B$ that form a pair of MOLS of order $m$. I then have an Olderogge code formed from $A$ and $B$, where each binary vector of length $m^2$ is encoded as a codeword ...
0
votes
1answer
29 views

Different BCH code between encoder and decoder

I am searching for the mathematical properties of the BCH codes that could explain that if I encode a message with a BCH defined by $(m=6,n=63,k=24,t=7)$, I can decode that message correctly with ...
0
votes
0answers
24 views

Sum of Coding rates of encoders accessible by decoder must be at least “h”, in order for “r” to be admissible. How?

Let we have one source with information rate "h" and 4 encoders with information rate r1, r2, r3 and r3 and r=[r1...r4]. Following conditions are necessary for r to be admissible. How? r1+r2 >= h ...
1
vote
2answers
65 views

How to represent a number in such a way that no more than 2 consecutive digits are the same?

The idea is to lower the probability of transcription errors when a person is reading the number on a paper and typing it on a computer, for instance. I'd be more interested in Base-58 notation, but ...
1
vote
1answer
15 views

Why Are The First and Last Entries of a Binary Reflected Gray Code Sequence Adjacent?

Some Information on Gray Codes If you're rusty or unfamiliar with Binary Reflected Gray Code, but want to try and help, here is a youtube tutorial explaining what they are: ...
1
vote
1answer
35 views

Bioinformatics meets Combinatorics. How to find a subset in a combinatorial problem?

I’m having a bioinformatics related problem. Let me walk you through it: The DNA base ambiguity code can be represented by 15 letters, where each codes for a different subset of DNA bases therefore ...
2
votes
0answers
34 views

Shortened Reed-Solomon proving p(D) is primitive

Assume we have a shortened $(n=18, k=12, t=3)$ Reed Solomon code in $GF(2^{8})$.Let $\alpha$ be a primitive element of $GF(2^{8})$. Consider the primitive polynomial given by: $p(D) = D^{8} + D^{4} + ...
1
vote
1answer
52 views

kind of mathematical puzzle

i was recently doing this problem--- problem statement You have r red, g green and b blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons ...
1
vote
0answers
29 views

Show a binary code does not exist. [duplicate]

Show that there is no $(6,9,3)$ binary code. I'm pretty sure the way to tackle this problem is to deal with it's generator matrix and then get a condradiction. However I seem to be getting no ...
0
votes
0answers
23 views

hamming weight of error correcting codes and BCH codes

In general the hamming weight of codewords of error correcting codes is well understood. If I were to write down the $k \times n$ generator matrix, with the span of the rows corresponding to the ...
3
votes
2answers
52 views

ISBN check digit

a ISBN-10 has 10 digits. The correctness of the last digit, the check digit, can be verified using the following formula: $$(x_1 + 2x_2 + 3x_3 + 4 x_4 + 5x_5 + 6x_6 + 7x_7 + 8x_8+9x_9+10m) \text{ mod ...
1
vote
1answer
31 views

Use a parity check matrix for Ham(4,2) and syndrome decoding

I have a coding theory question which I am confused about: Use a Parity check matrix for Ham(4,2), with the columns in lexicographical order, and syndrome decoding to decode a.) 00000 00000 11111 ...
0
votes
1answer
51 views

Weights of Binary Linear Code

I was looking at this problem related to coding theory: How do we know a linear code have even weight? Can anyone explain how we know either all codewords have even weight or half the codewords have ...
0
votes
2answers
27 views

Linear Code Problem, Weight & Minimum Distance

Please the highlighted part in the image below. I don't understand why w(c2) must be larger than s(c1, c2) considering s(c1, c2) is counting the position where c1 + c2 = 0, c1 != 0 and c2 != 0 while ...
1
vote
0answers
83 views

Latin square code dimension

I am need to understand what is the dimension of the code generated by the Olderogge Encoding: Given two mutually orthogonal latin squares, the encoding of a message of $m^2$ bits is: the message ...
0
votes
1answer
30 views

Calculating the information per symbol of a markov chain source

I have a 4-state 2nd order markov chain source with symbols 0 and 1. I have all the transition probabilities and have worked out the probabilities of each state. How do I go about finding the amount ...
0
votes
0answers
21 views

How to find generator matrix given a PCM of a Hamming code?

I'm having trouble as how to begin solving this. I'm given a Hamming Parity Check Matrix, and I have to find code vector V and generator matrix G. H = \begin{bmatrix} ...
0
votes
0answers
34 views

Dictionary learning for sparse coding using ADMM

I'm trying to formulate an ADMM for performing dictionary learning (for sparse coding) on a set of data. Let's assume we have a data matrix of $X \in \mathbb{R}^{M \times N}$, a dictionary of $D \in ...
2
votes
1answer
58 views

Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?

Consider the polynomial $p(x) = 1+x^5+x^{10}$ with binary coefficients. Consider the multiplicative group of $\mathbb{F}_{16}$, and let $p(x)$ be evaluated at each of these $15$ elements. The only ...
0
votes
1answer
36 views

Finding a generator matrix for C in standard form using only row operations

Let $C$ be the [5,4] code over $F_7$ with generator matrix $G=$ $$\begin{pmatrix} 1 & 0 & 3 & 5 & 4 \\ 0 & 0 & 2 & 3 & 5\\ 2 & 1 & 0 & 3 & 0\\ 1 ...
0
votes
1answer
18 views

Equivalent Codes and weight

If $C$ and $D$ are equivalent linear codes, how can I show that the number of words with weight $w$ in Code $C$ is equivalent to number of words with weight $w$ in Code D?
0
votes
0answers
32 views

Generator Matrix G

The question is: Suppose C is a linear $[3,2]$-code over $\Bbb{F}_q$ with generator matrix $G$. Show that using elementary operations, we can transform $G$ into one of the matrices: $$ M_1 = ...
0
votes
1answer
39 views

Probability in a Random Matrix

Assume the following random matrix with $N$ rows and $L$ columns consisting of elements in {0,1}. \begin{bmatrix} 1 &0 & 1 & ...&0 \\ 1 & 0 & 0& ... &1 \\ 1 & 0 ...
1
vote
0answers
23 views

Binary Goppa Codes: Calculating code characteristics (traces, length L, distance d, k)

I am having (many) troubles with binary Goppa Codes. My question is at the moment: How do I calculate the trace on given points $tr(\alpha^u)$? For example: Given a finite field $GF(2^6)$ and the ...
1
vote
1answer
26 views

Equivalence of Codes

Consider the binary codes below: C1= {0000, 1100, 1010, 0110} C2= {0111, 0100, 0010, 0001} C3= {1000, 0100, 0010, 0001} Show that C1 is not equivalent to C3. Is C2 equivalent to C3? When we say two ...
0
votes
0answers
35 views

What are the possible dimensions of a binary cyclic code of length 37?

What about the possible dimensions of a 16-ary cyclic code of length 37? [Edit]: The cyclic codes of length $37$ are in a bijective correspondence with factors of $x^{37}-1$. Furthermore, the ...
4
votes
1answer
39 views

Hamming(7,4) matrix for decoding?

Encoding a 4bit word (vector) $w$ can easily be done by $c := Gw$. Decoding a codeword of the Hamming(7,4) code is normally done by first computing $p = Hc$ where $p$ is zero, if there is no 1-bit ...
0
votes
1answer
39 views

How to prove that a code has an unique decodability

I have the alphabet: $A=\{a,d,k,u\}$, The code: $c=110011100111010$ An code words: $$ \begin{array}{|c|c|c|c|} \hline x \in A& a & d & k & u \\ \hline \gamma (x) & 001 & ...
2
votes
0answers
57 views

Picking codewords that are close

Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and number of minimum weight codewords $N_d$. How many ways can you select codewords $c_1,\dots,c_T$ (assume $T\ll q^k$) such ...
3
votes
1answer
92 views

Upper bounds for the dimension of a binary cyclic code

Let $\mathbb{F}_2 = \{0,1\}$ denote the field with two elements. Consider a binary $N$-tuple $a = a_0 a_1 \ldots a_{N-1}$, of elements $a_i \in \mathbb{F}_2$. The cyclic code $C_a$ corresponding to ...
0
votes
1answer
38 views

Huffman coding - conditions for perfect tree output

The question is: Given 4 characters and their frequencies, what's the max possible difference between the frequency of the rarest character and that of the most common character, so the output Huffman ...
1
vote
0answers
31 views

The rate of a code with prescribed minimum distance

Fix $\delta\in(0,1)$. For integer $n$, what is the largest size of a subset $C\subset\{0,1\}^n$ such that any two elements of $C$ are at least $\delta n$ away from each other in the Hamming metric? In ...
0
votes
1answer
33 views

If $n=(b_k,b_{k−1},…,b_1)_2$ where $b_i$ are the digits of n in binary, what is the binary expression of $n+1$?

I have a curiosity. If $n=(b_k,b_{k−1},...,b_1)_2$ where $b_i$ are the digits of n in binary, what is the binary expression of $n+1$? Is there a relationship that binds $n+1$ to $b_i$ (ie the digits ...
0
votes
0answers
21 views

Prove a relation on Gray code $(0,b_k,…,b_3,b_2)+(b_k,b_{k−1},…,b_2,b_1)$.

Suppose we want to find the n-th entry in the binary Gray code. Write $n=(b_k,b_{k−1},...,b_1)_2$ where $b_i$ are the digits of n in binary. Then, prove that the corresponding Gray code entry is ...
0
votes
1answer
17 views

Cryptographic encoding scheme that enables counting

Suppose there are $n$ players. Each player has a $k$-length bit vector. Is there an efficient way of encoding the $k$ length bit vectors, such that after receiving the $n$ encoded outputs, one can ...
1
vote
1answer
27 views

What bound does the Hamming bound give you for the largest possible size of a $t$-error-correcting code of length $2t + 1$?

Let $\mathbb{A}$ = $\{0, 1\}$ and suppose $t$ is a positive integer. What bound does the Hamming bound give you for the largest possible size of a $t$-error correcting code of length $2t+1$? I have ...
1
vote
0answers
57 views

Intuition behind the link between coding theory and group theory

I am trying to find an easy link between group theory and coding theory. The usual path that most of the texts follow is that they present introductory material on groups, fields, rings, etc., and ...
0
votes
1answer
29 views

How do I prove that if $x, y ∈ F_n^{2}$ then w(x) + w(y) + w(x+ y) is even and at most $2n$?

Let $w(x)$ denote the Hamming weight of a binary word $x = (x_1,x_2, \ldots, x_n) \in \mathbb F_2^n$. Show that if $x, y ∈ \mathbb F_2^n$ then $w(x) + w(y) + w(x+ y)$ is even and at most $2n$. I ...
0
votes
0answers
39 views

Maximum $M$ in Binary$ (5,M,3)$ Code

The sphere packing bound (hamming bound) gives that $M\leq5$, but I need to show 'by construction' that $M=4$. It would take a long time to write out all possible sets of code words of size $4$ and ...
0
votes
0answers
34 views

Determining generator matrix

Gents, I have the 128 codewords of a [14,7,4] binary linear code - which is actually the Plotkin $(a\mid a+b)$ construction of $Ham(3,2)$ and $Sim(3,2)$. Now, I want to have its generating matrix, ...