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

learn more… | top users | synonyms

0
votes
0answers
27 views

Is there an alternative encoding scheme to binary where similarity of pattern correlates with size of number?

If I compare binary for 7 111 and binary for 8 1000 there is no correlation between these two patterns that suggests that ...
1
vote
0answers
15 views

Relationship between hamming weight and number of codewords of a binary code

Set $ N_c (i,4)$ as the number of codewords in a binary code C with hamming weights congruent to $i$ module $4$. Assuming C is of length $n$ and dimension $k$, how can it be proved that if $C$ is an ...
0
votes
1answer
30 views

Linearity of codes

Assuming $C$ is a binary linear code and let $a$ $\notin $ $C$ be any vector. Show that $C$ $\cup (a + C) $ is also linear. I know that for any $C_1,C_2 \in C $ then $\alpha C_1 + \beta C_2 \in C$ ...
1
vote
0answers
36 views

Vector distance

Suppose $\overline{u},\overline{v},\overline{w},\overline{x}$ are four vectors, pairwise distance d apart. Show that d must be even, there's exactly one vector which is a distance $d\over 2$ from each ...
0
votes
1answer
16 views

Maximum code words

i am new to coding theory. i am trying to understand some of the basics by solving a few questions. I came across this one. Assuming $\\C$ is a binary (not necessarily linear) code of length $\\n$ and ...
0
votes
0answers
21 views

Intersection of balls in Hamming space

Let $B(x_1, r)$ and $B(x_2,r)$ be balls in $\{0,1\}^n$ (in Hamming distance). Denote by $d$ Hamming distance between $x_1$ and $x_2$. What is $|B(x_1, r) \cap B(x_2, r)|$ (asymptotically)? Upd: I ...
1
vote
0answers
40 views

DataMatrix convolutional codes

I'm trying to decode datamatrix code ECC 000-050 it uses convolutional codes for error correction. Could someone explain me how to decode the stream (e.g. few first bytes of the stream) or give some ...
0
votes
0answers
11 views

How to show a random matrix has large spectral gap?

If I know $Y$ is a random d-regular bipartite graph (tanner code in coding theory), can I show $Y^TY$ has large spectral gap with high probability? More specifically: If I know $Y=AX \in ...
1
vote
0answers
15 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
17 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$. ...
0
votes
0answers
15 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
18 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
17 views

$Mod 3$ or $mod 5$ for for an $N_5(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
30 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 ...
-2
votes
0answers
35 views

Generator matrix for Reed-solomon Code 2 [on hold]

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
30 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
30 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
25 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
36 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
64 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
28 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
37 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
60 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
37 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
20 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
27 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
37 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
59 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
94 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 ...