Loading...

Atlanta RF Services, Software & Designs

Presentation Content Link Budget Analysis: Error Control & Detection 1. Cause of Performance Degradation. 2. Sources of Errors. 3. Overview of Error Detection. 4. Error Correction: Basic Principles.

5. Error Control Techniques. 6. ARQ: Automatic Repeat reQuest. 7. Forward Error Correction Codes. 8. Classification of FEC Codes. 9. Applications of Channel Coding. 10.Benefits of FEC. 11.Channel FEC Coding Techniques. 12.Channel Coding Gain.

13. Linear Block Error Correcting Codes. 14. Cyclic Block Error Codes. 15. BCH Error Correcting Codes. 16.Reed-Solomon Error Correcting Codes 17. Interleaving Error Correction Codes. 18. Convolutional Error Correcting Codes. 19.Low Density Parity Check Codes. 20.Concatenated Codes. 21.Turbo Convolutional Codes (TCC). 22. Turbo Product Codes (TPC). 23. Design Trade-offs with FEC.

Refer to background material in Atlanta RF’s presentations titled: 1. ‘Link Budget – Getting Started’ and 2. ‘Link Budget: Digital Modulation Part 1’ (Overview & M-ASK). 3. ‘Link Budget: Digital Modulation Part 2’ (M-FSK). 4. ‘Link Budget: Digital Modulation Part 3’ (M-PSK & QAM). which can be downloaded from our website: www.AtlantaRF.com. Aug-2013

www.AtlantaRF.com

2

Atlanta RF Services, Software & Designs

Data Transmission: Errors are Everywhere Link Budget Analysis: Error Control & Detection 1. Many communication channels suffer from noise, interference or distortion due to hardware imperfections, or physical limitations. 2. Channel coding deals with error control techniques. If the data at the output of a communications system has errors that are too frequent for the desired use, the errors can often be reduced by the use of a number of error control techniques. 3. The goal of error control coding is to encode digital information in such a way that, even if the channel (or storage medium) introduces errors, the receiver can correct the errors and recover the original transmitted information.

Atlanta RF Aug-2013

www.AtlantaRF.com

3

Services, Software & Designs

Cause of Performance Degradation Link Budget Analysis: Error Control & Detection 1. Receive Signal loss (Eb term): A. The receive signal looses signal strength due to: 1) Distance between Transmitter’s antenna and the Receiver’s antennas, 2) Absorption of the Tx signal, 3) Scattering of the Tx signal, 4) Reflection of the Tx signal, 5) Refraction of the Tx signal, 6) Antenna pointing errors, etc.

2. Inter-Symbol Interference (N0 term): A. The receive signal is interfered with by near-by transmitted signals, due primarily to frequency-dependent effects (in the channel or by amplifiers).

3. Noise and interference (N0 term): A. InterModulation distortion: IMD. B. Interfering signals (co-channel & adjacent channel interference). C. Amplifier noise sources (thermal noise, shot noise, flicker noise). D. Atmospheric noise and galactic noise sources.

Recall: The energy per bit (Eb) is related to the received signal (S = Pr) as:

Eb S Bw Rbits , dB No N Aug-2013

www.AtlantaRF.com

4

Atlanta RF Services, Software & Designs

Example: Receive Signal Loss in 16-QAM Viewed in QAM’s Phase State Constellation Diagram Receive Signal Loss: 1. Low signal-to-noise ratio (S/N) leads to discrimination errors. 2. Signal loss is due to absorption, scattering, reflection, refraction, pointing, etc. Bit errors in red Q

Q

Q

I

16-QAM with Eb/N0 = 11 dB

I

16-QAM with Eb/N0 = 6 dB

I

16-QAM with Eb/N0 = 2 dB

Recall: The energy per bit (Eb) is related to the received signal (S = Pr) as:

Aug-2013

www.AtlantaRF.com

Eb S Bw Rbits , dB No N

Atlanta RF

5

Services, Software & Designs

Sources of Errors Link Budget Analysis: Error Control & Detection Volts

Time

White Noise: N kTs Bw , watts 1. 2. 3. 4.

Also known as thermal or Gaussian noise. Relatively constant . Can be reduced by filters. If white noise gets too strong, can completely disrupt signal.

Volts

Time

Volts

Time

Volts

Impulse Noise:

Time

1. One of the most disruptive forms of noise caused by random spikes of power that produce irregular pulses or noise spikes of short duration, which can destroy one or more bits of information. 2. Impulse noise is the primary source of bit-errors in digital data communication: burst errors. 3. Caused by switching, manual interruptions, ignition noise, electrical sparks and lightning.

Atlanta RF

Time

Aug-2013

www.AtlantaRF.com

6

Services, Software & Designs

Sources of Errors Link Budget Analysis: Error Control & Detection

Phase Jitter:

Volts

1. The result of small timing irregularities during transmission of digital signals. 2. Occurs when a digital signal is repeated over and over. 3. If serious enough, jitter forces systems to slow down their transmission. 4. Steps can be taken to reduce jitter.

Time

Time

Echo: 1. The reflective feedback of a transmitted signal as the signal moves through a medium. 2. Most often occurs on coaxial cable. 3. If echo bad enough, it could interfere with the original signal. 4. Relatively constant. 5. Can be significantly reduced.

Atlanta RF Aug-2013

www.AtlantaRF.com

7

Services, Software & Designs

QAM or QPSK Impairments/Errors When viewed in Phase State Constellation Diagram Q 01

Q 00

01

Quadrature (imaginary)

I 10

11

I 10

00

01

Gaussian Noise

Q

11

10

00

11

Amplitude Distortion

In phase (real)

Q 01

00

01

Input

Input Message Signal (Ideal)

00

I

I 10

10

11

Phase Distortion Aug-2013

www.AtlantaRF.com

11

Intermodulation IMD Distortion

Atlanta RF

8

Services, Software & Designs

64-QAM Digital Modulation Errors When viewed in QAM’s Phase State Constellation Diagram

Atlanta RF Aug-2013

www.AtlantaRF.com

9

Services, Software & Designs

Summary: Sources of Errors and Prevention Link Budget Analysis: Error Control & Detection

Source of error

Cause

Prevention Technique

White noise

Movement of electrons (thermal energy).

Increase signal strength (increase SNR).

Impulse noise

Sudden increases in noise spikes (e.g., lightning, power surges, etc).

Shield or move the wires, special filters and DSP.

Cross-talk

Multiplexer guard bands are too small or wires too close together (coupling).

Increase the guard bands, or move or shield the wires/cable.

Echo

Poor connections (causing signal to be reflected back to the source).

Proper termination of cables; Fix connections, or tune eqpmt.

Attenuation

Gradual decrease in signal over distance (weakening of a transmitted signal).

Use digital repeaters or analog amplifiers to increase signal’s RF power level.

Intermodulation noise

Signals from several circuits combine.

Move or shield the wires.

Phase Jitter

Analog signals change phase.

Better circuits; Fewer repeaters

Atlanta RF Aug-2013

www.AtlantaRF.com

10

Services, Software & Designs

Basic Single-Link Digital Communications System Link Budget Analysis: Error Control & Detection Source bits

Digital Input Analog In:

Data Source

Anti-alias lowpass filter

Nyquist sampling

Source Encoder

Transmit

Channel Encoder

A/D

➢ Audio ➢ Video

Channel bits

• FEC • ARQ • Block • Convolution

Bandpass Modulator • ASK • FSK • PSK • Binary • M’ary

Pulse shaping filter • ISI

Baseband User

Source Decoder

Analog Out: ➢ Audio ➢ Video

Digital Output

D/A Low pass filter

Quantization noise

Source bits

Multiple Access • FDMA • TDMA • CDMA

Channel Rx

Receive

Regenerate

Demodulator & Detect

• Matched filter • FEC • Envelope • Decision threshold • Coherent • ARQ • Timing recovery • Block • Carrier recovery • Convolution

1. Source transmits signals (e.g. speech). 2. Source encoder: Samples, quantizes and compresses the analog signal. 3. Channel encoder: Adds redundancy to enable error detection or correction @ Rx. 4. Modulator: Maps discrete symbols onto analog waveform and moves it into the transmission frequency band.

Tx

Passband

Channel bits

Channel Decoder

Transmit Channel Bandpass Filter

Multiple Access Receive Channel Bandpass Filter

5. Physical channel represents transmission medium: Multipath propagation, time varying fading, noise, etc. 6. Demodulator: Moves signal back into baseband and performs lowpass filtering, sampling, quantization. 7. Channel decoder: Estimation of information data sequence from code sequence Error correction. 8. Source decoder: Reconstruction of analog signal.

Atlanta RF Aug-2013

www.AtlantaRF.com

11

Services, Software & Designs

Overview of Error Detection Link Budget Analysis: Error Control & Detection 1. When high-speed binary data is transmitted over a communication link, errors will occur; whether the communication link is twisted-pair wires, coaxial cable, fiber optic cable, magnetic tape or radio/air link. 2. These errors produce changes in the data’s binary bit pattern caused by interference, fading, distortions, noise, or equipment malfunctions, which cause incorrect data to be received. 3. The number of bit errors that occur for a given number of bits transmitted is referred to as the bit error rate (BER). 4. The process of error detection and correction involves adding extra bits to the message data characters at the transmitter (redundant bits) to permit error detection or correction at the receiver. This process is generally referred to as channel encoding. 5. The topic of coding deals with methods of trying to get transmission channels to operate at their maximum data transmission capacity. More…….

Atlanta RF Aug-2013

www.AtlantaRF.com

12

Services, Software & Designs

Overview of Error Detection….Continued Link Budget Analysis: Error Control & Detection 6. The message data to be transmitted is processed in a way that creates the extra bits and adds them to the original message data. At the receiver, these extra bits help identify any errors that occur in transmission caused by noise or other channel effects. Think: Matrix multiplication. 7. A key point about channel encoding is that it takes more time to transmit the message data because of the extra bits. These extra bits are called overhead in that they extend the time of transmission. 8. Channel encoding methods fall into to two separate categories, error detection codes and error correction codes. 9. A number of efficient error-correction schemes have been devised to complement error-detection methods. 10.The process of detecting and correcting errors at the receiver so that retransmission is not necessary is called forward error correction (FEC). There are two basic types of FEC: block codes and convolutional codes.

Atlanta RF Aug-2013

www.AtlantaRF.com

13

Services, Software & Designs

Error Correction: Basic Principle Link Budget Analysis: Error Control & Detection 1. All error correcting codes are based on the same basic principle: redundancy is added to information in order to correct any errors. In a basic (and practical) form, redundant symbols are appended to information symbols to obtain a coded sequence or codeword. 2. Code rate: Rc equals the ratio of length of the uncoded sequence: k to the coded sequence: n, and describes the required expansion of the signal’s bandwidth. 3. Basic Idea: Add extra bits to a block of information data bits. A. Information data block size: k bits long. B. Error detection redundancy: r = n - k more bits added to block size. 1) The added bits are algebraically related to the buffered bits, based on some algorithm for creating those extra redundant bits.

C. Results in a frame (data link layer packets are called “frames”) of length: n bits.

Atlanta RF Aug-2013

www.AtlantaRF.com

14

Services, Software & Designs

Types of Error Coding in Telecommunications Link Budget Analysis: Error Control & Detection Taxonomy of coding in telecommunications

Automatic repeat request (ARQ) coding to correct errors by using a feedback channel Aug-2013

www.AtlantaRF.com

Atlanta RF 15

Services, Software & Designs

Error Control Techniques Channel Coding in Digital Communication Systems Three approaches can be used to cope with data transmission errors: 1. Automatic Repeat reQuest (ARQ): Error detection A. When a receiver circuit detects errors in a block of data, it requests that the block be retransmitted. The receiver sends a feedback to the transmitter: Error is detected (NACK: Not-Acknowledgement) in the received packet, then retransmit that data block, or if no errors detected (ACK: Acknowledgement), don’t resend. B. The transmitter retransmits the previously sent packet if it receives a NACK. C. Uses extra/redundant bits merely for error detection. D. Full-duplex (two-way) connection between the Transmitter and the Receiver. E. Result: Constant reliability, but varying data rate throughput due to retransmit.

2. Forward Error Correction (FEC): Error detection and correction.

A. The transmitter’s encoder adds extra/redundant bits to a block of message data bits to form a codeword, so the receiver can both detect errors and automatically correct errors incurred during transmission, without retransmission of the data. B. Simplex (one-way) connection between the Transmitter and the Receiver. C. Result: Varying reliability, but constant data rate throughput.

3. Hybrid ARQ (ARQ+FEC): Error detection and correction. A. Full-duplex connection required between the Transmitter and the Receiver. B. Uses error detection and correction codes.

4. In general, wire-line communications (more reliable) adopts ARQ scheme, while wireless communications (relatively less reliable) adopts FEC scheme.

Atlanta RF Aug-2013

www.AtlantaRF.com

16

Services, Software & Designs

Automatic Repeat reQuest (ARQ) or: Automatic Retransmisson Query: ARQ 1. Automatic Repeat Request (ARQ) is a communication protocol where the receiving device detects errors and requests retransmissions. As such, ARQ requires a feedback channel between the Receiver (Rx) and the Transmitter (Tx). 2. After each codeword, the Receiver sends back a positive (ACK) or negative (NAK) acknowledgement to the Transmitter. When the Receiver detects an error in a packet, it automatically requests the Transmitter to resend the packet. This process is repeated until the packet is error free, or the error continues beyond a predetermined number of retransmission events transmission delays/latency. 3. Three types of Automatic Repeat reQuest: Return an error message to the Tx. A. Stop-and-wait ARQ: 1) The Receiver waits for an acknowledgement (ACK) of each transmission before transmitting the next data packet/frame.

B. Continuous ARQ with pull back: Go-Back-’N’ ARQ.

1) Both the Transmitter and Receiver transmit continuously. 2) In case of NAK (negative Ack), the Transmitter will retransmit the Nth error packet and retransmit all the subsequent data packets/frames.

C. Continuous ARQ with selective repeat: Selective Repeat ARQ 1) In case of NAK, the Transmitter will only retransmit that Nth error data packet. 2) More complicated operation at the Receiver (re-order data packets, memory).

4. Error correction in ARQ is a little simpler than FEC (just re-transmit), but requires more hardware and requires a feedback channel. ARQ is seldom used in speech communication. Also called: Backward Error Correction.

Atlanta RF

Aug-2013

www.AtlantaRF.com

17

Services, Software & Designs

Types of Forward Error Control Codes Channel Coding Major categories of Error Detection and Error Correction Codes: 1. Error Detection Codes: A. Parity Check codes. B. ARC: Arithmetic Redundancy Check codes. C. CRC: Cyclic Redundancy Check codes.

2. Block Error Correction Codes: A. Hamming linear block error correcting codes. B. BCH (Bose-Chaudhuri-Hocquenghem) cyclic block codes. C. Reed-Solomon cyclic block codes. D. Turbo Product Codes (TCP).

3. Convolutional Error Correction Code: A. Tradition, Viterbi Decoding. B. Turbo Convolutional Code (TCC). C. Low Density Parity Check Code.

4. Concatenated Error Correction Codes: Inner/Outer codes. A. Reed-Solomon Error Correction Codes/ Viterbi algorithm.

Atlanta RF Aug-2013

www.AtlantaRF.com

18

Services, Software & Designs

Classification of FEC Codes Link Budget Analysis: Error Control & Detection Forward Error Correction Codes

Convolutional (Trellis) Codes

Block Codes

Non-Binary Block Codes

Reed-Solomon Codes A. Systematic B. Non-Systematic

Binary Block Codes

Non-Binary Convolutional Codes

Hamming Codes BCH Codes

Binary Convolutional Codes

Systematic (Turbo Codes)

Non-Systematic (Viterbi Algorithm)

Algebraic coding & decoding

Atlanta RF

FEC: Forward Error Correction Aug-2013

www.AtlantaRF.com

19

Services, Software & Designs

Applications of Channel Coding Importance of channel coding increased with digital communications 1. First use for deep space communications in planetary probes: A. AWGN channel, no bandwidth restrictions, only few receivers (costs negligible). Early Mariner probes, 1962-1967 (Mars, Venus): No error correction codes used. B. Later Mariner and Viking probes, 1969-1976 (Mars, Venus): Linear block codes,Examples: Viking (Mars), Voyager (Jupiter, Saturn), Galileo (Jupiter), ... C. Convolutional codes with Viterbi decoding: Voyager (1977) forward, Cassini, Mars Exploration Rover, …

2. Digital mass storage: A. Compact Disc (CD), Digital Versatile Disc (DVD), Digital Audio Tapes (DAT), hard disk, …

3. Digital wireless communications: A. GSM, UMTS, Long Term Evolution (LTE), WLAN (Hiperlan, IEEE 802.11), ...

4. Digital wired communications: A. Modem transmission (V.32/V.90 use trellis codes), Integrated Services Digital Network (ISDN), Digital Subscriber Line (DSL), …

5. Digital Audio Broadcasting (DAB), Digital Video Broadcasting (DVB). 6. Computer buses, Memory subsystems, Digital broadcasting. Coding can only be used in digital communication systems.

Atlanta RF Aug-2013

www.AtlantaRF.com

20

Services, Software & Designs

Benefits of Forward Error Correction For a Digital Communication System 1. Advances in FEC can offer an improvement of 3dB to 5dB in system performance. Especially dramatic improvement against fading channels. 2. Designers can choose between levels of improved data reliability, reduced systems costs or increases in range. An extra 3 dB of Coding Gain can: A. Reduce the required frequency bandwidth by 50% (OPEX), or B. Increase data throughput by a factor of 2 (OPEX), or C. Reduce antenna size by 30% (CAPEX), or OPEX: Operational Expenditure ($$) D. Reduced ground G/T (CAPEX), or CAPEX: Capital Expenditure ($$) E. Increase range/distance by 40% or reduce the transmitter’s RF power by a factor of 2 (CAPEX), or F. Provides more link margin during off-axis operation (Higher Service Level). G. Access by more users to the same radio frequency in a multi-access communication system can be ensured by the use of error control technique. H. Jamming margin in a spread spectrum communication system can be effectively increased by using suitable error control technique.

3. The Cost ? A. Increased bit overhead (line rate), time delay, and processing complexity.

Atlanta RF Aug-2013

www.AtlantaRF.com

21

Services, Software & Designs

Channel FEC Coding Techniques Link Budget Analysis: Error Control & Detection 1. Forward Error Correction (FEC) coding techniques are classified as either block codes or convolutional codes. The classification depends on the presence or absence of memory. 2. A block code has no memory, since it collects and therefore isolates kbits in a buffer prior to processing: A. There is no retention within the encoding system of information related to the previous samples points memoryless. B. Each output codeword of an (n,k) block code depends only on the current buffer.

3. A convolutional coder may process one or more samples during an encoding cycle: A. The number of sample points collected prior to processing is far less than required for a block code. The delay through the encoder is therefore far less. B. The encoder acts on the serial bit stream as it enters the transmitter. C. Each bit in the output stream is not only dependent on the current bit, but also on those processed previously. This implies a form of memory. D. Its performance is less sensitive to Signal-to-Noise Ratio variations than that of block codes. In situations of limited power, where Signal-to-Noise Ratios would be a concern, the preferred method for achieving FEC is: Convolutional codes.

Atlanta RF Aug-2013

www.AtlantaRF.com

22

Services, Software & Designs

Channel Coding Gain Link Budget Analysis: Error Control & Detection The coding gain produced by an error correcting code is defined as the reduction of Eb/N0 (in dB) that is needed to obtain the same error rate. Channel coding allows the use of lower signal power (smaller Eb/N0) to achieve the same error rate (BER) we would have had without using correction bits, since errors can be corrected.

Bit Error Rate: BER

A. Example: For a BER of 10-6, (Eb/No)c= 11 dB PB is needed for the ½ rate code, as compared to (Eb/No)u= 13.77 dB without the coding. This is a coding gain: G = 2.77 dB. B. Probability of an error in decoded data block is lower with FEC than without it. C. Equivalent to an increase in Signal-to-Noise Ratio (SNR). D. Improved performance for a given SNR, or same BER performance for lower SNR.

Eb Eb [dB] [dB] G [dB] N0 u N 0 c Aug-2013

www.AtlantaRF.com

Coding Gain at BER value.

Coded A F C

B

D E

Uncoded

Eb / N 0 (dB)

Atlanta RF 23

Services, Software & Designs

Linear Block Error Correction Codes: Overview Link Budget Analysis: Error Control & Detection 1. Block Codes are generally the simplest types of error correction codes. 2. Examples of popular Block error correction codes: A. B. C. D.

Repetition Codes. E. Golay Codes. Hamming Codes. F. Turbo Product Codes. Reed-Solomon Codes. G. Low Density Parity Check (LDPC) Codes. BCH Codes: Bose-Chaudhuri-Hocquenghem Codes.

3. One of the famous classes of block codes is the Hamming (7, 4) Code. This code is capable of correcting 1 bit of error in each block of 4 bits of data. 4. Essentially, all iteratively-decoded codes are block error correction codes. 5. Key property: The sum of any two codewords is also a codeword, which is a necessary and sufficient for the code to be linear. Bit Rate Rb

Data block

Channel Data Rate R0

Channel encoder

Codeword

k information bits;

n Rb k

n bits;

2n distinct codewords

2k distinct messages

Atlanta RF Aug-2013

www.AtlantaRF.com

24

Services, Software & Designs

Linear Block Error Correction Codes Principle of Operation 1. In block codes, the input data stream is partitioned/divided into small blocks of information bits: k (dataword) . Several redundancy bits: r (called ‘parity bits’ or ‘check bits’) are added to each dataword block, which computes a unique larger block of total length: n = k + r coded bits (n > k), called a ‘codeword’ (a code vector) via a linear transformation, which are modulated and transmitted over a transmission channel memoryless. The reverse procedure is done at the receiver, where the Decoder looks for a codeword closest to the received vector (= code vector + error vector). 2. The parity bits: r carry no extra information (they are redundant) but help to detect and/or correct raw bit errors at the receiver. 3. The error correcting code is called a: (n, k) linear block code. 4. With a (n, k) code, there are 2k valid codewords out of a possible 2n codewords. 5. The code rate: Rc defines the ratio of the number of bits in the original data block: k to the transmitted data block: n , or Code Rate = Rc = k/n . 6. Example: A simple repetition code, repeating each symbol 3 times (input k : ‘x’, output n : ‘xxx’) has a code rate: Rc = k/n = 1/3.

Atlanta RF

Aug-2013

www.AtlantaRF.com

25

Services, Software & Designs

Hamming Error Correction Codes Link Budget Analysis: Error Control & Detection 1. Hamming* codes are a subclass of linear block codes and belong to the category of perfect codes (‘perfect’ for 1-bit error correction). 2. Hamming codes are expressed as a function of a single integer: m.

Code length :

m2

n 2m 1

Richard W. Hamming (1915- 1998)

Number of informatio n bits : k 2 m m 1 Number of parity bits : n-k m Error correction capability : t 1 3. Popular Hamming code: (4,7) with 7-bit codewords (k = 4 information bits & m = 3 redundant bits) which detects all one- and two -bit errors and corrects all 1-bit errors (n = 7). Code efficiency: Rc = 4/7 = 57%. * Hamming, Richard W. , "Error detecting and error correcting codes", Bell System Technical Journal , Volume 29, Number 2, April 1950, pages 147–160.

Atlanta RF

Aug-2013

www.AtlantaRF.com

26

Services, Software & Designs

Example: Hamming Code impact on BER For QPSK & 8PSK Modulation

PB 8PSK

QPSK

Atlanta RF

Eb / N 0 [dB] Aug-2013

www.AtlantaRF.com

27

Services, Software & Designs

Cyclic Block Error Codes: Overview Link Budget Analysis: Error Control & Detection 1. Cyclic codes are an important subclass of linear block codes. A. BCH and Reed-Solomon codes are cyclic codes. B. First published by Eugene Prange* in 1957.

2. A linear (n,k) code is called a cyclic block code if all cyclic shifts of a codeword are also codewords. 3. Cyclic block codes are of interest and importance in error detection and error correction because: A. They posses rich inherent algebraic structure that can be utilized in a variety of practical methods for decoding them. B. They have extremely concise specifications. C. Encoding and computation can be easily performed by using simple shift registers with feedback connections (or linear sequential circuits). Hence, relatively long block codes can be implemented with reasonable complexity.

* E. Prange , Cyclic error-correcting codes in two symbols, Air Force Cambridge Research Center, Cambridge, MA (1957), pages 57-103. Aug-2013

www.AtlantaRF.com

28

Atlanta RF Services, Software & Designs

Cyclic Redundancy Check (CRC) Codes Overview 1. Cyclic Redundancy Check, also known as a polynomial code, is a mathematical technique for detecting errors in digital data, but not for making corrections when errors are detected. It is used primarily in synchronous data transmission. Invented by W. Wesley Peterson, and published* in 1961. 2. In the CRC method, a certain number of check bits, often called a checksum, are appended to the message being transmitted. The receiver can determine whether or not the check bits agree with the data, to ascertain with a certain degree of probability whether or not an error occurred in transmission. If an error occurred, the receiver sends a “negative acknowledgement” (NAK) back to the sender, requesting that the message be retransmitted: ARQ. 3. When this polynomial code method is employed, the sender and receiver must agree upon a generator polynomial: G(x), in advance. 4. CRC codes have considerable burst-error detection capability and effectively catches 99.9% or more of transmission errors. *Peterson, W. W. and Brown, D.T. “Cyclic Codes for Error Detection.” Proceedings of the IRE, January 1961, pages 228–235. Aug-2013

www.AtlantaRF.com

29

Atlanta RF Services, Software & Designs

Cyclic Redundancy Check (CRC) Principle of Operation 1. CRC error detection method treats packet of data to be transmitted CRC Code Applias a large polynomial. Name r Generator Polynomial: G(x) cation 2. Transmitter processing: CRC-4 4 x4 + x + 1 ITU-G.704 A. Using polynomial arithmetic, CRC-8 8 x8 + x2 + x + 1 divides polynomial by a given CRC-10 10 x10 + x9 + x5 + x4 + x + 1 ‘generating’ polynomial. CRC-12 12 x12 + x11 + x3 + x2 + x + 1 B. Quotient is discarded. CRC-16 16 x16 + x15 +x2 + 1 C. Remainder error control bits: r CRC-CCITT 16 x16 + x12 + x5 + 1 are “attached” to the end of x32 + x26 + x23 + x22 + x16 + x12 + x11 CRC-32 32 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 the data message. D. Data message (with the remainder) is transmitted to the receiver.

ATM header ATM AAL Telecom Phones Bluetooth LANs

3. Receiver processing:

A. Divides the data message and remainder by the same ‘generating’ polynomial. B. If a remainder ‘not equal to zero’ results Error during transmission. C. If a remainder of zero results No error during transmission.

4. Example: A 16-bit checksum (CRC-16) catches all single and double errors, all errors with an odd number of bits, all burst errors of length 16 or less, 99.997% of 17-bit error bursts, and 99.998% of 18-bit and longer bursts.

Atlanta RF

Aug-2013

www.AtlantaRF.com

30

Services, Software & Designs

BCH Error Correcting Codes: Overview Link Budget Analysis: Error Control & Detection 1. Bose, Ray-Chaudhuri, Hocquenghem* (BCH) error correcting codes A. Multiple error correcting ability. B. Ease of encoding and decoding.

2. Most powerful cyclic code: A. For any positive integer m and t <2(m-1) , there exists a t-error correcting (n,k) code with n = 2m-1 and n - k <= m t.

3. Industry standards: A. (511, 493) BCH code in ITU-T. Rec. H.261 “video codec for audiovisual service at kbit/s” a video coding a standard used for video conferencing and video phone. B. (40, 32) BCH code in ATM (Asynchronous Transfer Mode).

* Bose, R. C. ; Ray-Chaudhuri, D. K., (March 1960), "On A Class of Error Correcting Binary Group Codes", Information and Control, Volume 3 (1): pages 68–79.

Atlanta RF

Aug-2013

www.AtlantaRF.com

31

Services, Software & Designs

Bit error rates for BCH codes (Length n = 255) Modulation: Binary Phase Shift Keying (BPSK)

At first, the BER decreases with decreasing Code Rate: Rc. For t > 25, the performance worsens BCH codes are asymptotically bad.

Atlanta RF

Aug-2013

www.AtlantaRF.com

32

Services, Software & Designs

Bit error rates for BCH codes (Code rate: Rc = ½) Modulation: Binary Phase Shift Keying (BPSK) Comparison of BCH codes with different block length n , but constant rate Rc ~ ½.

For constant Rc , the BER performance increases significantly with block length n . Aug-2013

www.AtlantaRF.com

33

Atlanta RF Services, Software & Designs

Bit error rates for BCH codes (Code rate: Rc = ¼) Modulation: Binary Phase Shift Keying (BPSK) Comparison of BCH codes with different block length n , but constant rate Rc ~ ¼ .

For constant Rc , the BER performance increases significantly with block length n .

Aug-2013

www.AtlantaRF.com

34

Atlanta RF Services, Software & Designs

Bit error rates for BCH codes (Code rate: Rc = ¾) Modulation: Binary Phase Shift Keying (BPSK) Comparison of BCH codes with different block length n , but constant rate Rc ~ ¾.

For constant Rc , the BER performance increases significantly with block length n .

Aug-2013

www.AtlantaRF.com

35

Atlanta RF Services, Software & Designs

Reed-Solomon Error Correcting Codes: Overview Link Budget Analysis: Error Control & Detection 1. Reed Solomon (R-S) codes form an important sub-class of the family of BoseChaudhuri-Hocquenghem (BCH) block-based codes and are very powerful linear non-binary block codes capable of correcting multiple random errors, as well as ‘burst-error’ correction; that is, they are effective for channels that have memory. 2. In 1960, Irving Reed and Gus Solomon published a paper* that described a new class of error-correcting codes, now called: Reed-Solomon (R-S) codes. 3. These R-S codes have great power and utility, and are used to correct errors in many digital communication systems including: A. B. C. D. E.

Storage devices: Magnetic tape, Compact Disk, DVD, barcodes, etc… Wireless/mobile communications: Cellular telephones, microwave links, etc. Satellite communications. Digital television/Digital Video Broadcast (DVB). High-speed modems such as ADSL, xDSL, etc.

4. Reed-Solomon codes achieve the largest possible code minimum distance for any linear code with the same encoder input and output block lengths. 5. RS coding is eight times more faster than convolutional coding. * Reed, I. S. and Solomon, G., “Polynomial Codes Over Certain Finite Fields”, SIAM Journal of Applied Math., Volume 8, 1960, pages 300-304. Aug-2013

www.AtlantaRF.com

36

Atlanta RF Services, Software & Designs

Reed-Solomon Error Correcting Codes Principle of Operation 1. A Reed-Solomon codeword consists of a block of data “symbols”, with parity symbols appended. 2. An (n, k) Reed-Solomon error correction code has parameters: n symbols A. Symbol length: m bits per symbol. k symbols 2t symbols B. Block length: n = 2m – 1 symbols, Information data Redundant/parity bits = m(2m – 1) bits. C. Message data length: k = 2m – 1 – 2t, symbols. D. Size of parity check code: n – k = 2t symbols = m(2t) bits. E. Minimum distance: dmin = 2t + 1 symbols. 3. Input bits are first packed into small blocks of k symbols, which are then packed in super blocks with n symbols by adding redundant bits. 4. RS decoder can correct t symbols in the codeword according to: 2t = n – k . 5. Example: RS(204,188, T=8) has 16 redundant bits and the possibility to correct 8 bits: 2t = n – k = 204 - 188 = 16 redundant bits and t = 8 corrected bits.

6. One bit is used for synchronization and 187 bits contain information. 7. Transmission of information is decreased by the code rate: Rc = k/n .

Atlanta RF Aug-2013

www.AtlantaRF.com

37

Services, Software & Designs

Bite Error Rate for Reed Solomon Codes Modulation: Binary Phase Shift Keying (BPSK)

Atlanta RF Aug-2013

www.AtlantaRF.com

38

Services, Software & Designs

Parameters for a few Reed-Solomon Codes Link Budget Analysis: Error Control & Detection A large number of R-S codes are available with different code rates:

Atlanta RF Aug-2013

www.AtlantaRF.com

39

Services, Software & Designs

Interleaving Link Budget Analysis: Error Control & Detection 1. Convolutional error correction codes are suitable for memoryless channels with randomly distributed and statistically independent error events. 2. Some channels exhibit burst-error characteristics, like: errors in multipath fading channels in wireless communications, errors due to switching noise, 3. “Interleaving” makes the channel look like as a memoryless channel. 4. Interleaving is done by spreading the coded symbols in time (interleaving) before transmission. A burst error that may occur is spread out over a number of blocks, making error correction possible at the receiver’s decoder. 5. The reverse in done at the receiver by deinterleaving the received sequence. 6. “Interleaving” makes bursty errors look like random independent errors. Hence, convolutional and turbo product codes can still be used. 7. Interleaving is neither error-correcting or error-detecting; it is an error avoidance technique. There is no coding gain associated with interleaving. 8. The tradeoff in choosing the size of the interleaver is between time scale of bit dispersal and tolerable delay times/latency in transmission. 9. Types of interleaving: Block interleaving; Convolutional or cross interleaving

Atlanta RF Aug-2013

www.AtlantaRF.com

40

Services, Software & Designs

Convolutional Error Correcting Codes: Overview Link Budget Analysis: Error Control & Detection 1. Convolutional error correcting codes are applied in applications that require good performance with low implementation cost. A. Easy implementation using a linear finite-state shift registers.

2. Convolutional codes offer an approach to error control coding substantially different from that of block codes. 3. They encode/operate on serial information code streams rather than on information blocks, as do Block error correcting codes. 4. Convolution codes have memory that utilizes previous bits to encode or decode following bits (Block codes are memoryless). 5. Its performance is less sensitive to Signal-to-Noise Ratio variations than that of Block codes. In situations of limited power where SNR would be a concern, the preferred method for achieving FEC is based on convolutional codes. Convolution is a mathematical operation on two functions: f and g, producing a third function that is typically viewed as a modified version of one of the original functions, giving the area overlap between the two functions as a function of the amount that one of the original functions is translated. . . . definition from Wikipedia.com

Atlanta RF

Aug-2013

www.AtlantaRF.com

41

Services, Software & Designs

Convolutional Error Correcting Codes: Definition Link Budget Analysis: Error Control & Detection 1. Convolutional codes are generated using linear finite-state shift registers to apply a polynomial to a stream of data. Convolutional codes generate redundant bits continuously, so error checking and correcting are carried out continuously. 2. A Convolutional code is specified by three parameters: n, k, K. A. Input processes k bits at a time. B. Output produces n bits for every k input bits. C. K = constraint length and is a measure of code redundancy. D. k and n generally very small, so they have a lower decoding delay.

3. n-bit output of (n, k, K) code depends on: A. Current block of k input bits. B. Previous K-1 blocks of k input bits.

4. Convolutional codes are typically decoded using the Viterbi algorithm, which increases in complexity exponentially with the constraint length: K. The Viterbi decoder is a Maximum Likelihood Sequence Estimator, that estimates the encoder state using the sequence of transmitted codewords.

Atlanta RF Aug-2013

www.AtlantaRF.com

42

Services, Software & Designs

Convolutional Error Correction Codes Principle of Operation 1. Convolutional encoding creates additional bits from the data, as do Hamming and Reed Solomon codes, but the encoded output is a function of not only the current data bits but also previously occurring data bits. 2. Convolutional codes pass the data to be transmitted through a special shift register. As the serial data is shifted through the shift register flip-flops, some of the flip-flop outputs are XORed together to form two outputs. 3. These two outputs are the convolutional code, and this is what is transmitted. 4. The original data itself is not transmitted. 5. Instead, two separate streams of continuously encoded data are sent. 6. Since each output code is different, the original data can more likely be recovered at the receiver by an inverse process.

Convolutional encoding uses a shift register with exclusive-OR gates to create the output.

Atlanta RF Aug-2013

www.AtlantaRF.com

43

Services, Software & Designs

Bite Error Rate for Convolutional Codes Modulation: Binary Phase Shift Keying (BPSK)

Atlanta RF Aug-2013

www.AtlantaRF.com

44

Services, Software & Designs

Known Good Convolutional Codes Generator Polynomials versus K = Constraint Length Good Codes with Code Rate 1/5

Good Codes with Code Rate 1/3

Good Codes with Code Rate ¼

Good Codes with Code Rate ½

Atlanta RF Aug-2013

www.AtlantaRF.com

45

Services, Software & Designs

LDPC: Low Density Parity Check codes Link Budget Analysis: Error Control & Detection 1. Low Density Parity Check (LDPC) codes were proposed by Robert Gallager* in his 1960 Ph.D dissertation at Massachusetts Institute of Technology, then rediscovered by MacKay and Richardson/Urbanke in 1999. 2. Features of LDPC codes: A. Performance approaching Shannon limit. B. Good block error correcting performance. C. Suitable for parallel implementation. 3. Advantages over Turbo Codes: A. LDPC do not require a long interleaver. B. LDPC’s error floor occurs at a lower BER. C.LDPC decoding is not trellis based. Robert G. Gallager (1931 )

* R. G. Gallager, “Low Density Parity Check Codes,” Sc.D. thesis, Massachusetts Institute of Technology, Cambridge; September, 1960.

Atlanta RF

Aug-2013

www.AtlantaRF.com

46

Services, Software & Designs

Applications with LDPC Codes Link Budget Analysis: Error Control & Detection 1. Low Density Parity Check (LDPC) codes have superior error performance. A. 4 dB coding gain over convolutional codes (see graph, below).

2. Standards and applications:

Bit Error Probability

A. Digital Video Broadcasting: DVB-S2, DVB-T2, DVB-C2. B. Next-Gen Wired Home: Networking (G.hn). C. 10 Gigabit Ethernet (10GBASE-T). 100 D. WiMAX (802.16e). E. WiFi (802.11n). 10-1 F. Hard disks. G. Deep-space satellite missions. 10-2 10-3

Uncoded

4 dB

10-4

Convolutional code

LDPC 0

1

2

3

4

5

6

7

Signal to Noise Ratio (dB)

Atlanta RF Aug-2013

www.AtlantaRF.com

47

Services, Software & Designs

8

Bite Error Rate for LDPC Codes Modulation: Binary Phase Shift Keying (BPSK)

Atlanta RF

LDPC: Low Density Parity Check. Aug-2013

www.AtlantaRF.com

48

Services, Software & Designs

LDPC: Low Density Error Correction codes Advantages and Disadvantages 1. Advantages of LDPC codes: A. Near Capacity Performance…. approaches Shannon’s Capacity Limit. B. Some LDPC Codes perform better than Turbo Codes. C. Trellis diagrams for Long Turbo Codes become very complex and computationally elaborate. D. Low BER Floor Error . E. Decoding in the Log Domain is quite fast.

2. Disadvantages of LDPC Codes: A. Can take a long time to converge to a good solution. B. Requires very long code word lengths for good decoding efficiency. C. Iterative convergence is SLOW. 1) Takes ~ 1000 iterations to converge under standard conditions. D. Due to the above reasons, transmission time increases: 1) i.e. Processing: encoding, transmission and decoding E. Hence large initial latency/delay: 1) A (4086,4608) LPDC codeword has a latency of almost 2 hours.

Atlanta RF Aug-2013

www.AtlantaRF.com

49

Services, Software & Designs

Concatenated (Joined) Codes: Overview Link Budget Analysis: Error Control & Detection A concatenated code uses two separated codes: an inner code and an outer code (at a higher data rate), which are combined to form a larger code. 1. Popular concatenated codes: Convolutional codes with Viterbi decoding as the inner code and Reed-Solomon codes as the outer code. 2. Example 1:The convolutional code is well-suited for channels with random errors, and the Reed-Solomon code is well suited to correct the bursty output errors common with a Viterbi decoder. An interleaver is used to spread the Viterbi output error bursts across multiple RS codewords.

The purpose is to reduce the overall complexity, yet achieving the required error performance. Transmit chain

Digtial Input stream

Reed Solomon outer encoder

Interleaver

Convolutional Inner encoder

Digital Modulator

Tx

Channel

Receive chain Digital Output stream

Reed Solomon outer decoder

Deinterleaver

Viterbi/AAP Inner decoder

Rx

Atlanta RF

APP: a posteriori probability Aug-2013

Digital Demodulator

50

Services, Software & Designs

Bite Error Rate for Concatenated Codes Modulation: Binary Phase Shift Keying (BPSK)

Atlanta RF Aug-2013

www.AtlantaRF.com

51

Services, Software & Designs

Turbo Error Correcting Codes: Overview Link Budget Analysis: Error Control & Detection 1. Turbo codes were proposed by Berrou and Glavieux* at the 1993 International Conference in Communications . Today, Turbo Codes are considered the most efficient coding schemes for FEC. 2. The name was derived from an iterative decoding algorithm used to decode these codes where, like a turbo engine: Part of the output is reintroduced at the input and processed again. 3. Turbo Codes provided the first known means of achieving decoding performance close to the theoretical Shannon capacity.

Turbo codes get their name because the decoder uses feedback, like a turbo engine.

* C. Berrou, A. Glavieux, P. Thitimajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes”, Proc. ICC ’93, Geneva, Switzerland, pp. 1064-1070, May 1993.

Atlanta RF

Aug-2013

www.AtlantaRF.com

52

Services, Software & Designs

Turbo Convolutional Codes Principle of Operation 1. Turbo Codes add error coding diversity by encoding the same data twice through concatenation (i.e.: joining 2 convolutional codes). 2. The two decoders, each working on a different codeword, can “iterate” and continue to pass reliability update information to each other in order to improve the probability of converging on the correct solution. Once some stopping criterion has been met, the final data estimate is provided for use. Essentially concatenating (i.e.: joining) two convolutional codes (may be the same code algorithm): A. One code operates on straight input. B. Other code operates on delayed and interleaved input. C. Decoding involves iteration between the two codes.

Atlanta RF Aug-2013

www.AtlantaRF.com

53

Services, Software & Designs

Bite Error Rate for Turbo Codes Modulation: Binary Phase Shift Keying (BPSK)

Atlanta RF Aug-2013

www.AtlantaRF.com

54

Services, Software & Designs

Turbo Code vs Number of Iterations for UMTS Link Budget Analysis: Error Control & Detection Bit-error performance of the Universal Mobile Telecommunications System (UMTS) turbo code as the number of decoder iterations varies from one to ten. The encoder input word length is k = 1530 bits, modulation is BPSK, and channel is AWGN.

Atlanta RF Aug-2013

www.AtlantaRF.com

55

Services, Software & Designs

Applications of Turbo Convolutional Codes Link Budget Analysis: Error Control & Detection Application CCSDS (deep space) UMTS, LTE and CDMA2000 (3GPPx Mobile) DVB-RCS (Return Channel over Satellite) DVB-RCT (Return Channel over Terrestrial)

Inmarsat (Aero-H Satellite) Eutelsat (Skyplex Satellite) IEEE 802.16 (WiMAX)

Turbo code Termination

Polynomials

Code Rates

Tail bits

23, 33, 25, 37 13, 15, 17

1/6, 1/4, 1/3, 1/2 1/4, 1/3, 1/2

Duo-binary, 8-state

Circular

15, 13

1/3 up to 6/7

Duo-binary, 8-state

Circular

15, 13

1/2, 3/4

Binary, 16-state Duo-binary, 8-state Duo-binary, 8-state

No

23, 35

1/2

Circular

15, 13

4/5, 6/7

Circular

15, 13

1/2 up to 7/8

Binary, 16-state Binary, 8-state

Tail bits

CCSDS: Consultative Committee for Space Data Systems (telemetry standard).

Atlanta RF

Aug-2013

www.AtlantaRF.com

56

Services, Software & Designs

Turbo Code: Advantages & Disadvantages Link Budget Analysis: Error Control & Detection 1. Advantages: A. Turbo codes have remarkable power efficiency in AWGN and flat-fading channels for moderately low BER. B. Design tradeoffs suitable for delivery of multimedia services. 2. Disadvantages: A. Turbo codes exhibit high latency/delay due to interleaving and iterative decoding. B. Poor performance at very low BER. C.Because turbo codes operate at very low SNR, channel estimation and tracking is a critical issue.

Atlanta RF Aug-2013

www.AtlantaRF.com

57

Services, Software & Designs

Turbo Product Codes (TPC) Link Budget Analysis: Error Control & Detection 1. Turbo Product Codes offer excellent performance at high code rates. 2. TPC’s have low complexity relative to coding gain. 3. Lower cost and lower power consumption. 4. TPCs offer significant improvement over concatenated Reed-Solomon codes/Viterbi algorithm. 5. A single low cost TPC encoder/decoder can support code rates from 1/5 to 19/20. 6. No puncturing required. 7. Code change ‘on the fly’ supports changing channel environments. A. Near zero latency, no “tail biting” required. Turbo Product Code (128,127) x (128,127) (128,120) x (128,127) (64,57) x (32,26) (32,26) x (16,15) x (8,7) (16,11) x (16,11) (16,11) x (16,11) x (16,11 )

Block Size Code Rate 16,383 16,383 2,048 4,096 256 4,096

0.98 0.93 0.72 0.66 0.47 0.32

Atlanta RF Aug-2013

www.AtlantaRF.com

58

Services, Software & Designs

Turbo Convolutional verse Turbo Product Codes Link Budget Analysis: Error Control & Detection 1. How generated: A. Turbo Convolutional Codes (TCC) are generated from Concatenated Convolutional codes. B. Turbo Product Codes (TPCs) are based on block codes, not convolutional codes.

2. Code Rate: A. TCCs perform best for low code rate applications: Within 1dB of Shannon Limit. B. TPCs perform best for high code rate applications.

3. Data Rate: A. TCCs will have difficulty achieving high data rates. B. TPCs can operate to data rates of 10 Gbps in CMOS.

4. Error Floor: A. TCCs exhibit error floor at BERs below 10-5 . B. TPCs error floor (flare) is less pronounced and at lower BER values.

5. Intellectual Property/Patents: A. TCCs require a license from France Telecom. B. TPCs based on public domain technology.

Atlanta RF Aug-2013

www.AtlantaRF.com

59

Services, Software & Designs

Design Trade-offs with Error Correction Link Budget Analysis: Error Control & Detection 1. Trade-off 1: Error performance versus Bandwidth A. For a fixed Signal-to-Noise value……. B. Error correction code produces a smaller BER. C. Error correction code More bandwidth needed to transmit information bits and redundancy bits. PB

2. Trade-off 2: Power versus Bandwidth

A. For a fixed BER and data rate value…… B. Error correction code smaller Eb/No smaller signal: Pr . C. Error correction code More bandwidth needed to transmit information bits and redundancy bits.

Coded A F

3. Trade-off 3: Data rate versus Bandwidth A. For a fixed BER and Tx power level….. B. Error correction code smaller Eb/N0 bigger data rate: R . C. Error correction code More bandwidth needed to transmit information bits and redundancy bits.

C

B

D E

Uncoded

Eb / N 0 (dB)

Atlanta RF Aug-2013

www.AtlantaRF.com

60

Services, Software & Designs

Atlanta RF

Services, Software & Designs

Atlanta RF LLC was founded to provide engineering solutions, design software solutions, and product development solutions to the high-frequency RF/microwave industry in the areas of: Telecommunications (ground segment), Satellite (space segment) and military/defense (RF front-ends). Through teamwork, Atlanta RF applies our diverse technical experience to your project's challenges with creative and innovative solutions while holding ourselves accountable fo the results. With professionalism and commitment to our clients, Atlanta RF will be there for you, both today and tomorrow. Contact Atlanta RF by e-mail at: ➢ Atlanta RF Services : [email protected] ➢ Atlanta RF Software : [email protected] ➢ Atlanta RF Designs : [email protected] Or, contact Atlanta RF by phone at: 678-445-5544, to reach our Atlanta-area office in Georgia, USA, and discuss our support to your current or future projects & products.

Atlanta RF Aug-2013

www.AtlantaRF.com

61

Services, Software & Designs

Forward Error Correction & Modulation Spectral Efficiency vs. Eb/No

Source: Comtech EF Data: http://www.comtechefdata.com/technologies/fec Aug-2013

www.AtlantaRF.com

62

Atlanta RF Services, Software & Designs

Presentations by Atlanta RF, LLC Download various presentations at our website: www.AtlantaRF.com : 1. Satellite: LEO, MEO & GEO. 2. Antennas: An Overview. 3. Link Budget: Getting Started. 4. Link Budget: Digital Modulation Part 1 (Overview & M-ASK). 5. Link Budget: Digital Modulation Part 2 (M-FSK). 6. Link Budget: Digital Modulation Part 3 (M-PSK & QAM). 7. Link Budget: Error Control & Detection. 8. Multiple Access Techniques: FDMA, TDMA and CDMA. 9. Insertion Loss: Double Ridge Waveguide. 10.RF Filters: An Overview. 11.Multi-Section Symmetrical Directional Couplers. 12.Parallel Coupled Bandpass Filters. Visit our website often as presentations are added for your viewing pleasure.

Atlanta RF Aug-2013

www.AtlantaRF.com

63

Services, Software & Designs

Loading...