2 of 60

DIGITAL COMMUNICATION

COURSE OBJECTIVES:

1. Familiarize the students with elements of digital communication system and waveform coding techniques like PCM, DPCM, DM and ADM.

2. Introduce the concepts of information theory and source coding

3. Familiarize the students with channel coding techniques such as LBC, BCC and convolution codes

4. Introduce the concepts of baseband digital data transmission and analyze the error performance of different digital carrier modulation schemes like ASK, FSK, PSK etc.

5. Familiarize the students with the concepts of spread spectrum communication with emphasis on DSSS and FHSS.

COURSE OUTCOMES:

CO1: Classify the different types of digital modulation techniques PCM, DPCM, DM and ADM and compare their performance by SNR.

CO2: Illustrate the classification of channels and Source coding methods.

CO3:Distinguish different types of Error control codes along with their encoding/decoding algorithms.

CO4: Examine the Performance of different Digital Carrier Modulation schemes of Coherent and Non-coherent type based on Probability of error.

CO5:Generation of PN sequence using Spread Spectrum and characterize the Acquisition Schemes for Receivers to track the signals.

MATRUSRI

ENGINEERING COLLEGE

3 of 60

LESSON PLAN:

UNIT III- Channel Coding

MATRUSRI

ENGINEERING COLLEGE

S. No.	Topic(S)	No. of Hrs	Relevant COs	Text Book/ Reference Book
1.	Types of transmission errors, need for error control coding	01	CO3	T2,R1,R3
2.	Linear Block Codes (LBC): description of LBC, generation	01	CO3	T2,R1,R3
3.	Syndrome and error detection, Minimum distance of Linear block code	02	CO3	T2,R1,R3
4.	error correction and error detection capabilities, Standard array and syndrome decoding, Hamming codes.	02	CO3	T2,R1,R3
5.	Binary cyclic codes (BCC): Description of cyclic codes, encoding	01	CO3	T2,R1,R3
6.	decoding and error correction using shift registers	01	CO3	T2,R1,R3
7	Convolution codes: description, encoding	01	CO3	T2,R1,R3
8	code tree, state diagram	01	CO3	T2,R1,R3
	TOTAL	10

4 of 60

TEXT BOOKS /REFERENCES

TEXT BOOKS:

Simon Haykin, “Communication systems” 4/e, Wiley India 2011
Sam Shanmugam K, “Digital and Analog Communication systems”, Wiley 1979.
B.P.Lathi, “Modern digital and analog communication systems” 3/e, OxfordUniversityPress. 1998.
Leon W.Couch II., Digital and Analog Communication Systems, 6th Edn, Pearson Education inc., New Delhi, 2001.
R.E.Zimer&R.L.Peterson : Introduction to Digital Communication, PHI, 2001.

REFERENCES:

P. Ramakrishna Rao, “Digital Communication”, TMH, 2011.
Dr. Sanjay Sharma, “Digital and Analog Communication”, Mc Graw Hill Publication, 2009.
Bernard Sklar “Digital Communications – Fundamentals and Applications” / 2nd Edition, Prentice Hall.
John G. Proakis” Digital Communications” Fourth Edition (textbook) McGraw Hill.

MATRUSRI

ENGINEERING COLLEGE

5 of 60

UNITIII-CHANNEL CODING: �TYPES OF TRANSMISSION ERRORS, NEED FOR ERROR CONTROL CODING, LINEAR BLOCK CODES (LBC): DESCRIPTION OF LBC, GENERATION, SYNDROME AND ERROR DETECTION, MINIMUM DISTANCE OF LINEAR BLOCK CODE, ERROR CORRECTION AND ERROR DETECTION CAPABILITIES, STANDARD ARRAY AND SYNDROME DECODING, HAMMING CODES. BINARY CYCLIC CODES (BCC): DESCRIPTION OF CYCLIC CODES, ENCODING, DECODING AND ERROR CORRECTION USING SHIFT REGISTERS. CONVOLUTION CODES: DESCRIPTION, ENCODING – CODE TREE, STATE DIAGRAM.

UNIT-III

OUTCOMES:

Distinguish different types of Error control codes along with their encoding/decoding algorithms.

MATRUSRI

ENGINEERING COLLEGE

6 of 60

CONTENTS: �- CHANNEL CODING: INTRODUCTION�- TYPES OF TRANSMISSION ERRORS�- NEED FOR ERROR CONTROL CODING�-CLASSIFICATION OF CODES �

OUTCOMES:

Understanding the need for error control coding techniques with block diagram and different types of codes.

MODULE-I

MATRUSRI

ENGINEERING COLLEGE

7 of 60

INTRODUCTION �IN ANY DIGITAL COMMUNICATION SYSTEM, THE TWO IMPORTANT DESIRABLE FEATURES ARE THE HIGHER TRANSMISSION RATE AND GOOD RELIABILITY (I.E., LOW PROBABILITY OF ERROR). ��TO ACHIEVE THESE FEATURES BASEBAND CODING TECHNIQUES ARE USED. ��THERE ARE TWO TYPES OF BASEBAND CODING. �SOURCE CODING AND �CHANNEL CODING. �

Source coding is used for an efficient representation of data generated by a discrete source.

Channel coding is used for the reliable transmission of digital information over the channel. Channel coding methods introduce controlled redundancy in order to provide error detecting and correcting capability to the data being transmitted. Hence channel coding is also called as error control coding.

Channel Coding

MATRUSRI

ENGINEERING COLLEGE

8 of 60

DEPENDING UPON THE NATURE OF THE NOISE, THE CODEWORDS TRANSMITTED THROUGH THE CHANNEL IS AFFECTED DIFFERENTLY. � �THERE ARE MAINLY TWO TYPES OF ERRORS INTRODUCED DURING DATA TRANSMISSION. �1) RANDOM ERROR�2) BURST ERROR. ��BOTH RANDOM ERROR AND BURST ERRORS OCCUR IN THE CONTENTS OF A MESSAGE. HENCE THEY MAY ALSO BE REFERRED TO AS “CONTENT ERRORS”. ��ALTERNATIVELY, IT IS POSSIBLE THAT A DATA BLOCK MAY BE LOST IN THE NETWORK AS IT HAS BEEN DELIVERED TO A WRONG DESTINATION. IT IS REFERRED AS THE “FLOW INTEGRITY ERROR”. �

Types of Transmission errors

MATRUSRI

ENGINEERING COLLEGE

9 of 60

* THE PRIMARY COMMUNICATION RESOURCES ARE THE TRANSMITTED SIGNAL POWER AND CHANNEL BANDWIDTH.�* THESE TWO PARAMETERS, TOGETHER WITH THE POWER SPECTRAL DENSITY OF RECEIVER NOISE, DETERMINE THE SIGNAL ENERGY PER BIT-TO-NOISE POWER DENSITY RATIO, E_B/N_O. �* THIS RATIO E_B/N_O UNIQUELY DETERMINES THE PROBABILITY OF ERROR (P_E) OR BIT ERROR RATE (BER), FOR A PARTICULAR MODULATION SCHEME. �* THE CHANNEL INDUCED NOISE CAN INTRODUCE ERRORS IN THE TRANSMITTED BINARY DATA. I.E., A BIT 0 MAY CHANGE TO BIT 1 OR A BIT 1 MAY CHANGE TO BIT 0. THE RELIABILITY OF DATA TRANSMISSION GETS SEVERELY AFFECTED BECAUSE OF THESE ERRORS. �

Need for Error Control Coding

MATRUSRI

ENGINEERING COLLEGE

10 of 60

THE CHANNEL ENCODER ADDS EXTRA BITS (REDUNDANCY) TO THE MESSAGE BITS IN A CONTROLLED MANNER. THE ENCODED SIGNAL IS MODULATED AND THEN TRANSMITTED OVER THE NOISY CHANNEL. � AFTER DEMODULATION, THE CHANNEL DECODER IDENTIFIES THE REDUNDANT BITS AND USES THEM TO DETECT AND CORRECT THE ERRORS IN THE MESSAGE BITS. THUS THE ERRORS INTRODUCED DUE TO CHANNEL NOISE ARE MINIMIZED BY CHANNEL CODING. � �

Drawbacks of channel coding � �* The addition of redundant bits in the coded messages, increases the required transmission bandwidth. �* The use of coding adds complexity to the communication system. � � Therefore, the design trade-offs in the use of error control coding to achieve acceptable error performance must include consideration of bandwidth and system complexity.�

Digital Communication System with Channel Coding

MATRUSRI

ENGINEERING COLLEGE

11 of 60

TYPES OF CODES

MATRUSRI

ENGINEERING COLLEGE

12 of 60

1. WHY CODING OF INFORMATION REQUIRED?�2. DEFINE “ERROR”. WRITE THE CAUSE FOR ITS OCCURRENCES IN DIGITAL COMMUNICATION SYSTEMS WITH DIFFERENT TYPES.�3. EXPLAIN THE BLOCK DIAGRAM OF DIGITAL COMMUNICATION SYSTEM WITH CHANNEL CODING.

Questions & Answers

MATRUSRI

ENGINEERING COLLEGE

13 of 60

CONTENTS:�ERROR CONTROL CODING METHODS�IMPORTANT TERMS USED IN ERROR CONTROL CODING�LINEAR BLOCK CODES (LBC): DESCRIPTION OF LBC, �GENERATION, SYNDROME AND ERROR DETECTION, �MINIMUM DISTANCE OF LINEAR BLOCK CODE, ��

OUTCOMES:

Understanding Error Control Coding methods and generation & detection of linear block codes along with Hamming codes.

MODULE-II

MATRUSRI

ENGINEERING COLLEGE

14 of 60

- THE REDUNDANT BITS ADDED TO THE MESSAGE ARE CALLED CHECK BITS. ERRORS CAN BE DETECTED AND CORRECTED WITH THE HELP OF THESE BITS. �- THE CHECK BITS REDUCE THE DATA RATE THROUGH THE CHANNEL. �- IT IS NOT POSSIBLE TO DETECT AND CORRECT ALL THE ERROR IN THE RECEIVED MESSAGE. ERRORS UPTO CERTAIN LIMIT CAN ONLY BE DETECTED AND CORRECTED. ��

There are two main methods used for error control coding. They are

1) Forward acting Error Correction (FEC)

2) Error detection with retransmission or Automatic Repeat Request (ARQ)

ERROR CONTROL CODING METHODS

MATRUSRI

ENGINEERING COLLEGE

15 of 60

�� STOP-AND-WAIT ARQ

Automatic Repeat Request (ARQ)

MATRUSRI

ENGINEERING COLLEGE

16 of 60

�� GO-BACK-N

Automatic Repeat Request (ARQ)

MATRUSRI

ENGINEERING COLLEGE

17 of 60

�� SELECTIVE REPEAT

Automatic Repeat Request (ARQ)

MATRUSRI

ENGINEERING COLLEGE

18 of 60

CODEWORD: �THE ENCODED BLOCK OF ‘N’ BITS IS CALLED A CODEWORD. IT CONTAINS MESSAGE BITS (K) AND REDUNDANT CHECK BITS (Q). � �BLOCK LENGTH: THE NUMBER OF BITS ‘N’ AFTER CODING IS CALLED THE BLOCK LENGTH OF THE CODE. � �CODE RATE: THE CODE RATE ‘R’ IS DEFINED AS THE RATIO OF MESSAGE BITS (K) AND THE ENCODER OUTPUT BITS (N). HENCE, ��CODE RATE, WHERE 0 < R < 1 (3.1)��CODE VECTOR: AN ‘N’ BIT CODE WORD CAN BE VISUALIZED IN AN N-DIMENSIONAL SPACE AS A VECTOR WHOSE ELEMENTS OR CO-ORDINATES ARE THE BITS IN THE CODE WORD. � ��

TERMINOLOGIES

MATRUSRI

ENGINEERING COLLEGE

19 of 60

CODE EFFICIENCY: THE CODE EFFICIENCY IS THE RATIO OF THE MESSAGE BITS TO THE TRANSMITTED BITS FOR THAT BLOCK BY THE ENCODER. HENCE,��WEIGHT OF THE CODE: THE NUMBER OF NON-ZERO ELEMENTS IN THE TRANSMITTED CODE VECTOR IS CALLED CODE VECTOR WEIGHT. � �HAMMING DISTANCE: THE HAMMING DISTANCE (D) BETWEEN THE TWO CODE VECTORS IS EQUAL TO THE NUMBER OF ELEMENTS IN WHICH THEY DIFFER. EG. LET X = 101 AND Y = 110. THEN HAMMING DISTANCE (D) BETWEEN X AND Y CODE VECTORS IS 2. � �MINIMUM HAMMING DISTANCE: �THE SMALLEST HAMMING DISTANCE BETWEEN THE VALID CODE VECTORS IS TERMED AS THE MINIMUM HAMMING DISTANCE (D_MIN). ��

MATRUSRI

ENGINEERING COLLEGE

20 of 60

MODULO-2 ARITHMETIC �1. ADDITION �MODULO-2 ADDITION IS AN EXCLUSIVE OR OPERATION.�0 XOR 0 = 0�0 XOR 1 = 1�1 XOR 0 = 1�1 XOR 1 = 0��

2. Multiplication �Multiplication of binary digits follows AND logic.�0 . 0 = 0�0 . 1 = 0�1 . 0 = 0�1 . 1 = 1

MATRUSRI

ENGINEERING COLLEGE

21 of 60

FUNCTIONAL DIAGRAM OF BLOCK CODER:��AN (N, K) LBC IS A SAID TO BE SYSTEMATIC IF THE K-MESSAGE BITS EITHER APPEAR AT THE BEGINNING OF THE CODEWORD OR AT THE END OF THE CODE WORD.��

Linear Block Codes (LBC): Description of LBC

MATRUSRI

ENGINEERING COLLEGE

22 of 60

MESSAGE BITS :��PARITY BITS: ��CODE VECTOR : �

Generation of Linear Block Codes (LBC)

MATRUSRI

ENGINEERING COLLEGE

23 of 60

PREDETERMINED RULE FOR FINDING PARITY BITS :��P-MATRIX:

Generation of Linear Block Codes (LBC)

MATRUSRI

ENGINEERING COLLEGE

24 of 60

��GENERATOR MATRIX :

Generation of Linear Block Codes (LBC)

MATRUSRI

ENGINEERING COLLEGE

25 of 60

THE H-MATRIX IS USEFUL AT THE DECODER OF THE RECEIVER.

Parity Check Matrix[H]

MATRUSRI

ENGINEERING COLLEGE

26 of 60

ENCODING CIRCUIT OF LBC.

MATRUSRI

ENGINEERING COLLEGE

27 of 60

EXAMPLE 1 �THE GENERATOR MATRIX FOR A BLOCK CODE IS GIVEN BELOW. FIND ALL CODE VECTORS OF THIS CODE. �G = �

Questions & Answers

MATRUSRI

ENGINEERING COLLEGE

28 of 60

CONTENTS:�-SYNDROME AND ERROR DETECTION, �-MINIMUM DISTANCE OF LINEAR BLOCK CODE, �-ERROR CORRECTION AND ERROR DETECTION CAPABILITIES, �-STANDARD ARRAY AND SYNDROME DECODING, �-HAMMING CODES. ��

OUTCOMES:

Estimate the error using syndrome and correct .

MODULE-III

MATRUSRI

ENGINEERING COLLEGE

29 of 60

WHEN R IS RECEIVED, THE DECODER COMPUTES THE FOLLOWING OPERATION.�SYNDROME,��

SYNDROME DECODING

MATRUSRI

ENGINEERING COLLEGE

30 of 60

THE ERROR DETECTION AND CORRECTION CAPABILITIES OF A CODING TECHNIQUE DEPEND ON THE MINIMUM HAMMING DISTANCE DMIN � �ERROR CONTROL CAPABILITIES��

Error detection and correction capability of block codes

MATRUSRI

ENGINEERING COLLEGE

S.No.	Name of errors detected / corrected	Distance requirement
1.	Detect upto ‘s’ errors per code word	dmin ≥ s + 1
2.	Correct upto ‘t’ errors per code word	dmin ≥ 2t + 1
3.	Correct upto ‘t’ errors and detect s > t errors per code word	dmin ≥ t + s+ 1

31 of 60

1. DETERMINE THE SYNDROME OF THE RECEIVED VECTOR R ��2. IDENTIFY THE COSET WITH THIS SYNDROME AND LET ITS COSET LEADER BE AN ERROR PATTERN E�3. DECODE THE RECEIVED VECTOR R INTO THE CODE VECTOR C =R+ E.��

STANDARD ARRAY DECODING

MATRUSRI

ENGINEERING COLLEGE

32 of 60

HAMMING CODES ARE (N, K) LINEAR BLOCK CODES. THEY CAN BE GENERATED EITHER SYSTEMATICALLY OR NON-SYSTEMATICALLY. � �SYSTEMATIC FORM OF HAMMING CODES �THE SYSTEMATIC FORM OF HAMMING CODES SATISFY THE FOLLOWING CONDITIONS. � �1) NUMBER OF CHECK BITS, Q ≥ 3 �2) CODE WORD LENGTH, N = 2^Q – 1 �3) NUMBER OF MESSAGE BITS, K = N – Q �4) MINIMUM HAMMING DISTANCE, D_MIN = 3 �5) SINCE D_MIN = 3, � THE ERROR DETECTION CAPABILITY IS �D_MIN ≥ S + 1 → 3 ≥ S + 1 → S ≤ 3 – 1 → S ≤ 2 � �THE ERROR CORRECTION CAPABILITY IS �D_MIN ≥ 2T + 1 → 3 ≥ 2T + 1 → 2T ≤ 2 → T ≤ 1 � HENCE BY USING HAMMING CODE, WE CAN CORRECT SINGLE BIT ERRORS AND DETECT ERRORS IN TWO BITS. � �

Hamming Codes

MATRUSRI

ENGINEERING COLLEGE

33 of 60

1. THE PARITY CHECK MATRIX OF A (7, 4) LINEAR BLOCK CODE IS GIVEN BY � �H = � ��I. FIND THE GENERATOR MATRIX (G). �II. LIST ALL THE CODE VECTORS. �III. HOW MANY ERRORS CAN BE DETECTED? �IV. HOW MANY ERRORS CAN BE CORRECTED? �V. DRAW THE ENCODER CIRCUIT. �

TRY IT?

MATRUSRI

ENGINEERING COLLEGE

34 of 60

2. CONSIDER A DATA (MESSAGE) BLOCK OF 1 1 0 1. THE HAMMING CODE ADDS THREE PARITY BITS TO THE MESSAGE BITS IN SUCH A WAY THAT BOTH MESSAGE BITS AND CHECK BITS GET MIXED. THE CHECK BIT LOCATIONS ARE AS SHOWN BELOW.� ��HERE P₁, P₂ AND P₃ REPRESENT THE PARITY CHECK BITS TO BE ADDED. D REPRESENTS THE DATA (MESSAGE) BITS. ��

MATRUSRI

ENGINEERING COLLEGE

1	2	3	4	5	6	7	---> Bit location
P1	P2	D	P3	D	D	D

35 of 60

CONTENTS:�- BINARY CYCLIC CODES (BCC): DESCRIPTION OF CYCLIC CODES�- ENCODING, DECODING AND �- ERROR CORRECTION USING SHIFT REGISTERS. �

OUTCOMES:

Understanding generation & detection of Binary cyclic codes (BCC)

MODULE-IV

MATRUSRI

ENGINEERING COLLEGE

36 of 60

A CYCLIC CODE EXHIBITS THE FOLLOWING TWO PROPERTIES. � �(I) LINEARITY PROPERTY: A CODE IS SAID TO BE LINEAR IF MODULO-2 ADDITION OF ANY TWO CODE WORDS WILL PRODUCE ANOTHER VALID CODEWORD. ��(II) CYCLIC PROPERTY: A CODE IS SAID TO BE CYCLIC IF EVERY CYCLIC SHIFT OF A CODE WORD PRODUCES ANOTHER VALID CODE WORD. �FOR EXAMPLE, CONSIDER THE N-BIT CODE WORD, X = (X_N-1, X_N-2, ….. X₁, X₀).

Binary Cyclic Codes (BCC)

MATRUSRI

ENGINEERING COLLEGE

37 of 60

��CYCLICALLY SHIFTING ‘C’ ‘I’ PLACES TO THE RIGHT IS EQUIVALENT TO CYCLICALLY SHIFTING C, (N-I) PLACES TO LEFT. THIS PROPERTY OF CYCLIC CODES ALLOWS US TO TREAT THE ELEMENTS OF EACH CODE-VECTOR AS THE COEFFICIENTS OF A POLYNOMIAL OF DEGREE (N-1) OR LESS.

Representation of code words by a polynomial

MATRUSRI

ENGINEERING COLLEGE

38 of 60

SYSTEMATIC ENCODING : ��BECAUSE X CANNOT BE A FACTOR OF AND MINIMUM FACTOR IS (1+X)��NON-SYSTEMATIC :� C(X)=M(X)G(X).

MATRUSRI

ENGINEERING COLLEGE

39 of 60

Systematic Encoding Using (n-k) shift register

MATRUSRI

ENGINEERING COLLEGE

40 of 60

Syndrome and Error Correction Using (n-k) shift register

MATRUSRI

ENGINEERING COLLEGE

41 of 60

ADVANTAGES OF CYCLIC CODES �- CYCLIC CODES CAN CORRECT BURST ERRORS THAT SPAN MANY SUCCESSIVE BITS. �- THEY HAVE AN EXCELLENT MATHEMATICAL STRUCTURE. THIS MAKES THE DESIGN OF ERROR CORRECTING CODES WITH MULTIPLE-ERROR CORRECTION CAPABILITY RELATIVELY EASIER. �- THE ENCODING AND DECODING CIRCUITS FOR CYCLIC CODES CAN BE EASILY IMPLEMENTED USING SHIFT REGISTERS. �- THE ERROR CORRECTING AND DECODING METHODS OF CYCLIC CODES ARE SIMPLER AND EASY TO IMPLEMENT. THESE METHODS ELIMINATE THE STORAGE (LARGE MEMORIES) NEEDED FOR LOOKUP TABLE DECODING. THEREFORE THE CODES BECOME POWERFUL AND EFFICIENT. � �

Disadvantages of cyclic codes �- Even though the error detection is simpler, the error correction is slightly more complicated. This is due to the complexity of the combinational logic circuit used for error correction. �

Advantages & Disadvantages of cyclic codes

MATRUSRI

ENGINEERING COLLEGE

42 of 60

EXAMPLE 1 �THE GENERATOR POLYNOMIAL OF A (7, 4) CYCLIC CODE IS G(P) = P³ + P + 1. FIND ALL THE CODE VECTORS FOR THE CODE IN NON-SYSTEMATIC FORM. � (I) CONSIDER ANY MESSAGE VECTOR AS � M = (M₃ M₂ M₁ M₀) = (1 0 0 1) � (II) CONSIDER ANOTHER MESSAGE VECTOR AS � M = (M₃ M₂ M₁ M₀) = ( 0 1 1 0 ) ��

Questions & Answers

MATRUSRI

ENGINEERING COLLEGE

Example 2

The generator polynomial of a (7, 4) cyclic code is g(p) = p³ + p + 1. Find all the code vectors for the code in systematic form by considering any message vector as � M = (m₃ m₂ m₁ m₀) = (1 1 1 0 ) ��

43 of 60

CONTENTS:�- CONVOLUTION CODES: DESCRIPTION�- ENCODING – CODE TREE�- STATE DIAGRAM.�

OUTCOMES:

Understanding generation of Convolution codes with graphical representations like code tree, state diagram etc.

MODULE-V

MATRUSRI

ENGINEERING COLLEGE

44 of 60

- IN BLOCK CODING, THE ENCODER ACCEPTS A K-BIT MESSAGE BLOCK AND GENERATES AN N-BIT CODE WORD. THUS CODE WORDS ARE PRODUCED ON A BLOCK-BY-BLOCK BASIS. �- THEREFORE, A BUFFER IS REQUIRED IN THE ENCODER TO PLACE THE MESSAGE BLOCK. ��

A subclass of tree codes is convolutional codes.
The convolutional encoder accepts the message bits continuously and generates the encoded codeword sequence continuously. Hence there is no need for buffer.
But in convolutional codes, memory is required to implement the encoder.

CONVOLUTIONAL CODES

MATRUSRI

ENGINEERING COLLEGE

45 of 60

Convolutional Encoder

MATRUSRI

ENGINEERING COLLEGE

46 of 60

Consider that the current message bit is shifted to position m₀. Then m₁ and m₂ store the previous two message bits. Now, by mod-2 adders 1 and 2 we get the new values of X₁ and X₂. We can write

X₁ = m₀ + m₁ + m₂ and X₂ = m₀ + m₂

Convolutional Encoder redrawn alternatively

MATRUSRI

ENGINEERING COLLEGE

47 of 60

IN THIS CONVOLUTIONAL ENCODER, FOR EVERY INPUT MESSAGE BIT, TWO ENCODED OUTPUT BITS X₁ AND X₂ ARE TRANSMITTED. HENCE NUMBER OF MESSAGE BITS, �K = 1. THE NUMBER OF ENCODED OUTPUT BITS FOR ONE MESSAGE BIT, N = 2.�

Code rate:

The code rate of this convolutional encoder is given by

Code rate, r =

where 0 < r < 1

Convolutional Encoder

MATRUSRI

ENGINEERING COLLEGE

48 of 60

CONSTRAINT LENGTH: �THE CONSTRAINT LENGTH (K) OF A CONVOLUTION CODE IS DEFINED AS THE NUMBER OF SHIFTS OVER WHICH A SINGLE MESSAGE BIT CAN INFLUENCE THE ENCODER OUTPUT. IT IS EXPRESSED IN TERMS OF MESSAGE BITS. ��

Convolutional Encoder

MATRUSRI

ENGINEERING COLLEGE

For the above convolutional encoder, constraint length is K = 3 bits. �Whenever a particular message bit enters the shift register, it remains in the shift register for three shifts i.e., � �First shift → message bit is entered in position m₀. �Second shift → message bit is shifted in position m₁. �Third shift → message bit is shifted in position m₂. � �Constraint length ‘K’ is also equal to one plus the number of shift registers required to implement the encoder.

49 of 60

DIMENSION OF THE CODE:�THE CODE DIMENSION OF A CONVOLUTIONAL CODE DEPENDS ON THE NUMBER OF MESSAGE BITS ‘K’, THE NUMBER OF ENCODER OUTPUT BITS, ‘N’ AND ITS CONSTRAINT LENGTH ‘K’. THE CODE DIMENSION IS THEREFORE REPRESENTED BY (N, K, K). ��FOR THE ENCODER SHOWN ABOVE, THE CODE DIMENSION IS GIVEN BY (2, 1, 3) �WHERE N = 2, K = 1 AND CONSTRAINT LENGTH K = 3. �

Graphical representation of convolutional codes

Convolutional code structure is generally presented in graphical form by the following three equivalent ways. �1. By means of the state diagram �2. By drawing the code trellis �3. By drawing the code tree � �These methods can be better explained by using an example.

Convolutional Encoder

MATRUSRI

ENGINEERING COLLEGE

50 of 60

Example problem

MATRUSRI

ENGINEERING COLLEGE

For the convolutional encoder given below in Figure, determine the following.

a) Code rate b) Constraint length c) Dimension of the code d) Represent the encoder in graphical form.

51 of 60

A) CODE RATE: �THE CODE RATE, R = K/N�THE NUMBER OF MESSAGE BITS, K = 1. �THE NUMBER OF ENCODER OUTPUT BITS, N = 2. �HENCE CODE RATE, R = 1/2� �B) CONSTRAINT LENGTH: �CONSTRAINT LENGTH, K = 1 + NUMBER OF SHIFT REGISTERS. �HENCE K = 1 + 2 = 3 � �C) CODE DIMENSION: �CODE DIMENSION = (N, K, K) = (2, 1, 3) �HENCE THE GIVEN ENCODER IS OF ½ RATE CONVOLUTIONAL ENCODER OF DIMENSION (2, 1, 3).�

Solution

MATRUSRI

ENGINEERING COLLEGE

52 of 60

D) GRAPHICAL FORM REPRESENTATION �THE ENCODER OUTPUT IS X = (X₁ X₂ X₁ X₂ X₁ X₂….. AND SO ON) �THE MOD-2 ADDER 1 OUTPUT IS X₁ = M₀ + M₁ + M₂ �THE MOD-2 ADDER 2 OUTPUT IS X₂ = M₀ + M₂. �WE CAN REPRESENT THE ENCODER OUTPUT FOR POSSIBLE INPUT MESSAGE BITS IN THE FORM OF A LOGIC TABLE. �

Solution

MATRUSRI

ENGINEERING COLLEGE

	Input Message bit	Present State		Next State		Encoder Output
	m₀	m₁	m₂	m₁	m₂	X₁	X₂
A	0	0	0	0	0	0	0
A	1	0	0	1	0	1	1
B	0	1	0	0	1	1	0
B	1	1	0	1	1	0	1
C	0	0	1	0	0	1	1
C	1	0	1	1	0	0	0
D	0	1	1	0	1	0	1
D	1	1	1	1	1	1	0

53 of 60

- THE ENCODER OUTPUT DEPENDS ON THE CURRENT INPUT MESSAGE BIT AND THE CONTENTS IN THE SHIFT REGISTER I.E., THE PREVIOUS TWO BITS. �- THE PRESENT CONDITION OF THE PREVIOUS TWO BITS IN THE SHIFT REGISTER MAY BE IN FOUR COMBINATIONS. LET THESE COMBINATIONS 00, 10, 01 AND 11 BE CORRESPONDS TO THE STATES A, B, C AND D RESPECTIVELY. �- FOR EACH INPUT MESSAGE BIT, THE PRESENT STATE OF THE M₁ AND M₂ BITS WILL DECIDE THE ENCODED OUTPUT. �- THE LOGIC TABLE PRESENTS THE ENCODED OUTPUT X₁ AND X₂ FOR THE POSSIBLE ‘0’ OR ‘1’ BIT INPUT IF THE PRESENT STATE IS A OR B OR C OR D. �

Solution

MATRUSRI

ENGINEERING COLLEGE

54 of 60

THE STATE OF A CONVOLUTIONAL ENCODER IS DEFINED BY THE CONTENTS OF THE SHIFT REGISTER. THE NUMBER OF STATES IS GIVEN BY 2 ^K-1 = 2^3-1 = 2² = 4. HERE K REPRESENTS THE CONSTRAINT LENGTH. �LET THE FOUR STATES BE A = 00, B = 10, C = 01 AND D = 11 AS PER THE LOGIC TABLE. A STATE DIAGRAM AS SHOWN IN THE FIGURE 3.9 ILLUSTRATES THE FUNCTIONING OF THE ENCODER. �

1. State Diagram Representation

MATRUSRI

ENGINEERING COLLEGE

55 of 60

SUPPOSE IN THE STATE A = 00. �I. AT THIS STATE, IF THE INCOMING MESSAGE BIT IS 0, THE ENCODER OUTPUT IS X = (X₁ X₂) = 00. THEN IF THE M₀, M₁ AND M₂ BITS ARE SHIFTED, THE CONTENTS OF THE SHIFT REGISTER WILL ALSO BE IN STATE A = 00. THIS IS REPRESENTED BY A SOLID LINE PATH STARTING FROM A AND ENDING AT A ITSELF. �II. AT THE ‘A’ STATE, IF THE INCOMING MESSAGE BIT IS 1, THEN THE ENCODER OUTPUT IS X = 11. NOW IF THE M₀, M₁ AND M₂BITS ARE SHIFTED, THE CONTENTS OF THE SHIFT REGISTER WILL BECOME THE STATE B = 10. THIS IS REPRESENTED BY A DASHED LINE PATH STARTING FROM A AND ENDING AT B. �SIMILARLY WE CAN DRAW LINE PATHS FOR ALL OTHER STATES, AS SHOWN IN THE ABOVE FIGURE. �

2. Code tree representation

The code tree diagram is a simple way of describing the encoding procedure. By traversing the diagram from left to right, each tree branch depicts the encoder output codeword.
Figure below shows the code representation for this encoder.

Continued with state diagram representation

MATRUSRI

ENGINEERING COLLEGE

56 of 60

2. Code Tree Representation

MATRUSRI

ENGINEERING COLLEGE

57 of 60

ADVANTAGES OF CONVOLUTIONAL CODES: �- THE CONVOLUTIONAL CODES OPERATE ON SMALLER BLOCKS OF DATA. HENCE DECODING DELAY IS SMALL.�- THE STORAGE HARDWARE REQUIRED IS LESS. ��DISADVANTAGES OF CONVOLUTIONAL CODES:�- DUE TO COMPLEXITY, THE CONVOLUTIONAL CODES ARE DIFFICULT TO ANALYZE. �- THESE CODES ARE NOT DEVELOPED MUCH AS COMPARED TO BLOCK CODES.

Advantages & Disadvantages of Convolutional Codes

MATRUSRI

ENGINEERING COLLEGE

58 of 60

Comparison between

Linear Block codes and Convolutional codes

MATRUSRI

ENGINEERING COLLEGE

Sl. No.	Linear Block Codes	Convolutional Codes
1.	Block codes are generated by X = MG (or) X(p) = M(p) .G(p)	Convolutional codes are generated by convolution between message sequencing and generating sequence.
2.	For a block of message bits, encoded block (code vector) is generated	Each message bit is encoded separately. For every message bit, two or more encoded bits are generated.
3.	Coding is block by block.	Coding is bit by bit.
4.	Syndrome decoding is used for most liklihood decoding.	Viterbi decoding is used for most liklihood decoding.
5.	Generator matrices, parity check matrices and syndrome vectors are used for analysis.	Code tree, code trellis and state diagrams are used for analysis.
6.	Generating polynomial and generator matrix are used to get code vectors.	Generating sequences are used to get code vectors.
7.	Error correction and detection capability depends upon minimum distance dmin.	Error correction and detection capability depends upon free distance dmin.

1 of 60

2 of 60

3 of 60

4 of 60

5 of 60

6 of 60

7 of 60

8 of 60

9 of 60

10 of 60

11 of 60

12 of 60

13 of 60

14 of 60

15 of 60

16 of 60

17 of 60

18 of 60

19 of 60

20 of 60

21 of 60

22 of 60

23 of 60

24 of 60

25 of 60

26 of 60

27 of 60

28 of 60

29 of 60

30 of 60

31 of 60

32 of 60

33 of 60

34 of 60

35 of 60

36 of 60

37 of 60

38 of 60

39 of 60

40 of 60

41 of 60

42 of 60

43 of 60

44 of 60

45 of 60

46 of 60

47 of 60

48 of 60

49 of 60

50 of 60

51 of 60

52 of 60

53 of 60

54 of 60

55 of 60

56 of 60

57 of 60

58 of 60

59 of 60

60 of 60