Is this coding exercise well thought? I have to create a code C of 5 words with length n=6, with the alphabet F_2={0,1} that corrects 1 mistake.

ymochelows

ymochelows

Answered question

2022-09-07

Is this coding exercise well thought?
I have to create a code C of 5 words with length n = 6, with the alphabet F 2 = { 0 , 1 } that corrects 1 mistake.
I am new to coding theory so I am having some troubles with this particular question...
If it corrects 1 mistakes, that means that d > 2 1 (I believe this is a well-known result [I prove it at my courses]), where d is the minimal distance of the code C defined as d = d ( C ) = min { d ( x , y ) | x , y C , x y }, and that distance in the definition is the Hamming distance defined as d ( x , y ) = # { i | 1 i n , x i y i }, being x = ( x 1 , x 2 , . . . , x n ) and y = ( y 1 , y 2 , . . . , y n ) elements in F q n (where F q is the alphabet of the code, and n denotes the length of the words).
So, in my particular case I want that the minimal distance of the code is greater than 2, i.e., I want that there are no two different words in the code that have Hamming distance equal or lesser than 2, i.e., no two words in the code that have more than 4 coordinates equal to each other (as If they have four equal to each other, there would be 6 4 = 2 different to each other, so the Hamming distance would be 2, and if there are 5 equal to each other, the Hamming distance would be 1 which is not valid). So, I begin to construct the code, by taking the first word:
( 1 , 1 , 1 , 1 , 1 , 1 ) F 2 6
Then, I could take another one like:
( 1 , 1 , 1 , 0 , 0 , 0 ) F 2 6
which satisfies the previous conditions. So, taking this kind of words, and taking on account the conditions that must hold, I could keep going with this ''constructive algorithm'' until I have 5 words. For example:
( 1 , 0 , 0 , 1 , 0 , 0 ) F 2 6
( 0 , 1 , 0 , 1 , 1 , 0 ) F 2 6
( 0 , 0 , 0 , 0 , 0 , 0 ) F 2 6
And this would conclude the exercise (by taking all this 5 words listed above). I am not sure if this is a great argument and I would really appreciate if someone could give me some feedback on it...

Answer & Explanation

Gracelyn Paul

Gracelyn Paul

Beginner2022-09-08Added 17 answers

Step 1
It is unclear whether your greedy algorithm will always work without backtracking, as pointed out in the comments.
To put the question in context, you need minimum distance d 3 for a length n = 6 code.
The Hamming code has parameters [ n , k , d ] = [ 2 m 1 , 2 m m 1 , 3 ] and it is linear. Take m = 3 to obtain a [7,4,3] code. Since it is linear half its codewords have 1 in any single bit position. So take half of its codewords which have a 1 in the last position and drop the last coordinate. You get a code with 8 codewords, length 6 and minimum distance 3. This is called shortening a code. You can take a subset of this code to answer your question.
Edit:
Consider any binary [n,k] linear code defined by a k × n generator matrix G = [ G 1 | | G n ] via
m T G = c
where the arithmetic is modulo 2. Fix the last codeword bit, say c n .. Also assume that the generator matrix is nontrivial, i.e., all its columns are nonzero. We then have
( c 1 , , c n ) = ( m T G 1 , m T G 2 , , m T G n ) ,
thus c n = m T g n .. Let the column G n = ( g 1 , , g k ) ,, and m = ( m 1 , , m k ) and note that this means
c n = m 1 g 1 + m 2 g 2 + + m k g k .
Step 2
Assume without loss of generality that the first coordinate g 1 0.. Let the expression
c = m 2 g 2 + + m k g k
take on the value 0 exactly f times and the value 1 exactly 2 k 1 f times as the vector ( m 2 , , m k ) ranges over F 2 k 1 and let the subset of F 2 k 1 where c′ takes on the value 0 be denoted X 0 .. Since g 1 0 ,, then g 1 = 1.. This means that the last bit
c n = c + m 1
takes on the values 0 and 1 equally many times (f times each) when ( m 2 , , m k ) X 0 .. Also c n takes on the values 0 and 1 equally many times 2 k 1 f times) when ( m 2 , , m k ) F 2 k 1 X 0 ..
So c n takes on the values 0 and 1 exactly 2 k 1 times each.
yamalwg

yamalwg

Beginner2022-09-09Added 17 answers

Step 1
We can try a linear code. But then we would have 2 k codewords. Then, let's try to find one with k = 3. If we succeed, we'll have a codebook with 8 codewords, which is more than we need (we'll remove 3 of them and we'll be done).
The parity check matrix H must have dimensions ( n k ) × n = 3 × 6. Let's build it so it has d m i n 3. Recall that the minimal distance equals the minimum number of columns of H that are LD. Then, to attain d m i n 3 it suffices to have H with different columns (and not zero).
Then, it's possible, for example (let's make it systematic).
H = ( 1 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 ) = ( I | P )
(BTW: this is how we design Hamming codes).
What remains is to write G = ( P t | I ), write down the 2 3 codewords and pick five of them.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?