Title: Theory / Unimportant / CS / Fundamental / Information Theory, Inference and Learning Algorithm / Information Theory

Name: Information theory
Definition: the theoretical limitations and potentials of encoding/decoding system over noisy channel
Page: 5
Chapter: 1
Section: 2

Name: Coding theory
Definition: creation of practical encoding/decoding system over noisy channel
Page: 5
Chapter: 1
Section: 2

Name: Repetition code
Definition: Encoding: repeating each bit \(N\) times
Page: 5
Chapter: 1
Section: 2
Notation: \(R_N\)
Definition2: Decoding by majority
Assuming: \(N\) odd

Question: In \(R_N\) with probability one half for each bit, and \(f\) for a transmission error, the probability of a correct decoding is
Answer: \(\sum_{n=(N+1)/2}^N{N\choose n}f^n(1-f)^{N-n}\)
Page: 8
Chapter: 1
Section: 2
Index: 3
Kind: Ex

Name: A block code
Definition: A rule for converting a sequence of source bits \(s\), of length \(K\) into a transmitted sequence \(t\) of length \(N\) bits.
Page: 9
Chapter: 1
Section: 2
Context: information theory

Name: A linear block code
Definition: A block code whose extra bits are a linear function of the source bits.
Page: 9
Chapter: 1
Section: 2

Name: A parity check bit
Definition: A non-source bit of a linear block code
Page: 9
Chapter: 1
Section: 2

Name: The \((7,4)\) Hamming code
Definition: The parity check bit \(i\) is the sum of each source bit, but the \(i\)-th one, modulo 2
Page: 9
Chapter: 1
Section: 2
Conjdef: equivalenty
DefType: A linear block code with \(N=7\) and \(K=4\)

Name: Its generator matrix
Definition: A matrix which defines a linear transformation over \(\mathbb F_2\) which is the encoding.
Page: 9
Chapter: 1
Section: 2
Variables: \(C\) a linear block code
Notation: \(\mathbf G\)

Name: The syndrome of \(t\)
Definition: The sequence whose \(i\)-th value is 1 iff the \(i\)-th parity bit does not have the expected value, given the input bits.
Page: 10
Chapter: 1
Section: 2
Variables: \(C\) a linear block code,
\(t\) a received sequence of bits

Name: Parity check matrix
Definition: The matrix \([P I]\), with \(P\) the generator matrix without the identity diagonal.
Page: 12
Chapter: 1
Section: 2
Variables: \(C\) a linear block code,
Intuition: The matrix associating a received word to its syndrome vector
Denoted by: \(\mathbf H\)

Name: A maximum-likelihood decoder
Definition: A function which, given a symptome \(\mathbf z\) finds the most probable noise vector \(\mathbf n\) satisfying \(\mathbf{Hn=z}\)
Page: 12
Chapter: 1
Section: 2
Variables: \(C\) a linear block code,