Cheatsheet Coding &
Cryptography
1. Introducti on to Coding Theory
A binary channel is symmetric if 0 and 1 are transmitted with equal accuracy. The channel’s
1
reliability is a real number < p<1, where p is the probability that the digit sent is the digit
2
received.
The information rate (or just rate) of a code C is a number (between 0 and 1) that measures
the proportion of each codeword that is carrying the message:
For an (n , k , d )-code, the information rate is log 2 (2 k )/n=k / n .
The Hamming weight or weight of a word v wt (v ) is the number of times a non-zero
element occurs in v .
The Hamming distance of distance between words v , w d ( v , w) is the number of positions
in which v and w disagree. d ( v , w )=wt ( v +w)
Complete Maximum Likelihood Decoding (CMLD): If there is one unique closest codeword,
decode to that. If there are multiple, pick one.
Incomplete Maximum Likelihood Decoding (IMLD): If there is one unique closest codeword,
decode to that. If there are multiple, request retransmission.
d−1
A code of distance d will correct all error patterns of weight less than or equal to ⌊ ⌋.
2
d−1
Moreover, there is at least one error pattern of weight ⌊ ⌋ +1 which will not be
2
corrected.
2. Linear Codes
The distance of a linear code is equal to the minimum weight of any nonzero codeword.
The set of all linear combinations of the vectors in a given set S={v 1 , v 2 ,... , v k } is called the
linear span of S and is denoted by ⟨ S ⟩ .
For a given set S={v 1 , v 2 ,... , v k }, the set of all linear combinations (w=a 1 v 1+ …+ak v k) is
called the linear span ⟨ S ⟩ . For any S ⊆ K n, the code C=⟨ S ⟩ consists of the zero word, all
words in S and all sums of two or more words in S.
If v={v 1 , v 2 , … , v k } and w={w1 , w2 , … , wk }, then the dot product or scalar product
v ⋅ w=v 1 w 1+ …+ v k wk . If v ⋅w=0 , v and w are orthogonal. The set of vectors that are
orthogonal to every vector in S is called the orthogonal complement S⊥. If C=⟨ S ⟩, we write
C ⊥=S⊥ and call C ⊥ the dual code of C .
, A set of vectors S={v 1 , … , v k } is linearly independent if the only way to get that
a 1 v 1 +…+ ak v k =0 is if all a i=0.
A nonempty subset B of vectors from a vector space V is a basis for V if:
1. B spans V (that is, ⟨ B ⟩=V ), and
2. B is a linearly independent set.
From this, it follows that any linearly independent set B is automatically a basis for ⟨ B ⟩.
The number of elements in the basis is called the dimension k of the space. Usually, a vector
space has multiple bases. But they all have the same number of elements: k .
A linear code of dimension k contains exactly 2k words. This number can be explained by
envisioning the creation of codewords from the basis as k binary choices whether to include
a word from the basis in the linear combination or not.
Let C=⟨ S ⟩ be the linear code generated by a subset S of K n . Then (dimension of C ) +¿
(dimension of C ⊥) ¿ n.
There are two types of elementary row operations that may be performed on a matrix:
1. Interchanging two rows
2. Replacing a row by itself plus another row
A leading 1 in a matrix is a 1 with no 1s to its left. A leading column is a column that contains
a leading 1.
A matrix M is in row echelon form (REF) if:
1. the zero rows of M (if any) are all at the bottom and
2. each leading 1 is to the right of any leading 1s above.
More strictly, M is in reduced row echelon form (RREF) if it is in REF and every leading
column contains exactly 1. Any matrix can be put in REF or RREF by using the elementary row
operations.
[ALG] Finding the basis for C=⟨ S ⟩
1. Form a matrix A whose rows are the words of S.
2. Find a REF of A .
3. The nonzero rows of the REF form a basis C=⟨ S ⟩.
[ALG] Finding the basis for C=⟨ S ⟩
1. Form the matrix A whose columns are the words in S.
2. Place A in REF by using elementary row operations.
3. Locate the leading columns in the REF.
4. The original columns of A corresponding to these leading columns form a basis
C=⟨ S ⟩.
Cryptography
1. Introducti on to Coding Theory
A binary channel is symmetric if 0 and 1 are transmitted with equal accuracy. The channel’s
1
reliability is a real number < p<1, where p is the probability that the digit sent is the digit
2
received.
The information rate (or just rate) of a code C is a number (between 0 and 1) that measures
the proportion of each codeword that is carrying the message:
For an (n , k , d )-code, the information rate is log 2 (2 k )/n=k / n .
The Hamming weight or weight of a word v wt (v ) is the number of times a non-zero
element occurs in v .
The Hamming distance of distance between words v , w d ( v , w) is the number of positions
in which v and w disagree. d ( v , w )=wt ( v +w)
Complete Maximum Likelihood Decoding (CMLD): If there is one unique closest codeword,
decode to that. If there are multiple, pick one.
Incomplete Maximum Likelihood Decoding (IMLD): If there is one unique closest codeword,
decode to that. If there are multiple, request retransmission.
d−1
A code of distance d will correct all error patterns of weight less than or equal to ⌊ ⌋.
2
d−1
Moreover, there is at least one error pattern of weight ⌊ ⌋ +1 which will not be
2
corrected.
2. Linear Codes
The distance of a linear code is equal to the minimum weight of any nonzero codeword.
The set of all linear combinations of the vectors in a given set S={v 1 , v 2 ,... , v k } is called the
linear span of S and is denoted by ⟨ S ⟩ .
For a given set S={v 1 , v 2 ,... , v k }, the set of all linear combinations (w=a 1 v 1+ …+ak v k) is
called the linear span ⟨ S ⟩ . For any S ⊆ K n, the code C=⟨ S ⟩ consists of the zero word, all
words in S and all sums of two or more words in S.
If v={v 1 , v 2 , … , v k } and w={w1 , w2 , … , wk }, then the dot product or scalar product
v ⋅ w=v 1 w 1+ …+ v k wk . If v ⋅w=0 , v and w are orthogonal. The set of vectors that are
orthogonal to every vector in S is called the orthogonal complement S⊥. If C=⟨ S ⟩, we write
C ⊥=S⊥ and call C ⊥ the dual code of C .
, A set of vectors S={v 1 , … , v k } is linearly independent if the only way to get that
a 1 v 1 +…+ ak v k =0 is if all a i=0.
A nonempty subset B of vectors from a vector space V is a basis for V if:
1. B spans V (that is, ⟨ B ⟩=V ), and
2. B is a linearly independent set.
From this, it follows that any linearly independent set B is automatically a basis for ⟨ B ⟩.
The number of elements in the basis is called the dimension k of the space. Usually, a vector
space has multiple bases. But they all have the same number of elements: k .
A linear code of dimension k contains exactly 2k words. This number can be explained by
envisioning the creation of codewords from the basis as k binary choices whether to include
a word from the basis in the linear combination or not.
Let C=⟨ S ⟩ be the linear code generated by a subset S of K n . Then (dimension of C ) +¿
(dimension of C ⊥) ¿ n.
There are two types of elementary row operations that may be performed on a matrix:
1. Interchanging two rows
2. Replacing a row by itself plus another row
A leading 1 in a matrix is a 1 with no 1s to its left. A leading column is a column that contains
a leading 1.
A matrix M is in row echelon form (REF) if:
1. the zero rows of M (if any) are all at the bottom and
2. each leading 1 is to the right of any leading 1s above.
More strictly, M is in reduced row echelon form (RREF) if it is in REF and every leading
column contains exactly 1. Any matrix can be put in REF or RREF by using the elementary row
operations.
[ALG] Finding the basis for C=⟨ S ⟩
1. Form a matrix A whose rows are the words of S.
2. Find a REF of A .
3. The nonzero rows of the REF form a basis C=⟨ S ⟩.
[ALG] Finding the basis for C=⟨ S ⟩
1. Form the matrix A whose columns are the words in S.
2. Place A in REF by using elementary row operations.
3. Locate the leading columns in the REF.
4. The original columns of A corresponding to these leading columns form a basis
C=⟨ S ⟩.
