College aantekeningen

College aantekeningen Coding & Cryptography (X_405041)

0 keer verkocht

Instelling
Vrije Universiteit Amsterdam (VU)

Uitgebreide aantekeningen van alle hoorcolleges van het vak Coding and Cryptography, dat wordt gegeven op de Vrije Universiteit (VU) aan de master 'Computer Science'.

[Meer zien]

Voorbeeld 4 van de 55 pagina's

Bekijk voorbeeld

Geupload op 5 oktober 2023
Aantal pagina's 55
Geschreven in 2022/2023
Type College aantekeningen
Docent(en) R.m.h. de jeu
Bevat Alle colleges

€5,74

In winkelwagen

Op verlanglijstje

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

Lecture 1. Introduction
Lectures on Tuesday & Friday. Problem sessions on Wednesday.
The idea is that you want to send some information over a “noisy” channel. “Noisy” here
means that it will create errors: what comes out of the channel does not have to be exactly
what came in (e.g., telephone lines or writing to hard disk).
From an information source, data is put into an encoder (channel encoding), which adds
extra information to help correct errors later on.
This encoded information is passed over the channel, which might affect the data due to the
noise on the channel. When finally passed to the decoder, you want to correct the errors
introduced by the channel’s noise.
The decoding process consists of two processes:
1. Detect and correct errors (if possible) (also called decoding, as the actual channel
decoding is fairly trivial).
2. Channel decoding: undo channel encoding.
Some considerations for good codes are:
- Easy channel encoding for transmission
- Easy channel decoding
- Easy decoding error detection + correction.
- Good error correcting/detecting capabilities.
- Good information rate (e.g., there could be a code where the channel encoder
returns 000 for input 0. This is called “triple repetition” and has a bad rate of transfer
of information).
If p = chance of correct transmission of each symbol, then the chance of correct
transmission of pure information (0 or 1) is p.
Using triple repetition encoding, a message is decoded as 0 if it contains more 0’s than 1’s.
Hence, the chance of a correct submission is p3 (all of the 0’s remains correct) +3 p2 (1− p)
(any of the 3 cases occur where one 0 flips and 2 remain correct (001 , 010 ,100 )).
For a channel where p=0,9, triple encoding increases the chance of correct transmission
over the channel from 0,9 to 0,972.
Assumptions:
- We send information as a sequence of 0’s and 1’s, which are called digits.
- A word is a sequence of digits. The length of a word is the number of digits in it.
- We send words across a binary channel (it only knows 0’s and 1’s and is unable to
produce 2, 3, 4, …), one after the other.
- A block code is a set of C words (length denoted as ¿ C∨¿) where every word has
the same length (e.g., triple repetition has block length 3).

,Channel assumptions:
- The probability of an error is the same for any digit (a 0 flipping to a 1 is equally likely
as a 1 flipping to a 0). If this is the case, the channel is symmetric.
- The probability of an error in one digit is independent from errors in any of the other
digits (an error in the first digit does not make it more likely for there to be an error
in the second digit).
BSC = Binary Symmetric Channel.
Suppose a codeword v is sent across a BSC and a word w is received.
If w is in the code (e.g., it’s 000 or 111 when using triple repetition), we accept it. If w ≠ v ,
undetected errors can occur.
If w is not in the code, we have to try to detect and correct the error.
1
The (information) rate of code C of length n is log 2 ¿ C∨¿ ¿ (if |C|=2 k, then we can write C
n
in k digits but use n ). This number expresses what part of the redundant message is actually
k
meaningful. In the |C|=2 k example, the information rate is .
n
Say you have a code C 2 that contains all the length-2 words (00 , 01 ,10 , 11), with a parity bit
2
added: [000 , 011, 101 ,110] , the rate is . C 2 can detect errors in one digit only. Correction is
3
hopeless, because flipping any bit will give a word that’s in the code so you don’t know
which one was sent originally.
The chance of i errors occurring in a word of length n is given by the formula below:
n i
∑ (ni ) p n−i ( 1− p )
i=1

,Lecture 2.
What is the chance ϕ p ( v , w) that, if a codeword v is sent, the word w is received?
We know p = the reliability of the BSC, n = the length of the word, d = the number of digits
n−d d
that differ. Then ϕ p ( v , w )= p ( 1− p ) .
Let’s decode a received word w to a code word v such that ϕ p ( v , w) is maximal. That is,
ϕ p ( v , w )=max {ϕ p ( u , w ) : u ∈C }
1
Suppose we have a BSC with reliability < p<1. Suppose v1 , v 2 are codewords of length n , w
2
was received. If v1 and w differ in d 1 digits and v 2 and w differ in d 2 digits, then
ϕ p ( v1 , w ) ≤ ϕ p ( v 2 , w ) ⇔ d 1 ≥ d 2.
Algebra
K={0,1 } with 1+1=0 .
For n ≥ 1, K n denotes the set of all n -length words using the elements in K (a vector space
over K ). Page 10-11 of the book shown the operations that can be done in this space.
Weights/distance
For v ∈ K n, the (Hamming) weight wt (v ) is the number of non-zero positions in v.
For v , w ∈ K n the (Hamming) distance d ( v , w) is the number of positions where v and w
differ. Note that d ( v , w )=wt ( v−w )=¿ (due to our K -space) w (v + w).
d ≥ 0 , d ( v , w )=0 ⇔ v=w
d ( v , w )=d (w , v)
d ( v , w ) ≤ d ( v ,u )+ d (u , w)
d ( v, w ) wt ( v +w )
ϕ p ( v , w )= pn−d ( v ,w ) ( 1− p ) = p n−wt (v+ w ) (1− p )

Maximum likelihood decoding (MLD)
A received word w ∈ K n is decoded to v ∈C as follows:
1. Complete maximum likelihood decoding (CMLD): decode w to v ∈C with d ( v , w) is
minimal. If several v are tied, just make a choice.
2. Incomplete maximum likelihood decoding (IMLD): decode w to v ∈C if it is the
unique element of C where d (v , w) is minimal, and maybe even want to limit the
number of changes we allow between v and w . If we can’t decode, we don’t decode
(and might ask for retransmission or interpolate if it concerns a large volume
sequence). Incompleteness here means that not every w maps to a v ∈C .
MLD is really nearest-neighbor decoding, because you compare w to all v ∈C , and pick the
nearest neighbor.

, For a given code C ∈ K n and v ∈C , what is the chance of decoding the received word to v ?
Say we decode using IMLD, where we only decode to the unique nearest neighbor v' ∈C (if
it exists)
We get v back only if

w ∈ L ( v )={ u ∈ K | d ( u , v ) < d ( u , v ) for all v ≠ v ∈C }
n ' '

In words, that is if w is in the set L(v) of v ∈ K n where v is the unique nearest neighbor
that’s in the code C .
θ p denotes the probability that if v is sent over a BSC of probability p then IMLD correctly
concludes that v was sent
θ p ( C , v )= ∑ ϕ p (v , w)
w ∈L(v)

Suppose n=3 ,C=[000,111], then

Error detection and correction
Let d=d ( C )=min d ( v , v' ) with v , v ' ∈C ∧ v ≠ v ' . For a code C containing at least two words
the distance of the code C is the smallest of the numbers d ( v , w) as v and w range over all
pairs of different codewords in C .
C detects an error pattern u ∈ K n ≠ 0 (if there are no errors, you can’t detect them),
if v+u ∉ C , ∀ v ∈ C (that is, you know there’s an error if what comes out of the channel is not
in the code).
C is t -error detecting if it detects all error patterns of weight at most t , and it fails to detect
some of weight t+ 1(otherwise it would be t + 1-error detecting).
If d=d (C), then the code is d−1-error detecting.
Let’s now correct some errors. C corrects the error pattern u if v+u for any v ∈C is decoded
to v and not to some other v' ∈C . Hence,
' ' '
∀ v ∈ C ∧ v ≠ v , d ( v , v +u ) <d (v , v +u)
That is, a code C corrects the error pattern u if, for all v in C , v+u is closer to v than to any
other word in C .
C is t -error correcting if it corrects every error pattern u of weight at most t and it fails to
correct some error pattern of weight t+ 1 (otherwise it would be t+ 1-error correcting).

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

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 €5,74. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 69052 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis