Samenvatting
Summary Tentamen voorbereiding Coding & Cryptography (X_405041)
Alle belangrijke termen, formules, voorbeelden en feiten die je moet kennen voor het tentamen voor Coding & Cryptography.
[Meer zien]Voorbeeld 2 van de 11 pagina's
Voorbeeld 2 van de 11 pagina's
In winkelwagengesponsord bericht van onze partner
Verkoper
VolgenVoorbeeld van de inhoud
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 ⟩.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper sandervanwerkhooven. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €6,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 83637 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen