Consider a mapping between \(X \in \{0,1\}\), and output \(Y \in \{0,1\}\), with a chance of error of probability \(p\). So we have four outcomes:

Writing this out:

• \(P(y=1|x=0) = p\)
• \(P(y=0|x=1) = p\)
• \(P(y=0|x=0) = 1-p\)
• \(P(y=1|x=1) = 1-p\)

Recall chain rule:

\begin{equation} P(X,Y|A) = P(X|Y,A) P(Y|A) \end{equation}

Consider some input output pair:

\begin{equation} p(y=10 | x = 00) = p(y_1=1 | x_1=0, x_2=0)p(y_2=0| y_1=1, x_1=0, x_2=0) \end{equation}

• Analog vs Digital Signal
• bit (signal processing)
  • Source-Channel Separation Theorem

information

• information source can be modeled as a random variable
• surprise
• information value and entropy
  • joint entropy
    • joint entropy of independent events

Source Coding

• non-singular code
• uniquely decodeable
• Prefix-Free code, which is uniquely decodeable and instantaneously decodable
  • any prefix free code for a source has at least entropy length
  • prefix-free code has the same codeword lengths as any code
• Average Codeword Length
• generating Prefix-Free code with Huffman Coding
  • Huffman Coding is Bounded
• Block Coding
  • Boundedness of Block Coding and why it saves space!
• Diadic Source
• Shannon’s Source-Coding Theorem
  • Entropy Rate of the Source
• Non-IID Sequence Can Have Smaller Entropy (which is why we use Entropy Rate of the Source as the measure of how good a code is)

signal

• sinusoid and Fourier Series
  • Fourier Series as exactly a shifted sum of sinusoids
  • General Fourier Decomposition
• L-periodic functions and triangle wave
• Fourier Series components form a basis
• Bandwidth
  • Finite-Bandwidth Signal
• Discrete Fourier Transform
• Lossless Sampling and nyquist sampling theorem
  • Finite-Bandwidth Signal
  • Baseband Signal and Passband Signal
• Interpolation
  • Zero-Hold Interpolation
  • best: Infinite-Degree Polynomial Interpolation (uses sinc function)
    • Shannon’s Nyquist Theorem

Communication System Design!

• energy of signal
• error-correction code
  • rate (error correction code)
  • repetition code
  • minimum error-correction code length
  • sphere packing bound
  • perfect code: Hamming Code
    • Hamming Code Rate
  • Hadamard Code
• Convolutional Code
  • Viterbi Decoding
• Bit Error Rate

Key Sequence

New Definitions

• division + division algorithm
• greatest common divisor
• prime
• Euclidean Algorithm

Results and Their Proofs

• principle of induction
• primes
  • there are infinitely many primes
• division and greatest common divisor
  • division algorithm
  • properties of the gcd
• Euclidean Algorithm and some euclid lemma linked below in fundamental theorem of arithmetic

Questions for Jana

• Why does something being prime require that \(p>1\). that is, why is \(1\) not defined as prime?

Interesting Factoids