Summary
Summary Coding & Cryptography exam preparation (X_405041)
- Course
- Institution
All the important terms, formulas, examples and facts you need to know before the Coding & Cryptography exam.
[Show more]
Seller
Followsandervanwerkhooven
Content preview
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 ⟩.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller sandervanwerkhooven. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $6.96. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
53068 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now