Channel Coding.ppt

Jun 10, 2023Download as PPT, PDF0 likes20 views

This document discusses different channel coding techniques. It begins by introducing the concept of a noisy communication channel and the need for error correction. It then discusses early techniques like repetition coding and parity check codes. More advanced linear block codes and convolutional codes are presented. The document notes that while these codes help reduce errors, they do not achieve the theoretical maximum rate allowed by Shannon's channel capacity theorem. Finally, it introduces turbo codes as a breakthrough that can operate very close to channel capacity with reasonable complexity.

Channel Coding
Binit Mohanty
Ketan Rajawat

Recap��
? Information is transmitted through
channels (eg. Wires, optical fibres
and even air)
? Channels are noisy and we do not
receive what was transmitted

System Model
? A Binary Symmetric Channel
? Crossover with probability p

Repetition Coding
? Assume 1/3 repetition
? What is the probability of
error ?
? If crossover probability p = 0.01, Pe ��
0.0003
? Here coding rate R = 1/3. Can we do
better? How much better?
000
0 ?
111
1?
3
2
2
3
)
1
( p
p
p
P C
e ?
?
?

Shannon��s Theorem
? Given,
? A noisy channel (some fixed p)
? A value of Pe which we want to achieve
��We can transmit through the channel and achieve
this probability of error at a maximum coding
rate of C(p)��
? Is it counterintuitive?
? Do such good codes exist?

Channel Capacity
? C(p) is called the channel capacity
? For binary symmetric channel,
? Can we really design codes that achieve
this rate? How?
9192
.
0
)
01
.
0
( ?
?
p
C

Parity Check Codes
? #information bits transmitted = k
? #bits actually transmitted = n = k+1
? Code Rate R = k/n = k/(k+1)
? Error detecting capability = 1
? Error correcting capability = 0

2-D Parity Check
? Rate?
? Error detecting
capability?
? Error correcting
capability?
1 0 0 1 0 0
0 1 0 0 0 1
1 0 0 1 0 0
1 1 0 1 1 0
1 0 0 1 1 1
Bottom row consists of
check bit for each column
Last column consists
of check bits for each
row

Linear Block Codes
? #parity bits n-k (=1 for Parity Check)
? Message m = {m1 m2 �� mk}
? Transmitted Codeword c = {c1 c2 �� cn}
? A generator matrix Gkxn
? What is G for repetition code?
? For parity check code?
mG
c ?

Linear Block Codes
? Linearity
? Example : 4/7 Hamming Code
? k = 4, n = 7
? 4 message bits at (3,5,6,7)
? 3 parity bits at (1,2,4)
? Error correcting capability =1
? Error detecting capability = 2
? What is G?
,
1
1 G
m
c ?
G
m
c 2
2 ?
G
m
m
c
c )
( 2
1
2
1 ?
?
?

Cyclic codes
? Special case of Linear Block Codes
? Cyclic shift of a codeword is also a
codeword
? Easy to encode and decode,
? Can correct continuous bursts of errors
? CRC (used in Wireless LANs), BCH codes,
Hamming Codes, Reed Solomon Codes
(used in CDs)

Convolutional Codes
? Block codes require a buffer
? What if data is available serially bit by
bit? Convolutional Codes
? Example
k = 1
n = 2
Rate R = ?

Convolutional Codes
? Encoder consists of shift registers
forming a finite state machine
? Decoding is also simple �C Viterbi
Decoder which works by tracking
these states
? First used by NASA in the voyager
space programme
? Extensively used in coding speech
data in mobile phones

Achieving Capacity
? Do Block codes and Convolutional
codes achieve Shannon Capacity?
Actually they are far away
? Achieving Capacity requires large k
(block lengths)
? Decoder complexity for both codes
increases exponentially with k �C not
feasible to implement

Turbo Codes
? Proposed by
Berrou & Glavieux
in 1993
? Advantages
? Use very large block lengths
? Have feasible decoding complexity
? Perform very close to capacity
? Limitation �C delay, complexity

Summary
? There is a limit on the how good
codes can be
? Linear Block Codes and Convolutional
Codes have traditionally been used
for error detection and correction
? Turbo codes in 1993 introduced a new
way of designing very good codes
with feasible decoding complexity

The document discusses error control coding, which detects and corrects errors in received symbols. It defines error control coding and describes how it works by segmenting the bit stream into blocks and mapping blocks to codewords. The channel decoder detects and possibly corrects errors. It discusses ARQ and FEC techniques for error control. Specific coding techniques covered include Hamming distance, linear block coding, syndrome coding, and block vs convolutional coding. Applications of error control coding include aerospace, cellular networks, and security systems.

PresentationLalit Garg

The document discusses turbo codes, which are a type of error correction code used in communication systems. Turbo codes work by concatenating two or more simple convolutional codes with an interleaver between them. This structure allows for iterative decoding that can achieve performance close to the theoretical maximum. The key aspects covered are the turbo code concepts, log likelihood algebra used in decoding, the purpose and types of interleaving, and how recursive systematic convolutional codes are used as the component codes of a turbo code.

Hossein Taghavi : Codes on Graphsknowdiff

This document provides an overview of coding theory and recent advances in low-density parity-check (LDPC) codes. It discusses Shannon's channel coding theorem and how modern error-correcting codes achieve rates close to channel capacity. LDPC codes are described as having sparse parity-check matrices and being decoded iteratively using message passing. The performance of LDPC codes can be analyzed using density evolution and threshold calculations. Linear programming decoding is introduced as an alternative decoding approach that has connections to message passing decoding.

Implementation of reed solomon codes basicsRam Singh Yadav

This document provides an overview of Reed Solomon codes. It begins with the objectives to implement an encoder and decoder for Reed Solomon codes using MATLAB. It then introduces error control mechanisms like forward error correction and automatic repeat request. Various error detection and correction techniques are discussed, including Hamming codes and Reed Solomon codes. Reed Solomon codes are explained in detail, including how they are represented, encoded, and decoded to correct errors. Applications of Reed Solomon codes in storage, wireless communication, satellite, and digital television are also mentioned.

BLOCK CODES,STBCs & STTCs.pptxFAIZAN SHAFI

Space time block coding?is a technique used in?wireless communication?to transmit multiple copies of a data stream across a number of?antennas and to exploit the various received versions of the data to improve the reliability of data transfer. The fact that the transmitted signal must traverse a potentially difficult environment with?scattering, reflection, refraction and so on and may then be further corrupted by?thermal noise?in the?receiver means that some of the received copies of the data may be closer to the original signal than others. This redundancy results in a higher chance of being able to use one or more of the received copies to correctly decode the received signal. In fact,?space�Ctime coding combines?all?the copies of the received signal in an optimal way to extract as much information from each of them as possible.

Turbo Codesvasanth_mtech

Turbo codes provide reliable communication at high data rates by combining concepts from block and convolutional codes. They use two convolutional encoders separated by an interleaver, producing redundant parity bits. During iterative decoding, probabilistic information from the first decoder is used as a priori information for the second decoder, and vice versa, improving the estimates of the transmitted bits at each iteration. Turbo codes achieve performance close to the theoretical channel capacity limit with low error rates. They have applications in deep space communications, mobile wireless systems, and other areas requiring high reliability transmission.

Channel Coding .pptxMortadha96

Channel coding is used in digital communication systems to provide error control and allow reliable transmission of information over noisy channels. The two main methods of error control coding are forward error correction (FEC) and automatic repeat request (ARQ). FEC encodes redundant data into each message to allow the receiver to correct errors without requesting retransmissions, while ARQ relies on the receiver to request retransmission of corrupted data. Common types of FEC codes include block codes, cyclic codes, and convolutional codes, with each code characterized by parameters like coding rate and minimum distance that determine its error detection and correction capabilities.

Channel coding Ola Mashaqi @ an-najah national university

Channel coding is used to reduce error rates when digital communication encounters unacceptable errors over noisy channels. It works by mapping fixed-length message blocks to longer codewords with added check bits for error detection and correction. There are two main schemes for dealing with errors - Automatic Repeat Request retransmits codewords until error-free, while Forward Error Correction can detect and fix bit errors directly. The minimum distance of a code determines its ability to detect and correct errors using Hamming distance calculations during decoding. Bounds like the Hamming Bound provide the maximum number of codewords a code can contain to guarantee certain error correction capabilities.

Turbo Code SudhanshuSaini5

This document discusses turbo and turbo-like codes. It begins with an introduction to turbo codes, describing them as a class of high-performance error correction codes that were the first practical codes to closely approach channel capacity. It then covers channel coding, Shannon's theory, existing coding schemes like block codes and convolutional codes, and the need for better codes. The document spends significant time explaining turbo codes in detail, including their structure using parallel concatenated convolutional codes, interleaving, and iterative decoding. It also discusses related coding schemes like turbo product codes and low-density parity check codes. Finally, it reviews the performance, practical issues, applications in standards, and future trends of turbo and turbo-like codes.

Codingmahdi nematshahi

This document discusses digital baseband communication systems and line coding techniques. It provides an overview of the key steps in analog-to-digital conversion: sampling, quantization, mapping, and encoding/pulse shaping. It then describes several common line coding schemes used to transmit the digital bit stream over physical channels, including unipolar, polar, and bipolar encoding. The advantages and disadvantages of each scheme are discussed in terms of properties like DC balance, clock recovery, energy, and bandwidth.

��Ĵογ� Chap8Emma2013

This document discusses error control coding, also known as channel coding. It begins by introducing concepts such as bit error rate and methods to reduce it, including increasing transmission power, diversity techniques, automatic repeat request (ARQ), and forward error correction (FEC) codes. It then provides details on parity checks, cyclic redundancy checks (CRCs), and block error correction codes. Specific error control coding techniques like Reed-Solomon codes are also mentioned.

Convolutional Error Control CodingMohammed Abuibaid

Direct Link Lanyanhul

The document discusses several topics related to reliable data transmission over physical networks: 1) Encoding techniques like NRZ, Manchester, and 4B/5B encode binary data onto signals to transmit over networks and solve issues like consecutive 1s/0s. 2) Framing breaks the bit stream into frames using techniques like sentinel bits, counters, or clock timing. 3) Error detection codes like parity checks, checksums, and cyclic redundancy checks (CRCs) detect errors by adding redundant bits and checking values at the receiver.

Reed Solomon Coding For Error Detection and Correctioninventionjournals

This document discusses Reed-Solomon coding for error detection and correction. It provides an overview of Reed-Solomon codes, including that they are a type of linear block code well-suited for correcting burst errors. The encoding and decoding processes are described at a high-level, involving the generation and root-finding of polynomials over Galois fields. Applications mentioned include data storage, satellite communications, barcodes, and CD audio. In summary, the document provides a technical introduction to Reed-Solomon coding, the encoding and decoding algorithms, and common uses in digital communication and storage systems.

5G mmwaves - problems and solutions (graduation project)Faculty of Engineering - Alexandria University

Design and Performance Analysis of Convolutional Encoder and Viterbi Decoder ...IJERA Editor

In digital communication forward error correction methods have a great practical importance when channel is noisy. Convolutional error correction code can correct both type of errors random and burst. Convolution encoding has been used in digital communication systems including deep space communication and wireless communication. The error correction capability of convolutional code depends on code rate and constraint length. The low code rate and high constraint length has more error correction capabilities but that also introduce large overhead. This paper introduces convolutional encoders for various constraint lengths. By increasing the constraint length the error correction capability can be increased. The performance and error correction also depends on the selection of generator polynomial. This paper also introduces a good generator polynomial which has high performance and error correction capabilities.

Reed solomon codeMelaku Bayih Demessie

Reed Solomon codes are a type of linear block code that can detect and correct errors in transmitted data. Reed Solomon codes operate by dividing a message into blocks, calculating redundant parity data for each block based on the message contents, and transmitting the blocks with parity. At the receiver, the redundant data enables detection and correction of errors that may have occurred during transmission. Popular examples include RS(255,223) codes that can correct up to 16 byte errors per codeword. Reed Solomon codes are widely used in storage devices and wireless communications due to their high error correction capability.

Digital Communication: Channel CodingDr. Sanjay M. Gulhane

This document discusses channel coding and linear block codes. Channel coding adds redundant bits to input data to allow error detection and correction at the receiver. Linear block codes divide the data into blocks, encode each block into a larger codeword, and use a generator matrix to map message blocks to unique codewords. The codewords can be detected and sometimes corrected using a parity check matrix. Hamming codes are a type of linear block code that can correct single bit errors. The document provides examples of encoding data using generator matrices and decoding using syndrome values and parity check matrices. It also discusses how the minimum distance of a code determines its error detection and correction capabilities.

chp2 - data link layer.pptxChakra Pani

The document discusses various data link layer protocols. It begins by explaining the position and functions of the data link layer, including providing an interface to the network layer, dealing with transmission errors, regulating data flow, and preventing fast senders from overwhelming slow receivers. It then discusses various data link layer design issues like framing, error control, flow control, and the services provided to the network layer. The document proceeds to explain different elementary data link protocols like unrestricted simplex, stop-and-wait, and simplex protocols for noisy channels. It concludes by describing sliding window protocols including one-bit, go-back-N, and selective repeat protocols.

Channel Coding (Digital communication)VARUN KUMAR

Channel coding adds redundancy to transmitted data to allow for error correction and detection. It is used to achieve reliable digital communication in the presence of noise and interference. There are two main types of channel coding: linear block codes and convolution codes. Linear block codes divide data into blocks and encode each block into a longer codeword. Convolution codes consider not only the current data but also previous data when encoding. Channel coding trades off bandwidth for improved error correction through the addition of redundant parity bits.

02 ldpc bit flipping_decoding_dark knightDevanshi Piprottar

The document discusses low density parity check (LDPC) codes. It begins with a brief history of LDPC codes, invented by Gallager in 1960 but rediscovered in the 1990s. It then discusses linear block codes and how they can be represented by generator and parity check matrices. The key properties of LDPC codes are described, including their sparse parity check matrix and regular or irregular structure. Decoding of LDPC codes using tanner graphs and hard decision bit flipping algorithms is explained. Finally, some applications of LDPC codes in communication systems and data storage are provided.

Analysis of Error Correcting Code Algorithms used in WiMax CommunicationsWilliam Chipman

This document discusses error-correcting codes used for wireless communications. It summarizes three error-correcting code algorithms: Reed-Solomon codes, Turbo codes, and low-density parity-check (LDPC) codes. Reed-Solomon codes use a polynomial representation of data and oversampling to allow reconstruction of the original data if enough redundant data is received. Turbo codes use an encoder that generates parity bits for the original data and a permuted version, and an iterative decoder makes soft decisions to determine the correct values. LDPC codes were also developed by Gallager but were impractical to implement until recently.

Error Control Coding -IntroductionBurdwan University

Survey on Error Control Coding TechniquesIJTET Journal

This document discusses various error control coding techniques used to ensure correct data transmission over noisy channels. It describes automatic repeat request and forward error correction as the two main approaches. Specific coding schemes covered include parity codes, Hamming codes, BCH codes, Reed-Solomon codes, LDPC codes, convolutional codes, and turbo codes. Reed-Solomon codes can correct multiple burst errors with high code rates. LDPC codes provide performance close to the Shannon limit with lower complexity than turbo codes. The document provides an overview of the coding techniques and their encoding and decoding processes.

Performance Study of RS (255, 239) and RS (255.233) Used Respectively in DVB-...IJERA Editor

The error correction codes have a wide range of applications in digital communication (satellite, wireless) and digital data storage. This paper presents a comparative study of performance between RS (255, 239) and RS (255.233) used respectively in the Digital Video Broadcasting �C Terrestrial (DVB-T) and National Aeronautics and Space Administration (NASA). The performances were evaluated by applying modulation scheme in additive white Gaussian noise (AWGN) channel. Performances of modulation with RS codes are evaluated in bit error rate (BER) and signal energy -to- noise power density ratio (Eb / No). The analysis is studied with the help of MATLAB simulator to analyze a communication link with AWGN Channel, and different modulations.

Signal Distortion Techniques for PAPR Reduction in OFDM systemsNeil Christian Bonilla

1. The document analyzes the effect of signal distortion techniques for PAPR reduction like clipping and peak windowing on the bit error rate (BER) performance of turbo and low density parity check (LDPC) coded orthogonal frequency division multiplexing (OFDM) systems. 2. It implements an OFDM system based on IEEE 802.11a standards with turbo and LDPC error correcting codes over additive white Gaussian noise (AWGN) and exponentially decaying Rayleigh fade channels. 3. The results show that LDPC-COFDM performs better than turbo-COFDM in both channels, even with clipping applied. However, turbo-COFDM is better with peak windowing due to

Digital-transmission.pptxDennisA6

This document discusses key concepts in digital communications and pulse modulation techniques. It begins by outlining learning objectives related to comparing analog and digital communication, sampling rates, pulse modulation types, pulse-code modulation (PCM), companding, coding and decoding of PCM signals, delta modulation, and lossy/lossless compression. It then provides details on topics like digital transmission requirements, advantages of digital transmission, pulse modulation, PCM processing, quantization, line codes, companding, and delta modulation.

Application of Artificial Neural Networks.pdfJeveshMagnani

CE324-Module-6-Linear Equations-Week.pptxHannahPil2

More Related Content

Similar to Channel Coding.ppt (20)

Channel coding Ola Mashaqi @ an-najah national university

Turbo Code SudhanshuSaini5

Codingmahdi nematshahi

��Ĵογ� Chap8Emma2013

Convolutional Error Control CodingMohammed Abuibaid

Direct Link Lanyanhul

Reed Solomon Coding For Error Detection and Correctioninventionjournals

5G mmwaves - problems and solutions (graduation project)Faculty of Engineering - Alexandria University

Design and Performance Analysis of Convolutional Encoder and Viterbi Decoder ...IJERA Editor

Reed solomon codeMelaku Bayih Demessie

Digital Communication: Channel CodingDr. Sanjay M. Gulhane

chp2 - data link layer.pptxChakra Pani

Channel Coding (Digital communication)VARUN KUMAR

02 ldpc bit flipping_decoding_dark knightDevanshi Piprottar

Analysis of Error Correcting Code Algorithms used in WiMax CommunicationsWilliam Chipman

Error Control Coding -IntroductionBurdwan University

Survey on Error Control Coding TechniquesIJTET Journal

Performance Study of RS (255, 239) and RS (255.233) Used Respectively in DVB-...IJERA Editor

Signal Distortion Techniques for PAPR Reduction in OFDM systemsNeil Christian Bonilla

Digital-transmission.pptxDennisA6

Channel coding Ola Mashaqi @ an-najah national university

Turbo Code SudhanshuSaini5

Codingmahdi nematshahi

��Ĵογ� Chap8Emma2013

Convolutional Error Control CodingMohammed Abuibaid

Direct Link Lanyanhul

Reed Solomon Coding For Error Detection and Correctioninventionjournals

5G mmwaves - problems and solutions (graduation project)Faculty of Engineering - Alexandria University

Design and Performance Analysis of Convolutional Encoder and Viterbi Decoder ...IJERA Editor

Reed solomon codeMelaku Bayih Demessie

Digital Communication: Channel CodingDr. Sanjay M. Gulhane

chp2 - data link layer.pptxChakra Pani

Channel Coding (Digital communication)VARUN KUMAR

02 ldpc bit flipping_decoding_dark knightDevanshi Piprottar

Analysis of Error Correcting Code Algorithms used in WiMax CommunicationsWilliam Chipman

Error Control Coding -IntroductionBurdwan University

Survey on Error Control Coding TechniquesIJTET Journal

Performance Study of RS (255, 239) and RS (255.233) Used Respectively in DVB-...IJERA Editor

Signal Distortion Techniques for PAPR Reduction in OFDM systemsNeil Christian Bonilla

Digital-transmission.pptxDennisA6

Recently uploaded (20)

Application of Artificial Neural Networks.pdfJeveshMagnani

CE324-Module-6-Linear Equations-Week.pptxHannahPil2

Introduction-to-Stack-Instruction.pptxpptpptsuhas060606

Introduction to Stack, ? Stack ADT, ? Implementation of Stack using array, ...Dr. Madhuri Jawale

move curriculum guidennnnnnnnnnnnnnnnnnnnnnnoriginal.pptxCarlosFernandez289274

Matrices for Bid No Bid for estimation.pptxAshishshesharajBhale

��㏊��Y��_Data-Centric AI in The Age of Large Language Models��ʽ��

��Y�ϤǤϡ�LLM�γɹ��ˤϥǩ`��|�ȶ��Ԥ��Ƿ�Ǥ��뤳�Ȥ��h��Ƥ��ޤ��Υ�ǥ��ĤΥ��ץ��`��ˌ��ǩ`��Ĥ�AI�_�k��᰸��ꄿ�ʵĤ�͸��Ԥθߤ�LLM�Θ��B��򤱤��Ĥ��ַ��B�餷�Ƥ��ޤ��ǩ`��m��÷��؟�Τ��AI�_�k��Ҫ�ԤˤĤ��Ƥⴥ��Ƥ��ꡢLLM�Υѥե��`�ޥ��Ϥ��򤱤��¤��ҕ��ṩ��ݤǤ�� This paper explains that the success of LLMs depends heavily on the quality and diversity of data. Instead of focusing solely on model improvements, it proposes a data-centric approach to AI development, introducing concrete methods for building more efficient and transparent LLMs. It also discusses data optimization, utilization strategies, and the importance of responsible AI development, offering a fresh perspective on enhancing LLM performance.

AdminTPE.pptx rurjmgnntjktbjknljbdsgngbjtrbejbgrjtbtbtjanvionhamayadji

optical fibres ppt on its full details.pptxsashiP

Development of Economical Dye Sensitized Solar Cell by Characterizing Polymer...OsamaButt23

2. KONSEP EKONOMI TEKNIK & PERANCANGAN TEKNIK.pdfMuhammadToyeb

UNIT-2 - Concurrency & Interprocess Communicatio.pptxkishanchauhan10888

Insertion Sort, Merge Sort. Time complexity of all sorting algorithms and t...Dr. Madhuri Jawale

Application of Artificial Neural Network.pptxJeveshMagnani

b29e51b5-c830-4877-a978-a6b308ea8c5f.pptdashrimi0

lec1.pptx smartgrid fundamental datas presentationPandyselviBalasubram

22PCOAM16_UNIT 2_ Session 12 Deriving Back-Propagation .pptxGuru Nanak Technical Institutions

Chapter 2.pdf Smith Chart and Impedance Matchingdathoang3243

Machine Design Basic Concepts.pptxanjali681362

Angelika Dorosz - BIM School Expert course - Poland, Krakowbim.edu.pl

Application of Artificial Neural Networks.pdfJeveshMagnani

CE324-Module-6-Linear Equations-Week.pptxHannahPil2

Introduction-to-Stack-Instruction.pptxpptpptsuhas060606

Introduction to Stack, ? Stack ADT, ? Implementation of Stack using array, ...Dr. Madhuri Jawale

move curriculum guidennnnnnnnnnnnnnnnnnnnnnnoriginal.pptxCarlosFernandez289274

Matrices for Bid No Bid for estimation.pptxAshishshesharajBhale

��㏊��Y��_Data-Centric AI in The Age of Large Language Models��ʽ��

AdminTPE.pptx rurjmgnntjktbjknljbdsgngbjtrbejbgrjtbtbtjanvionhamayadji

optical fibres ppt on its full details.pptxsashiP

Development of Economical Dye Sensitized Solar Cell by Characterizing Polymer...OsamaButt23

2. KONSEP EKONOMI TEKNIK & PERANCANGAN TEKNIK.pdfMuhammadToyeb

UNIT-2 - Concurrency & Interprocess Communicatio.pptxkishanchauhan10888

Insertion Sort, Merge Sort. Time complexity of all sorting algorithms and t...Dr. Madhuri Jawale

Application of Artificial Neural Network.pptxJeveshMagnani

b29e51b5-c830-4877-a978-a6b308ea8c5f.pptdashrimi0

lec1.pptx smartgrid fundamental datas presentationPandyselviBalasubram

22PCOAM16_UNIT 2_ Session 12 Deriving Back-Propagation .pptxGuru Nanak Technical Institutions

Chapter 2.pdf Smith Chart and Impedance Matchingdathoang3243

Machine Design Basic Concepts.pptxanjali681362

Angelika Dorosz - BIM School Expert course - Poland, Krakowbim.edu.pl

Channel Coding.ppt

1. Channel Coding Binit Mohanty Ketan Rajawat

2. Recap�� ? Information is transmitted through channels (eg. Wires, optical fibres and even air) ? Channels are noisy and we do not receive what was transmitted

3. System Model ? A Binary Symmetric Channel ? Crossover with probability p

4. Repetition Coding ? Assume 1/3 repetition ? What is the probability of error ? ? If crossover probability p = 0.01, Pe �� 0.0003 ? Here coding rate R = 1/3. Can we do better? How much better? 000 0 ? 111 1? 3 2 2 3 ) 1 ( p p p P C e ? ? ?

5. Shannon��s Theorem ? Given, ? A noisy channel (some fixed p) ? A value of Pe which we want to achieve ��We can transmit through the channel and achieve this probability of error at a maximum coding rate of C(p)�� ? Is it counterintuitive? ? Do such good codes exist?

6. Channel Capacity ? C(p) is called the channel capacity ? For binary symmetric channel, ? Can we really design codes that achieve this rate? How? 9192 . 0 ) 01 . 0 ( ? ? p C

7. Parity Check Codes ? #information bits transmitted = k ? #bits actually transmitted = n = k+1 ? Code Rate R = k/n = k/(k+1) ? Error detecting capability = 1 ? Error correcting capability = 0

8. 2-D Parity Check ? Rate? ? Error detecting capability? ? Error correcting capability? 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 Bottom row consists of check bit for each column Last column consists of check bits for each row

9. Linear Block Codes ? #parity bits n-k (=1 for Parity Check) ? Message m = {m1 m2 �� mk} ? Transmitted Codeword c = {c1 c2 �� cn} ? A generator matrix Gkxn ? What is G for repetition code? ? For parity check code? mG c ?

10. Linear Block Codes ? Linearity ? Example : 4/7 Hamming Code ? k = 4, n = 7 ? 4 message bits at (3,5,6,7) ? 3 parity bits at (1,2,4) ? Error correcting capability =1 ? Error detecting capability = 2 ? What is G? , 1 1 G m c ? G m c 2 2 ? G m m c c ) ( 2 1 2 1 ? ? ?

11. Cyclic codes ? Special case of Linear Block Codes ? Cyclic shift of a codeword is also a codeword ? Easy to encode and decode, ? Can correct continuous bursts of errors ? CRC (used in Wireless LANs), BCH codes, Hamming Codes, Reed Solomon Codes (used in CDs)

12. Convolutional Codes ? Block codes require a buffer ? What if data is available serially bit by bit? Convolutional Codes ? Example k = 1 n = 2 Rate R = ?

13. Convolutional Codes ? Encoder consists of shift registers forming a finite state machine ? Decoding is also simple �C Viterbi Decoder which works by tracking these states ? First used by NASA in the voyager space programme ? Extensively used in coding speech data in mobile phones

14. Achieving Capacity ? Do Block codes and Convolutional codes achieve Shannon Capacity? Actually they are far away ? Achieving Capacity requires large k (block lengths) ? Decoder complexity for both codes increases exponentially with k �C not feasible to implement

15. Turbo Codes ? Proposed by Berrou & Glavieux in 1993 ? Advantages ? Use very large block lengths ? Have feasible decoding complexity ? Perform very close to capacity ? Limitation �C delay, complexity

16. Summary ? There is a limit on the how good codes can be ? Linear Block Codes and Convolutional Codes have traditionally been used for error detection and correction ? Turbo codes in 1993 introduced a new way of designing very good codes with feasible decoding complexity

�ݺ�ߣ

Channel Coding.ppt

Recommended

More Related Content

Similar to Channel Coding.ppt (20)

Recently uploaded (20)

Channel Coding.ppt