Syllabus told by sir: Channel models / capacity, polynomials, cyclic codes (systematic + non-systematic), groups and fields. When class asked “only ppts 2, 3, 8?”, he said yes.
| Topic | Read this |
|---|---|
| Channel models + capacity | Information_Theory_and_Coding (1).pdf slides 49–80 (Unit-II) |
| Groups + Fields + Polynomials | LECTURE SLIDE 2.pdf (all 42 slides) |
| Extended GF(2m), minimal poly, vector space | LECTURE SLIDE 3.pdf (14 slides) |
| Systematic vs non-systematic idea + trellis/Viterbi | LECTURE SLIDE 8.pdf (convolutional example) |
c=m·g vs c=x^{n-k}m + rem.Course Plan mapping: Lectures 9–15 = CO3 channels, Lectures 16–25 = CO4 Galois/poly/linear block, Lectures 26–40 = cyclic + convolutional + Viterbi. Quiz 2 sits at the 9–25 boundary, hence this mix.
Start here if you attended zero classes. English unless marked 🇮🇳 Hindi. Previous midsem guide videos for Unit-II still apply; below adds Quiz-2-specific ones.
Channels: ▶ DMC / channel matrix ▶ BSC capacity 🇮🇳 ▶ BEC capacity 🇮🇳 ▶ Shannon-Hartley numericals ▶ C=max I(X;Y) ▶ Noisy coding theorem
Fields + polynomials: ▶ GF(2) groups/fields (search: Mahesh Huddar) ▶ GF(2) polynomial division
Cyclic (prof’s hint): ▶ Cyclic non-systematic with example ▶ Systematic cyclic encoding (search NPTEL)
Convolutional (Slide 8): ▶ Trellis + Viterbi
Also: Prof. Ranjan Bose NPTEL course 117102062 (IIT Delhi) on Ansys/NPTEL portal covers linear block + Galois + cyclic + division algorithm — same as textbook T1. Duke ECE590 cyclic slides (pfister.ee.duke.edu) give the cleanest systematic proof: p = −xn−km mod g.
| Book | Open this for Quiz 2 |
|---|---|
| Bose 2nd ed | Ch.2.2–2.7 channels + BSC/BEC + Hartley; Ch.4.2–4.4 poly division + cyclic c=m·g vs remainder-append; Ch.5.2–5.4 GF/minimal poly; Ch.6 trellis/Viterbi |
| Satyanarayana | Ch.3 DMC matrix, Ch.4 Gaussian/Hartley, Ch.6 block-code algebra + GF tables, Ch.7 cyclic systematic + syndrome, Ch.8 convolutional |
| Lin & Costello 2nd ed | Ch.1 BSC/AWGN models; Ch.2 groups/rings/fields + GF(2m) + minimal poly; Ch.5 cyclic encode (5.4–5.6) + syndrome; Ch.11–12 convolutional + Viterbi |
| Wells | Ch.2 DMC + symmetric C=log|Y|−H(row) + BSC/BEC; Ch.4–5 binary fields + poly mod xn+1 + systematic encoder + Meggitt; Ch.6 trellis/Viterbi/puncturing |
If short on time: Bose Ch.2 + Ch.4.4 + Lin Ch.2.5–2.7 + Ch.5.4 covers 90% of Quiz 2.
Matrix row = “if I send this, what can come out?” Rows sum to 1. P(Y)=P(X)·M. Joint = scale each row by P(xi). Then H(Y|X) = average entropy of rows, I=H(Y)−H(Y|X).
BSC flips with prob ε. BEC erases with prob γ (never flips). So BEC hurts less: C=1−γ vs BSC 1−Hb(ε). Ex: ε=0.1 → Hb≈0.469 → C≈0.531. γ=0.2 → C=0.8. Hartley: B=4kHz, 10dB (S/N=10) → 4000·log2(11)≈13.8kbps. Remember 1023→1024=210 trick for clean logs.
Group: you can combine and undo, stay inside. Clock arithmetic mod-5 is a group. Field: you can also multiply/divide. GF(2)={0,1} with XOR/AND is the field all coding lives in.
Characteristic is prime. aq−1=1. Primitive element makes all non-zero by its powers. Ex GF(7): 3 is primitive (3,2,6,4,5,1), 4 has order 3. GF(4) is NOT integers mod-4; built from X2+X+1=0 → α2=1+α.
Bits = coefficients. 1+1=0 so add = XOR. (X+1)2=X2+1 (middle term vanishes). Divide: f=q·g+r, deg r < deg g. Slide-2 drill: (X6+X5+X4+X+1)/(X3+X+1) → q=X3+X2, r=X2+X+1. Root test: f(1)=0 ⇒ (X+1) factor. Degree 2–3: check f(0),f(1) enough. Degree ≥4: also rule out product of irreducible quadratics, e.g. (X2+X+1)2=X4+X2+1 has no root but is reducible.
(7,4) demo, g=X3+X+1, m=1101 (m=X3+X2+1):
Non-sys: m·g = X6+X5+X4+X3+X2+X+1 → 1111111.
Sys: X3m=X6+X5+X3 ÷ g → r=1 → c=X6+X5+X3+1 → 1101001 (message 1101 readable). Both satisfy c mod g=0.
Checklist: deg g=n−k, deg m<k, g | Xn+1, h=(Xn+1)/g, syndrome s=r mod g.
Block = combinational (no memory). Convolutional = sequential (memory m, 2m states). Slide-8 code: rate ½, g0=1011, g1=1111, non-systematic feedforward. u=(10111) → v=(11,01,00,01,01,01,00,11). Poly form g0(D)=1+D2+D3. Viterbi = keep best path per state by Hamming distance (add-compare-select), traceback at end. Rate k/n, states 2m.
Do in order. Clean numbers chosen so logs collapse (½,¼,⅛, 1023/1024). If intermediate looks ugly, re-read the question.
X∈{0,1}, PX=[½,½], M=[[¾,¼],[¼,¾]]. PY=[½,½]. Joint [[⅜,⅛],[⅛,⅜]]. H(X)=1, H(Y)=1. Each row Hb(¼)≈0.811. H(Y|X)≈0.811, H(X,Y)≈1.811, I≈0.189 bits.
PX=[¼,¾], M=[[1,0],[½,½]]. Joint [[¼,0],[⅜,⅜]]. PY=[⅝,⅜]. H(X)≈0.811, H(Y)≈0.954, H(Y|X)=¾·1=0.75, I≈0.204, H(X,Y)≈1.561.
C=1−Hb(¼)=1−0.811=0.189 bits/use.
Hb(⅛)≈0.544 → C≈0.456 bits/use.
C=1−¼=¾. 1000 uses → 750 info bits max.
Slin=100.477≈3. C=4000·log2(4)=8000 bps.
Slin=1000. C=106·log2(1001)≈9.97 Mbps ≈10 Mbps via 1024≈210.
Add: closed, identity 0, self-inverse → yes Abelian. Multiply: 0 has no inverse → not a group. Non-zero {1} is a group + distributive → GF(2) is a field.
Add/mul mod-3. 1−1=1, 2−1=2 (2·2=4≡1). 2x=2 → x=1.
1011⊕0111=1100 → x³+x².
=x³+x²+x+1 (1111).
q=x²+1, r=x². Verify (x²+1)(x³+x+1)+x²=x⁵+x+1. g(0)=1,g(1)=1 → no linear factor, deg 3 → irreducible.
m=X³+X²+1, g=X³+X+1. m·g=X⁶+X⁵+X⁴+X³+X²+X+1 → 1111111. Divisible by g by construction.
X³m=X⁶+X⁵+X³ ÷ g → r=1. c=X⁶+X⁵+X³+1 → 1101001. Check c÷g remainder 0. Compare with Q13: different codewords, both valid; systematic shows message.
k=1,n=2,m=2 → R=½, 4 states. Branch metric=Hamming(y,label). ACS: add, compare two merging paths, keep smaller survivor. Ex from 00: labels 00/11, y=00 → metrics 0 vs 2 → keep input-0 path.