CIS 6930 Powerline Communications Error Handling (c) 2013 Richard Newman Analysis Error Handling - Outline Forward Error Correction Copy codes Block codes Convolutional codes Scrambling Concatenated codes

Turbo-codes Low Density Parity Check (LDPC) Backward Error Correction (BEC) Stop-and-Wait ARQ Conclusions Analysis Measures Nature of errors detected/corrected Efficiency Efficiency: U = Uf Up Ue *

Uf = framing efficiency = D/(D+H) ** where D = Data length and H = Header length Up = protocol utilization Depends on protocol, propagation delay, transmission time Ue = error caused utilization efficiency = 1-P where P = frame error rate Caveats Efficiency formula does not show PHY layer efficiency Variable data rate effects PHY Efficiency * Must consider time spent to deliver frame

Include required gaps/spaces, preamble Also includes PHY layer FEC Variable Data Rate Effects ** Frame header/delimiter may be sent at lower modulation rate Esp. for wireless and PLC Error Correction Strategies Forward Error Correction Include sufficient redundancy in transmitted units that errors can be corrected Simplifies sender protocol used in PHY Backward Error Correction Include sufficient redundancy in transmitted units that errors can be detected Retransmit damaged units

More efficient* used in MAC and above Limitations Hamming Distance of code limits capabilities Always possible to fool receiver * Efficiency depends if have to resend large frame for single error, maybe not so much... General ECC Considerations Systematic vs. non-systematic Systematic = data bits appear in coded stream Non-systematic = no data bits identifiable Hamming Distance H(x,y) = number of bits where x and y differ Code C = {x1, x2, ..., xN} set of valid codewords d = H(C) = min{H(x,y) | x and y are distinct

codewords in C} Maximum detection ability = d-1 Maximum correction ability = (d-1)/2 Error Correction/Detection Theory Code C is subset of n-bit binary words Received word R = T + E, for transmitted word T and error E H(C) determines maximum detection/correction capability Max detection is d-1 Max correction is floor (d-1)/2 If correcting, then won't detect! Can reduce correction to increase detection of uncorrectable errors, but correction + detection < d Efficiency Detection can be done with fixed # parity bits Larger block has less overhead, but is more prone to errors

Correction requires parity bits scale with info bits Economy of scale still exists may be non-linear Forward Error Correction Block vs. continuous Block = set number of information symbols encoded into set number of code symbols Internal fragmentation Need for delimitation Continuous = stream of information symbols encoded into stream of code symbols Memory/constraint length must fill the pipeline Linearity Sum of two code words is a code word Concatenation Combine two codes (inner and outer) to increase correction capabilities Forward Error Correction Efficiency = code rate Rate = k/n for (n,k) code k = information bits

n = total bits t = n-k = redundant bits With continuous codes, need to account for tail - the number of bits in the memory Block Codes Copy codes LRC Hamming codes BCH Reed-Solomon LDPC Copy Codes

Block Codes Simplest code, still useful at times Copy data bits r times to encode Use received copies to vote for input value Can survive a burst error if scrambled LRC Longitudinal Redundancy Check Information bits arranged in p-1 by q-1 matrix Each row has parity bit at the end Each column has parity bit at the bottom n = pq, k = (p-1)(q-1), r = p+q-1 Detects single bit errors

LRC Example 1 0 1 1 0 1 1 0 1 0 1 1 = information bits 1011_ 10111 0 1 1 0 _ -> 01100 1011_ 10111 _____ 0 1 1 0 0 <- LRC ^ VRC 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 = code word LRC Example 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 = sent 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 = error 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 = received 10111 01000X 10111 01100 X errors in LRC and VRC locate bit error Hamming Codes Hamming Codes

perfect 1-bit error correction 2n-1 bits per code word n parity bits, remainder systematic information bits Parity bit i is in position 2i Parity bit i checks even parity of bits in positions with ith bit of location non-zero Hamming Code Example n = 4, length N = 16-1 = 15 bits, k = 11, r = 4 information bits = 10110110101 f edcba987654321 bit positions 1011011_010_1__ info bits in posn ---------------->1 parity bit 3 -------------- ------->0

----- -- -- ------ -- -- parity bit 2 -->0 -- >0 101101110100100 parity bit 1 parity bit 0 code word Hamming Code Example f edcba987654321 bit positions 101101110100100 code word 000001000000000 error 101100110100100 received word ---------------->0

parity bit 3 X ------------- ------->0 ----- -- -- ------ -- -- parity bit 2 -->1 -- >0 parity bit 1 X parity bit 0 Syndrome = 1010 = a = location of error Bit error => invert received bit to correct it BCH Codes Bose, Chaudhuri, Hocquenghem ca. 1960 Easy to decode Syndrome decoding

Easy to implement in hardware Cyclic code Polynomial code over a finite field Reed-Solomon codes a special form of BCH Reed-Solomon Codes Based on oversampled polynomial Redundant samples allow optimal polynomial to be recovered if most samples are good Symbols greater than 1 bit m-bit symbols => limit block size to 2m-1 symbols 2 parity symbols needed to correct each error

One to locate position (or none) One to specify correction to symbol 1 parity symbol needed to correct each erasure Handles small bursts Popular DVDs, CDs, Blu-Ray, DSL, WiMax, DVB, ATSC, Raid-6 Low Density Parity Check Codes Linear code Capacity approaching code Can get near to Shannon limit in symmetric, memoryless channel Uses iterative belief propagation Defined by sparse parity check matrix No encumbering patents Used in DVB-S2 digital TV, ITU-T G.hn, 10GBase-T

Low Density Parity Check Codes Forney Factor Graph representation (fragment) Inputs Variable nodes Constraint nodes Probability values associated with variable nodes used with constraints to update value and confidence in variable nodes iteratively Convolutional Codes May be systematic or not Shift register for information bits Each output bit has one or more taps into shift register Tapped values are XORed to produce output Outputs are sent round robin May puncture output to increase coding rate

May scramble input to spread errors out May puncture (drop out bits) to increase rate Convolutional Codes in + out 1 0 0 1 1 0 1 -> = info bits 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 -> = output --------tail Initialize shift register with 0s, then shift in one bit at a time, then read one bit from each output Convolutional Codes data = 1011001 tail = 00 2 G(x)=x +1 + Input Constraint length m (i.e., amount of memory or size of shift register) m = n+1, where n = degree of G(x)

1 0 1 1 0 0 1 0 0 Parity 0 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0

1 1 0 0 1 1 0 0 1 1 1 1 0 1 Output 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 Decoding Convolutional Codes Maximum Likelihood Decoding

Viterbi Algorithm Trellis decoding Dynamic programming Number of states = 2m, m=constraint length State = contents of shift regisiter Cost = HD for transition based on received bits http://www.cambridge.org/resources/0521882672 /7934_kaeslin_dynpro_new.pdf Shift Register Trellis Graph 000 000 000 000 001 001 001 001 010 010 010 010 011

011 011 011 100 100 100 100 101 101 101 101 110 110 110 110 111 111 111 111

000 Shift register state 0 transition 1 transition ... Trellis edges depend on code 000 000 000 000 001 001 001 001 010 010 010 010 011 011

011 011 100 100 100 100 101 101 101 101 110 110 110 110 111 111 111 111 Start state?

00 transition 01 transition 10 transition 11 transition ... G(x)=x2+x+1 Start state defined by code specification Usually all 0s Trellis Decoding of Convolutional Codes 000 000 000 000 001 001 001 001 010 010 010 010 011

011 011 011 100 100 100 100 101 101 101 101 110 110 110 110 111 111 111 111

Illegal transitions? ... Only two legal transitions 0 or 1 shift in G(x) will determine arc labels depending on state and input shifted in Trellis Decoding of Convolutional Codes 000 000 000 000 001 001 001 001 010 010 010 010 011 011 011

011 100 100 100 100 101 101 101 101 110 110 110 110 111 111 111 111 Transitions at unit cost 00 or 11

01 or 10 G(x)=x2+x+1 Illegal transitions follow same edges, but cost according to errors e.g., if receive 01 or 10 in state 000 then 000 or 100 at cost 1 Trellis Decoding our code 000 000 000 000 001 001 001 001 010 010 010 010 011 011 011

011 100 100 100 100 101 101 101 101 00 transition 01 transition 10 transition 11 transition ... 2 G(x)=x +1 110 110 110 110 111 111

111 111 Illegal transitions follow same edges, but cost according to errors e.g., if receive 01 or 10 in state 000 then 000 or 100 at cost 1 Trellis Decoding our example G(x)=x2+1 000 0 cost 000 2 cost 100 4 cost 010 6 cost 101 1 cost 011 3 cost 101 5 cost

001 infinite cost 000 000 000 000 000 000 000 001 001 001 001 001 001 001 010 010 010

010 010 010 010 011 011 011 011 011 011 011 100 100 100 100 100 100 100 101

101 101 101 101 101 101 110 110 110 110 110 110 110 111 111 111 111 111 111

111 Received: 11 00 11 11 01 01 On each pair of received bits, update minimum cost for each state, preserving path(s) that produce that cost 4 bits later can correct Decoding Convolutional Codes Maximum Likelihood Decoding At any point in received stream, output the stream of input bits most likely to have produced that output (i.e., fewest errors) Viterbi Algorithm Trellis keeps track of state of memory For each possible state, track least cost to get there Accumulate costs cost of state B is minimum over all previous states A of cost of A plus cost to transition to B from A given current input If multiple ways to reach a state, take cheapest one Only have to maintain costs for current state set, then update based on received bits Scrambling

Convolutional codes correct well when errors are sparse Tend to have problems with burst errors Scramble bits after encoding, before decoding Concatenated codes allow errors/resynch Scrambling Shuffle order of bits on the way out/in Interleaver depth = memory required to shuffle E.g., fill block in row order, read out column order Concatenated Codes Can increase correcting power by combining two codes inner and outer

Apply outer first when encoding, last decoding Apply inner last encoding, first decoding RSV Reed-Solomon outer, Viterbi inner Very popular Convolutional inner code corrects sparse errors R-S outer code corrects bursts (n,k) and (n,k) code produce (nn,kk) code Concatenated Codes Outer Coder Inner Coder Scrambler Noise Outer Coder Receiver

Inner Coder Scrambler Channel Sender Turbo Codes Essentially concatenating two convolutional codes (may be the same code) One code operates on straight input Other code operates on delayed and interleaved input Decoding involves iteration between the two codes Can approach Shannon Limit Patents held by French Telecom Recall Error Correction Strategies Forward Error Correction

Include sufficient redundancy in transmitted units that errors can be corrected Simplifies sender protocol used in PHY Backward Error Correction Include sufficient redundancy in transmitted units that errors can be detected Retransmit damaged units More efficient used in MAC and above Limitations Hamming Distance of code limits capabilities Always possible to fool receiver Efficiency of BEC depends on size of frame & FER Backward Error Correction (BEC)

Received data cannot be corrected Include checksum/redundancy check to detect errors (detection is cheap) Retransmit frames that have errors How does sender know which to resend? ACK OK, dont resend NAK Received damaged frame No response time out and resend ACKs Cumulative vs. individual vs. SACK BEC Requirements Sender Must add error detection code to frames Must store frames sent until ACKed

Must know which frames receiver got correctly Must know when to resend frame Must have timer for ARQ Receiver Must check error detection code on frames Must be able to distinguish duplicate frames Must be able to signal sender on state May buffer out-of-order frames Acknowledgements ACK types Individual ACK just the SN indicated

Cumulative ACK indicates next expected unit Beneficial when ACKs are lost - redundancy SACK indicates multiple good/back units Sequence Number (SN) per unit Units may be frames, bytes, cells, etc. SNs eventually wrap around Need to avoid confusion send/receive window Larger SN = more framing overhead Error Detection Parity ARC Arithmetic Redundancy Check

Checksum adds values (with carry) Drop overflow May rotate addends CRC Cyclic Redundancy Check Linear code, generated by polynomial Easy to implement in feedback shift register Cryptographic Hashes MD5, SHA, HMAC Useful for secure integrity checks Stop-and-Wait ARQ One unit sent at a time Wait for response (ACK/NAK)

Units have sequencing information (1 bit) Accept received units in strict sequence Gaps are not allowed Duplicates are discarded One-bit acknowledgement (ACK) Resend unit on time-out or NAK Stop-and-Wait ARQ L/R 2T 1 L = Unit length (bits) R = Transmission rate (bps) T = Propagation delay (sec) Let a = T/(L/R) = propagation delay in frames 2a Cycle time = Tc = 1+2a

Data Tx time = 1 Utilization due to protocol = Up = 1/(1+2a) Stop-and-Wait ARQ Fram e1 Fram e2 Receiver needs way to distinguish duplicate frame from new frame, since ACK may be lost.... Fram e1 X Res e Fram nt e1 Go-Back-N ARQ Transmit units according to send window, k

Units have sequencing information Accept received units in strict sequence Gaps are not allowed Duplicates, out of order units are discarded Cumulative acknowledgement (ACK) Resend un-acked units Includes those received after a lost unit GBN ARQ k 1 2a 2a Cycle time = Tc = 1+2a Data Tx time = k Up = k/(1+2a) if no errors, and k <= 1+2a If errors at probability P, Expect to resend k units per error, so if k <= 1+2a,

Up = k/(2a+1)(1-P-kP) U = k(1-P)/(2a+1)(1-P-kP) Selective Repeat ARQ Transmit units according to transmit window Units have sequencing information Store received units according to sequencing information Gaps are allowed Duplicates are discarded Selective acknowledgement (SACK) Resend un-acked units Selective Repeat ARQ Efficiency is best possible

Only redundancy is sequence info and error detection Never resend units unnecessarily If P = prob(unit is lost), k = Tx window, then Utilization U = (1-P)k/(2a+1) for k <= 1+2a (U = (1-P) if k > 1+2a) Observations w.r.t. PLC Need a variety of techniques to deal with PL channel impairments Modulation and coding used to get near channel capacity means there will be errors Channel changes means there will be too many errors sometimes If raw error rate too low, then get closer!!! Longer frames mean greater error probability

Want to correction unit size to ensure success Observations w.r.t. PLC Different coding levels needed for different PPDU/MPDU parts Frame delimiter needs to be heard by all, so must be very robust Payload can be adapted to highest rate path can handle Coding method needs to deal with impulse noise Want to be selective about what must be resent Cross-layer design issues