introduction

Question 1

alphabet:

Answer 1

a finite set of 2 or more elements

Question 2

symbol:

Answer 2

an element of an alphabet

Question 3

information:

Answer 3

a stream/sequence of symbols

Question 4

noise:

Answer 4

there is noise in a channel that causes a small number of random errors

Question 5

memoryless channel:

Answer 5

a function that takes an input x and gives a random output y which depends only on x

Question 6

noisy/noiseless:

Answer 6

a noisy channel has random noise, a noiseless one doesn’t, we are dealing mostly with noisy ones tho

Question 7

BSC(p):

Answer 7

the binary symmetric channel, a memoryless noisy channel, when a symbol x is sent, either the received output is x, in which case there was no error, or y!=x, where an error occurred, with a certain probability that a bit will be flipped

Question 8

symbol error:

Answer 8

when a symbol is altered by noise

Question 9

channel coding:

Answer 9

the sender encodes the message before sending it, allowing to receiver to detect most errors and sometimes to correct them

Question 10

word:

Answer 10

a word of length n in the alphabet F is an element F^n, where n is how many symbols are used per word

Question 11

code:

Answer 11

a code of length n in the alphabet F is a nonempty subset of F^n, we denote a code by C, a codeword is an element of a code - basically take only a few potential words of F^n and use them as codewords

Question 12

encoder:

Answer 12

a bijective function ENCODE:F^k->C

Question 13

P(undetect)(C):

Answer 13

the probability of an undetected error

Question 14

E3:

Answer 14

codewords {000,011,101,110} - only even 1s
00->000, 01->011, 10->101, 11->110 - basically add the digit that would make the original word have an even no. of 1s|
the probability of an undetected error is 3p^(2)(1-p)
can’t correct errors with it

Question 15

hamming distance:

Answer 15

the number of differences in symbols between two words (Not how great the difference is, just if there is one)
d(x,y)

Question 16

decoder:

Answer 16

DECODE:F^n->C such that for any y in F^n, DECODE(y) is the nearest neighbour of y in C

Question 17

nearest neighbour:

Answer 17

a nearest neighbour of y in C is a codeword c such that d(c,y) = min{d(z,y): z in C} - smallest hamming distance to a codeword basically

Question 18

Rep(3, F2):

Answer 18

codewords are 000 and 111
ENCODE: {0,1} -> Rep(3,F2) by ENCODE(0)=000, ENCODE(1)=111
each possible word has only one nearest neighbour, so this both detects and corrects errors