An Intro To Digital Comms - Part 1

AN INTRODUCTION TO DIGITAL COMMUNICATIONS Part 1 Figure 1 shows the block diagram of a digital communication system.
. In this diagram, three basic signal-processing operations are identified: source coding, channel coding, and odulation. It is assumed that the source of information is digital by nature or converted into it by design ( i.e. sampling, uantising and digital coding into !"# for e$ample%. &he ob'ective of source encoding is to reduce the number of bits transmitted for each message by taking advantage of any redundancy in the message. For e$ample if one can convey a message accurately by transmitting ( bits, then it is inefficient to transmit that same message using ) bits. *sing ) bits increases the number of bits to be transmitted. &o transmit this information, in a certain amount of time, using ) bits instead of ( bits one needs to speed up the transmission. &his increase in transmission speed re uires a wider bandwidth. +s we know bandwidth is a very e$pensive resource, In source coding, the source encoder maps the digital message signal generated at the source output into another signal in digital form. &he mapping is one-to-one (i.e. for each source message there is only one uni ue source encoder output%, and the ob'ective is to eli inate or reduce redundanc! so as to provide an efficient representation of the source output. -ince the source encoder mapping is one-to-one, the source decoder simply performs the inverse mapping and thereby delivers to the destination a reproduction of the original digital source output. &he primary benefit thus gained from the application of source coding is a reduced "and#idth re$uire ent. ( +ll compression techni ues used in transmitting data use some form of source encoding method.% &he ob'ective of channel coding is to reduce the effect of noise on the transmitted signal through the channel. In channel coding, the channel encoder maps the incoming digital signal into a channel input and for the decoder to map the channel output into an output digital signal in such a way that the effect of channel noise is minimised. &hat is, the combined role of the channel encoder and decoder is to %ro&ide 'or relia"le co unication o&er a nois! channel. &his provision is satisfied "! introducing redundanc! to the signal representing the message in a prescribed fashion in the channel encoder (before transmitting it into the channel%, and e$ploiting this redundancy in the channel decoder to reconstruct the original channel encoder input as accurately as possible. &hus, in source coding, we remove redundancy, whereas in channel coding, we introduce controlled redundancy. "learly, we may perform source coding alone, channel coding alone, or include the two in the system. In the latter case, naturally, the source encoding is performed first, followed by channel encoding in the transmitter as illustrated in Figure 1. In the receiver we proceed in the reverse order. channel decoding is performed first, followed by source decoding. /hichever combination is used, the resulting improvement in system performance is achieved at the cost of increasedcircuit comple$ity.
#odulation is performed with the purpose of providing 'or the e''icient trans ission o' the signal o&er the channel. In particular, the modulator (constituting the last stage of the
0. 1egree &elecoms 2 3ecture notes
1451(512
transmitter in Fig. 1% uses digital modulation techni ues such as amplitude-shift keying, fre uency-shift keying, phase-shift keying, or uadarture amplitude modulation. &he demodulator performs the demodulation (the inverse of modulation%, thereby producing a signal that follows the time variations in the channel encoder output (e$cept for the effects of noise%. #odulation in general is a process designed to: -match the properties of the transmitted signal to the channel through the use of a carrier wave. - to reduce the effect of noise and interference - to simultaneously transmit several signals over a single channel - to overcome some e uipment limitations (e.g antennae and 6F circuits% &he combination of modulator, channel, and demoduator, enclosed inside the dashed rectangle shown in Fig. 1, is sometimes called a discrete channel. It is so called since both its input and output signals are in discrete form. &raditionally, channel coding and modulation are performed as separate operations and the introduction of redundant symbols by the channel encoder appears to imply increased transmission bandwidth. In some applications, however, these two operations (channel coding and modulation % are performed as one function in such a way that the transmission bandwidth need not be increased.
Channels 'or Digital Co unications &he details of modulation and coding used in a digital communications system depend on the characteristics of the channel and the application of interest. &wo characteristics, bandwidth and power, constitute primary communication resources available to the designer. In addition to bandwidth, channel characteristics of particular concern are the amplitude and phase responses of the channel and how they affect the signal, whether the channel is linear or non-linear, and how free the channel is from e$ternal interference. &here are si$ specific types of channels used in communications: &elephone channel, coa$ial cables, optical fibres, microwave radio, cellular mobile and satellite channel. &he channel provides the connection between the information source and the user. 6egardless of its type, the channel degrades the transmitted signal in a number of ways. &he degradation is a result of signal distortion due to imperfect response of the channel and due to undesirable electrical signals (noise% and interference. 7oise and signal distortion are two basic problems of electrical communications.
1451(512
1igital -ource
-ource 8ncoder
"hannel 8ncoder #odulator
"ommunications "hannel
NOIS+
1igital *ser
-ource 1ecoder
"hannel 1ecoder 1emodulator
(igure 1 )loc* Diagra
o' a Digital Co
unications S!ste
1451(512
1451(512
+L+M+NTS O( PRO)A)ILIT, T-+OR, Introduction: &he word 9random9 is used to describe apparently unpredictable variations of an observed signal. 6andom signals ( of one sort or another% are encountered in every practical communications system. ( Information carrying signals are unpredictable. noise that perturb information signals is also unpredictable. &hese unpredictable signal and noise waveforms are e$amples of outcome of random processes %. &he e$act value of these random signals cannot be predicted. 7evertheless the received signal can be described in terms of its statistical properties such as its average power, or the spectral distribution of its average power. &he mathematical discipline that deals with the statistical characterisation of random signals is probability theory. !robability theory is also used in measuring information which helps in defining the ideal channel from the point of view of reliable ma$imum information transmission, as well as estimating the probability of transmission error and helping in finding ways to combat the effect of noise in communications and especially in digital transmission. !robability theory is rooted in real-life situations which result in outcomes that cannot be predicted accurately before hand. &hese situations and their outcome are akin to random e$periments. For e$ample the e$periment may be the tossing of a fair coin, in which the possible outcomes of trials are 9heads9 or 9tails9. :y random e$periment is meant one which has the following three features: 1- &he e$periment is repeatable under identical conditions. 4- 0n any trial of the e$periment, the outcome is unpredictable. 2- For a large number of trials of the e$periment, the outcome e$hibits statistical regularity. &hat is, a definite average pattern of outcomes is observed if the e$periment is repeated a large number of times. "onsider an e$periment involving the tossing of a fair coin . 8very time the coin is tossed is considered as an event. "onsider a specific event, +, among all the possible events of the e$periment under consideration ( 9heads9 or 9tails9 in the coin tossing case% . If the e$periment is repeated 7 times during which the event + , ( the occurrence of a 9heads9 for e$ample% has appeared n+ times. &he ratio (n+57% is called the relati&e 're$uenc! of occurrence of the event + . +s 7 becomes large we find that this relative fre uency number converges to the same limit, every time we repeat this e$periment. /hen 7 , the limit of (n+57% (when 7 tends to infinity% is called ( or defined% as the %ro"a"ilit! %.A/ of the event + , i.e. %.A/ 0 lim (
N
nA ) N
&hus we can write : ; n+ 7
or
; n+57 1 <
and 1451(512
0 lim (
N
nA )1 N
or
1 %.A/ 1
-o we can see that the value of the probability p($% of occurrence of any event $ , ranges between =ero and one ( i.e. it is a non-negative real number less than or e ual to 1%, where, p($% > ;, means that the event $ never occurs. and p($% > 1 means the event $ always occurs.
? +lthough the outcome of a random e$periment is unpredictable, there is a statistical regularity about the outcomes. For, e$ample if a coin is tossed a large number of times, about half the times the outcome will be 9heads9, and the remaining half of the times it will be 9tails9. /e may say that the relative fre uency ( and in this case the probability % of the outcome 9heads9 or 9tails9 is one half . 0bserve that if the e$periment is repeated only a small number of times the relative fre uency of an outcome may vary widely from its probability of occurrence. :ecause of the statistical regularit! of the random process, the relative fre uency converges toward the probability when the e$periment is repeated a large number of time@ /e are now ready to make a formal definition of probability. + probability system consists of the following three features: 1- + sample space - of all events (outcomes% 4- +t least one class or set of events + that are subsets of -. 2- + probability p(+% assigned to each event + in the subset + and having the following properties: (i% p(-% > 1 (ii% ; p(+% 1 (iii% if + A : is the union of two utuall! e2clusi&e event in the classes + and : then p(+A:% > p(+% A p(:% !roperties (i% , (ii% , (iii% are known as the a$ioms of probability. +$iom (i% is really the occurrence of every event in the set +$iom (ii% has been e$plained above, +$iom (iii% states that the probability of the union of two mutually e$clusive event is the sum of the probabilities of the individual events. In the ne$t two pages these a$ioms will be e$plained further.
In the definition of a probability system above we used a few terms that need e$planation and definition. &o do this we will use a few simple and basic concepts from what is called -et &heory.
1451(512
/e define the sample space - as the collection of all possible separately identifiable outcomes of a random e$periment. 8ach outcome is an element, or sample point, of this space and can be represented by a point in the sample space. In the random e$periment of rolling a die, for e$ample, the sample space consists of si$ elements represented by si$ sample points s1,s4,s2,s(,s<,sB, where si represents the outcome 9a number i is thrown9 ( see figure 4 % B Ao s 1 s3 s5 Ae s 2 s4 s6 A 6 S
FIG. 2 Sample space for t e t ro! of a "ice &he event, on the other hand is a subset of the sample space -. &he event 9 an odd number is thrown9, denoted by +o , is a subset of - ( or a set of sample points s1, s2, and s< %. -imilarly, the event 9 an even number is thrown9, denoted by +e , is another subset of - ( or a set of sample points s4, s(, and sB %. &hese two events are written as : +o> (s1, s2, s<% and +e > (s4, s(, sB%
3et us denote the event 9 a number e ual to or less than ( is thrown 9 as the set :. thus : > (s1,s4,s2,s(%. 7ote that one outcome can also be an event, because an outcome is also a subset of - with one element in it. For e$ample the event or the outcome 9 a B is thrown 9 is represented by the circle +B as shown in figure 4. &he complement of any event +, denoted by +C, is the event containing all points not in +. &hus for the event : in Figure 4, :C > (s<,sB%, and also +oC > +e. +n event which has no sample point is a null event, which is denoted by and is e ual to -C.
7ow consider two particular events + and : among the events that result from an e$periment. 3et the e$periment be repeated n times. 8ach outcome observed can belong to only one of the following categories: 1- + has occurred but not :, i.e. +:C 4- : has occurred but not +, i.e. +C:
1451(512
2- :oth + and : have occurred, i.e. +: (- 7either + nor : has occurred, i.e. +C:C
A#B# A AB# AB A#B B A (AB#)
A#B# B (A#B)
FIG 2. $enn %ia&ram representin& 'nion an" Intersection of e(ents
FIG 3. $enn %ia&ram representin& )!o *+t+all, -.cl+si(e e(ents
+ set is a collection of items which have a common characteristic. For e$ample the left hand circle shown above denotes the set of events where the e$periment resulted in the occurrence of +. &he right hand circle represents the set showing all the occurrences of :. &he intersection of set + and set : i.e. of the two circles, denoted by A), is the set representing the occurrences of both + and : together, and note that the event +: is the same as the event :+. ( #athematicians use the notation A ) to represent the intersection of sets + and :, which is analogous to the logical +71 operation of digital circuits.% &he union of set + and set :, denoted by A3) , is the set that contains all the elements of + or all the elements of : or both. ( #athematicians use the notation A ) .% &he events + and : are called simple events and the events " > +: and 1 > +A: are called compound or 'oint events since they are functions of simple events which are related or which occur together. &wo events + and : are said to be dis'oint, or utuall! e2clusi&e, if they cannot occur simultaneously i.e. +: > ( for e$ample in figure 4, the events +o and +e are mutually e$clusive %. 3ooking at the above diagram + > +:C +: : > +C: +: + : > +:C +: +C: or or or (+:C A +:% (+C: A +:% + A : > +:C A +: A+C:
If the number of events of each of the categories 1,4,2, and ( listed above, (in the first paragraph of page (% is denoted by n1, n4, n2, n(, then n1A n4A n2A n( > n, the total number of all events. n +n fD+E the relative fre uency of occurrence of + independent of : > 1 3 n n2 + n 3 fD:E the relative fre uency of occurrence of : independent of + > n n fD+ :E the relative fre uency of occurrence of + and : together > 3 n
1451(512
fD+ :E the relative fre uency of occurrence of either + or : or both >
n1 + n2 + n3 n n3 n2 + n3 n3 n1 + n3
fD+G:E the relative fre uency of occurrence of + under condition that : has occurred >
fD:G+E the relative fre uency of occurrence of : under condition that + has occurred >
In the limit when n , fDHE becomes the probability p($% of occurrence of the event $, (as was defined earlier%, thus fD+E p(+% fD:E p(:% fD+:E p(+:% fD+A:E p(+A:% fD+G:E p(+G:% fD:G+E p(:G+%
4oint Pro"a"ilit! 1efinition: &he probability of a 'oint event, +:, is n p(+:% > lim ( AB ) n n where n+: is the number of times that the event +: occurs out of n trials. In addition, two events + and :, are said to be +: never occurs, which implies that p(+:% >; utuall! e2clusi&e if the event
1451(512
&he probability of the union of two events ( i.e. a 'oint event, represented by +A: or + :% may be evaluated by measuring the compound (or 'oint % event directly. or, it may be evaluated by measuring the probabilities of the simple events as given in the following theorem
Theore
: 3et the event 8 be the union of the two events + and : ( +: % i.e. 8 > + A : . then %.+/ 0 %.A3)/ 0 %.A/ 3 %.)/ 5%.A)/
Proo' : 3et the event +-only occur n+ times out of n trials, the event :-only occur n: times out of n trials, and the event +: occur n+: times. &hus p( A + B) = lim (
n
n A + nB + n AB ) n n A + n AB n + n AB n ) + lim ( B ) lim ( AB ) n n n n n
= lim (
n
which is identical to p(8% > p(+% A p(:% - p(+:%, since p( A ) = lim (

n
n A + n AB n + n AB n ) , p(B) = lim ( B ) , and p( AB) = lim ( AB ) n n n n n
(&he proof of this theorem could have been deduced directly from the above Jenn diagram in figure 2.% "onsider the two events + and : of a random e$periment. -uppose we conduct 7 independent trials of this e$periment and events + and : occur in n+ and n: trials, respectively. If + and : are mutually e$clusive (or dis'oint%, then if + occurs, : cannot occur, and vice versa. Kence the event + : occurs in n+A n: trials and n + n: n n n n % = lim( + + : % = lim( + % + lim( : % > p(+% A p(:% p(+ :% > lim( + n n n n n n n n n where in this case the event +: > (+gain the proof could have been deduced directly from the Jenn diagram in figure (.%
&o understand more the probability of mutually e$clusive events, lets consider the coin tossing e$periment. &he outcomes 9heads9 (K% or 9tails9 (&% cannot happen together, they are mutually e$clusive and thus their 'oint probability p(K&%, the probability of a 9head9 and a 9tail9 occurring together is =ero (p(K&% > ;%. &he probability of occurrence of a 9head9 or a 9tail9 i.e. the union of the two events would be e ual to p(K% A p(&% -p(K&% > p(K% A p(&% > 154 A 154 > 1. &his result stands to reason since the outcome of tossing a coin has to be either a 9heads9 or 9tail9. ( assuming the coin doesnLt come to rest on its edge, or gets lost , %
1;
1451(512
+s another e$ample of mutually e$clusive events consider the throwing of one dice. &he probability of occurrence of any number from 1 to B is e ual to p(1% A p(4% A p(2% A p((% A p(<% A p(B% > 15B A 15BA 15B A 15B A15B A15B > B5B >1 &he occurrence of any of these numbers is mutally e$clusive to the occurrence of any other one of these numbers, ( the numbers being 1 to B % and their 'oint probability is =ero.
11
1451(512
Conditional Pro"a"ilit!: &he probability that an event + occurs given that an event : has also occurred is denoted by p(+G:% and is defined by n p( A/B) = lim ( AB ) n nB p(+G:% is read 9 the probability of + given :9. &he probability of the intersection of two events may be evaluated by measuring the compound event directly or it may be evaluated from the probability of either of the simple events and the conditional probability of the other simple event.
Theore : 3et the event 8 be the intersection of the two events + and : i.e. 8 > +:. then %.A)/ 0 %.A/ %.)6A/ 0 %.)/ %.A6)/ Proo'7 p( AB) = lim (
n
n AB )= n =
n A l ar& e
lim (
n AB n A ) = p(B/ A )p( A ) nA n
nBl ar& e
lim (
n AB nB ) = p( A/B)p(B) nB n
1efinition:
&wo events + and : are said to be independent if either p(+G:% > p(+% or p(:G+% > p(:%
It is easy to show that if a set of events +1 ,+4 ,...., +n, are independent. then p(+1 ,+4 ,...., +n% > p(+1% p(+4% .....p(+n% 7ote that for mutually independent events : p(+:% > p(+% p(:% /hen the problem discussed is such that the outcome of each e$periment remain independent of the previous e$periment outcome, in engineering terminology such e$periments (or processes% are said to lack memory. For these e$periments the probability of any outcome is always the same ( i.e. an outcome of the nth trial has e$actly the same probability of occurrence as in the kth trial%. &his type of
14
1451(512
e$periment leads to the concept of so called independent stochastic (or random% processes, and is often called a e or!less %rocess8 In certain types of problems an outcome may be influenced by the past history or 9memory9 of the e$periment. -uch e$periment are termed 9dependent stochastic processes9. &he simplest of these are those e$periments in which the probability of an outcome of a trial depends on the outcome of the i ediate %receding trial. &hese types of e$periments are called 9Mar*o& %rocesses98
12
1451(512
COM)INATIONS If we tossed a coin four times in succession and wanted to determine the probability of obtaining e$actly two heads we might have to list all the 1B possible outcomes to identify the ones we are interests in to count them. ( see problem ( below% &his method of listing all possible outcomes uickly becomes unwieldy as the number of tosses increases. For e$ample, if a coin is tossed 1; times in succession, the total number of outcomes is 4 1; > 1;4(. 0bviously listing all these outcomes is not to be recommended , + more convenient approach would be to use the results of combinatorial analysis. If a coin is tossed k times, the number of ways in which ' heads can occur is the same as the number of combinations of k things taken ' at a time. &his is given by ( ) , where
0 1
( )>
0
12 > 02(1 0)2
C:
&his can be proved as follows. "onsider an urn containing k distinguishable balls marked 1, 4, ....., k. -uppose we draw ' balls from this urn without replacement. the first ball could be any one of the k balls, the second ball could be any one of the remaining (k-1% balls, and so onL Kence the total number of ways in which ' balls can be drawn is k (k-1% (k-4%.........(k-'A1% > k,5(k - '%, 7e$t, consider any one set of the ' balls drawn. &hese balls can be ordered in different ways. /e could choose any one of the ' balls for number 1, and any one of the remaining (' -1% balls for number 4, and so on. &his will give a total of (' -1% (' -4% .....1 > ', distinguishable patterns formed from the ' balls. &he total number of ways in which ' things can be taken from k things is k,5(k-'%,. but many of these ways will use the same ' things, but arranged in different order. &he ways in which things can be taken from k things without regard to order is k,5(k-'%, divided by ', . &his precisely ( ) .
0 1
&hus the number of ways in which two heads can occur in four tosses is 1 42 ( )= =6 22 2 2 0
1(
1451(512
Pro"le s: 1+ssign probabilities to each of the si$ outcomes in Figure 1. ? :ecause each of the si$ outcomes is e ually likely in a large number of independent trials, each outcome will appear in one-si$th of the trials . Kence p(si% > 15B for i > 1, 4, 2, (, <, B.@ 4+ssign probabilities to the events +e, +o, :, +e:, and +o:, in figure 1 ? :ecause +e > (s4 s( sB% where s4, s(, and sB are mutually e$clusive, p(+e% > p(s4% A p(s(% A p( (sB% > 15B A 15B A 15B > 154 , similarly p(+o% > 154 and p(:% > 452 +e: > (s4 s(% , and p(+e:% > p(s4% A !(s(% > 152, similarly p(+o:% > 152@ 2/hat is the probability of an even integer showing on a% a roll of one honest die M b% the sum of two honest dice M c% what would you e$pect from the sum of three honest diceM ?+nsr 154 , 154, 154.@ &wo dice are thrown together. 1etermine the probability that a seven is thrown. ? For this e$periment, the sample space contains 2B sample points because 2B possibl outcome e$ist. +ll the outcome are e ually likely. Kence the probability of each outcome is 152B. + sum of seven can be obtained by the si$ combinations : (1, B%, (4, <%, (2, (%, ((, 2%, (<, 4%, (B, 1%. Kence the event 9 a seven is thrown9 is the union of si$ outcomes, each with probability 152B . &herefore p(9a seven is thrown9% > 152B A 152B A 152B A 152B A 152B A 152B > 15B.@ /e can also consider the solution in the following manner: If we say that out of the possible 2B outcomes B outcomes will give us the 9seven9. &hen the 9seven9 will occur <52B of the time in many repeated e$periments . <In the above problem what is the probability of getting a si$ when the two dice are thrownM ( ansr: <52B% B)"heck that p(4% > 152B , p(2% > 452B , p((% > 252B, p(<% > (52B etc.... and that p(4% A p(2% A p((% A p(<% A ..........A p(11% A p(14% > 1 &wo coins are tossed. /hat is the probability of one head and one tail M ? &hrer are ( possiblre outcomes: K,K . K,& . &,K . &,& . 8ach outcome is e ually likely and has a probability of 15( of occurring. Kead-tail can occur in two ways if no distinction is made as to which coin turns up head. -o p(of one head and one tail%% > p(K,&% A p(&,K% > 15( A 15( > 154 ( i.e the union of two events which are mutually e$clusive %
(-
1<
1451(512
F-
+ coin is tossed four times in succession. 1etermine the probability of obtaining e$actly two heads.
? -ince each toss has two possible outcomes only i.e. a heads (K% or a tails (&%, then a total of 4 ( > 1B distinct outcomes are possible ( remember the number of all possible combinations of a four digit binary code %, all of which are e ually likely. Kence the sample space consists of 1B points, each with probability 151B. &he si$teen outcomes are listed below. &&&& &&&K &&K& &&KK &K&& &K&K &KK& &KKK K&&& K&&K K&K& K&KK KK&& KK&K KKK& KKKK
-i$ out of these outcomes are favourable to the event 9obtaining two heads9 (denoted by arrows% . :ecause all of these si$ outcomes are mutually e$clusive (dis'oint%. p(9 obtaining two heads9% > B51B > 25F@ F+ long binary message contains 1(4B binary 1Ls and 4BBF binary ;Ls. /hat is the probability of obtaining a binary 1 in any received bitM ( ansr: ;.2(F2% +n urn containing two white balls and three black balls. &wo balls are drawn in succession, the first one not being replaced. /hat is the chance of picking two white balls in successionM (ansr: 151;% again we can solve this problem in several ways: a% &here are 4; different permutations of 4 things out of <. ( we can write them down in this case- by giving the balls w w b b b numbers 1 4 2 ( < - although it is tedious, but a better way of knowing that there are 4; permutations is to use the permutation formula%. &wo of these permutations will have two white balls. &hus the probability of getting two white balls is e ual to the probability of getting either one of these two permutations which is 154; A 154; >151; . ( 8ach one of the 4; permutations is e ually likely and also they are all mutually e$clusive.% b% &he probability of drawing two white balls > the probab. of drawing white ball1 then white ball4 A the probab. of drawing white ball4 then white ball1 i.e p(w or w% > p(w1 w4% A p(w4 w1% but p(w1 w4 % > p(w1% p(w4Gw1% > (15<% (15(% > 154; similarly p(w4 w1% > 154; so p(w w% > 154; A 154; > 151; c% p(w w% > > p(w1% p(w4Gw1% (45<% ( 15(% > 151; 1B 1451(512
I-
1;-
&wo urns contain white and black balls. *rn + contains two black balls and one white ball. urn : contains three black balls and two white balls. 0ne of the urns is selected at random,and and one of the balls in it is chosen. /hat is the probability p(/% of drawing a white ballM &here are two ways of drawing one white ball: a% pick urn + . draw / b% pick urn : . draw / &hese two events are mutually e$clusive, so p(/% > p(+ /% A p(:/% but p(+ /% > p(+% p(/G+% > (154% ( 152% > 15B and p(: /% > p(:% p(/G:% > (154% (45<% > 15< -o p(/% > 15B A 15< > 1152;
1)
1451(512
1F
1451(512
IN(ORMATION T-+OR, Information theory deals with mathematical modelling and analysis of a communications system rather than with physical sources and physical channels. -pecifically, given an information source and a noisy channel, information theory provides limits on : 1- &he minimum number of bits per symbol re uired to fully represent the source. (i.e. the efficiency with which information from a given source can be represented.% 4- &he ma$imum rate at which reliable (error-free% communications can take place over the noisy channel. -ince the whole purpose of a communications system is to transport information from a source to a destination, the uestion arises as to how much information can be transmitted in a given time. ( 7ormally the goal would be to transmit as much information as possible in as small a time as possible such that this information can be correctly interpreted at the destination.% &his of course leads to the ne$t uestion, which is : Kow can information be measured and how do we measure the rate at which information is emitted from a source M -uppose that we observe the output emitted by a discrete source ( every unit interval or signalling interval.% &he source output can be considered as a set, -, of discrete random events ( or outcomes%. &hese events are symbols from a fi$ed finite alphabet. ( for e$ample the set or alphabet can be the numbers 1 to B on a die and each roll of the die outputs a symbol being the number on the die upper face when the die comes to rest. +nother e$ample is a digital binary source, where the alphabet is the digits 9;9 and 919, and the source outputs a symbol of either 9;9 or 919 at random .% If in general we consider a discrete random source which outputs symbols from a fi$ed finite alphabet which has k symbols. &hen the set - contains all the k symbols and we can write - > D s; , s1 , s4 , ......., sk-1 E
i = ( k 1% i=;
and (2.1%
p ( si % = 1
In addition we assume that the symbols emitted by the source during successive signalling intervals are statisticall! inde%endent i.e. the probability of any symbol being emitted at any signalling interval does not depend on the probability of occurrence of previous symbols. i.e. we have what is called a discrete e or!less source. "an we find a measure of how much 9information9 is produced by this source M &he idea of information is closely related to that of 9uncertainty9 and 9surprise9.
If the source emits an output si, which has a probability of occurrence p(si% > 1, then all other symbols of the alphabet have a =ero probability of occurrence and there is really no 9uncertainty9, 9surprise9, or information since we already know before hand ( a %rior! % what the output symbol will be.
1I
1451(512
If on the other hand the source symbols occur with different probabilities, and the probability p(s i% is low, then there is more 9uncertainty9, 9surprise9 and therefore 9information9 when the symbol si is emitted by the source, rather than another one with higher probability. &hus the words 9uncertainty9, 9surprise9, and 9information9 are all closely related. - :efore the output si occurs, there is an amount of 9uncertainty9. - /hen the output si occurs, there is an amount of 9surprise9. - +fter the occurrence of the output si, there is gain in the amount of 9information9. +ll three amounts are really the same and we can see that the amount of information is related to the inverse of the probability of occurrence of the symbol. De'inition : &he amount of information gained after observing the event si which occurs with probability p(si%, is
1 I.s /= log = < i > %.s / i
"its,
for i > ;,1,4, ..., (k-1%
(2.4%
&he unit of information is called 9"it9 , a contraction of 9binary digit9 &his definition e$hibits the following important properties that are intuitively satisfying: 1- I (si% > ; for p(si% > 1
i.e. if we are absolutely certain of the output of the source even before it occurs (a priory%, then there is no information gained. 4- I(si% ; because ; p(si% 1 for symbols of the alphabet. i.e. the occurrence of an output s' either provides some information or no information but never brings about a loss of information ( unless it is a severe blow to the head which is highly unlikely from the discrete source ,% 2- I(s'% I(si% for p(s'% p(si% i.e. the less probability of occurrence an output has the more information we gain when it occurs. (- I(s'si% > I(s'% A I(si% if the outputs s' and si are statistically independent.
&he use of the logarithm to the base 4 ( instead of to the base 1; or to the base e % has been adopted in the measure of information because usually we are dealing with digital binary sources, (however it is useful to remember that log>.a/ 0 ?8?>> log11.a/ %. &hus if the source alphabet was the binary set of
4;
1451(512
symbols, i.e. 9;9 or 919 , and each symbol was e ually likely to occur i.e. s; having p(s;% > 154 and s1 having p(s1% > 154 we have :
1 1 I(s %= log ? @> log 4 ? @= log 4 ( 4%= 1 i 4 p(s % 1 4 i
bit
Kence 9one bit9 is the amount of information that is gained when one of two possible and e$uall! li*el! .e$ui%ro"a"le/ outputs occurs. ?7ote that a 9bit9 is also used to refer to a binary digit when dealing with the transmission of a se uence of 1Ls and ;Ls@. &he amount of information , I(si%, associated with the symbol si emitted by the source during a signalling interval depends on the symbolLs probability of occurrence. In general, each source symbol have a different probability of occurrence. -ince the source can emit any one of the symbols of its alphabet, a measure for the a&erage in'or ation content %er source s! "ol was defined and called the entro%! o' the discrete source , -@ (i.e. taking all the discrete source symbols into account %. De'inition &he entro%!, K, of a discrete memoryless source with source alphabet composed of the set - > D s; , s1 , s4 , ......., sk-1 E, is a measure of the a&erage in'or ation content %er source s! "ol, and is given by :
- = =
i= .* 1/ i= 1
%.s
i
/I.s i / 1 < %.s i /
i= .* 1/ i= 1
%.s
/log > =
"itsAs! "ol
(2.2%
/e note that the entropy, K, of a discrete memoryless source with e uiprobable symbols is bounded as follows: ; K log 4 k , where k is the number of e uiprobable source symbols. Furthermore, we may state that : 1- K > ; , if and only if the probability p(si% > 1 for some symbol si , and the remaining source symbols probabilities are all =ero. &his lower bound on entropy corresponds to no uncertainty and no information. 4- - 0 log> * bits5symbol, if and only if p(si% > 15k for all the k source symbols (i8e8 the! are all e$ui%ro"a"le%. &his upper bound on entropy corresponds to ma$imum uncertainty and ma$imum information.
+2a %le7 "alculate the entropy of a discrete memoryless source with source alphabet - > D s; , s1 , s4 E with probabilities p(s;% > 15( , p(s1% > 15(, p(s2% > 154 .
41
1451(512
-= =
i = .* 1/ i=1
%.si / I.si /
1
i/
i = .* 1/ i =1
%.si / log > = %.s
<
K = p(s; % log 4 ? >
1 1 1 @ A p(s1 % log 4 ? @ A p(s4 % log 4 ? @ p(s; % p(s1 % p(s4 %
1 1 1 2 log 4 ( (% + log 4 ( (% + log 4 ( 4% = = 1. < bits 5 symbol ( ( 4 4
In'or ation Rate

If we consider that the symbols are emitted from the source at a fi$ed time rate (the signalling interval%, denoted by rs symbols5second. /e can define the a&erage source in'or ation rate R in bits per second as the product of the average information content per symbol, K, and the symbol rate rs. R 0 rs "itsAsec (2.(%
+2a %le + discrete source emits one of five symbols once every millisecond. &he source symbols probabilities are 154, 15(, 15F, 151B, and 151B respectively. Find the source entropy and information rate.
i = .* 1/ i=1
-=
%.si / log >= %.si / <
bits
where, in this case k > <
K = p(s; % log 4 ? >
1 1 1 1 1 @ A p(s1 % log 4 ? @ A p(s4 % log 4 ? @ A p(s2 % log 4 ? @ A p(s( % log 4 ? @ p(s; % p(s1 % p(s4 % p(s2 % p(s( %
1 1 1 1 1 log 4 ( 4% + log 4 ( ( % + log 4 (F% + log (1B% + log 4 (1B% 4 ( F 1B 4 1B
= ;. < + ;. < + ;. 2)< + ;. 4< + ;. 4< = 1. F)< bits 5 symbol
R 0 rs - bits5sec &he information rate 6 > (151;-2 % $ 1.F)< > 1F)< bits5second. +ntro%! o' a )inar! Me or!less Source: &o illustrate the properties of K, let us consider a memoryless digital binary source for which symbol ; occurs with probability p; and symbol 1 with probability p1 > (1 - p;%.
44
1451(512
&he entropy of such a source e uals:

K = p ; log 4 ? 1 1 @ A p 1 log 4 ? @ p; p1 1 1 @ A (1 - p ; % log 4 ? @ bits p; (1 - p ; %
= p ; log 4 ?
/e note that 1- /hen p; > ;, the entropy K > ;. &his follows from the fact that $ log $ ; as $ ;. 4- /hen p;> 1, the entropy K > ;. 2- &he entropy K attains its ma$imum value, Kma$ > 1 bit, when p; > p1 >154, that is symbols ; and 1 are e ually probable. (i.e. K > log4 k > log4 4 > 1 % ( Kma$ > 1 can be verified by differentiating K with respect to p and e uating to =ero %
42
1451(512
4(
1451(512
C-ANN+L CAPACIT, In Information &heory, the transmission medium is treated as an abstract and noisy filter called the channel. &he limiting rate of information transmission through a channel is called the channel capacity, ".
Channel Coding Theorm

-hannon showed that, if the information rate 6 ?remember that R 0 rs - bits5sec@ is e ual to or less than ", R C , then there e$ists a coding techni ue which enables transmission over the noisy channel with an arbitrarily small fre uency of errors. ?+ converse to this theorem states that it is not possible to transmit messages without error if 6N"@
&hus the channel capacity is defined as the ma$imum rate of reliable (error-free% information transmission through the channel.
7ow consider a binary source with an available alphabet of k discrete messages (or symbols% which are e uiprobable and statistically independent (these messages could be either single digit symbols or could be composed of several digits each depending on the situation%. /e assume that each message sent can be identified at the receiver. therefore this case is often called the Odiscrete noiseless channelP. &he ma$imum entropy of the source is log4 k bits, and if & is the transmission time of each message, (i.e. rs > is
C = R = rs H = rs log 4 k
1 symbols5sec%, the channel capacity T
"its %er second8
&o attain this ma$imum the messages must be e uiprobable and statistically independent. &hese conditions form a basis for the coding of the information to be transmitted over the channel. In the presence of noise, the capacity of this discrete channel decreases as a result of the errors made in transmission. In making comparisons between various types of communications systems, it is convenient to consider a channel which is described in terms of bandwidth and signal-to-noise ratio.
Review of Signal to Noise Ratio &he analysis of the effect of noise on digital transmission will be covered later on in this course but before proceeding, we will review the definition of signal to noise ratio. It is defined as the ratio of signal power to noise power at the same point in a system. It is normally measured in decibels.
4<
1451(512
Signal to Noise Ratio .d)/ 0 1; log1;
S N
d)
7oise is any unwanted signal. In electrical terms it is any unwanted introduction of energy tending to interfere with the proper reception and reproduction of transmitted signals.
Channel Capacity Theorm

:it error and signal bandwidths are of prime importance when designing a communications system. In digital transmission systems noise may change the value of the transmitted digit during transmission. (e.g. change a high voltage to a low voltage or vice versa%. &his raises the uestion : Is it possible to invent a system with no bit error at the output even when we have noise introduced into the channelM -hannonQs Channel Ca%acit! Theor (also called the the Shannon 5 -artle! Theor % answers this uestion
C 0 ) log> .1 3 SAN/
"its %er second,
where " is the channel capacity, : is the channel bandwidth in hert= and -57 is the signalto-noise power ratio (watts5watts, not d:%.
+lthough this formula is restricted to certain cases (in particular certain types of random noise%, the result is of widespread importance to communication systems because many channels can be modelled by random noise. From the formula, we can see that the channel capacity, ", decreases as the available bandwidth decreases. " is also proportional to the log of (1A-57%, so as the signal to noise level decreases " also decreases. &he channel capacity theorem is one of the most remarkable results of information theory. In a single formula, it highlights most vividly the interplay between three key system parameters: "hannel bandwidth, average transmitted power (or, e uivalently, average received power%, and noise at the channel output. &he theorem implies that, for given average transmitted power - and channel bandwidth :, we can transmit information at the rate " bits per seconds, with arbitrarily small probability of error by employing sufficiently comple$ encoding systems. It is not possible to transmit at a rate higher than " bits per second by any encoding system without a definite probability of error. Kence, the channel capacity theorem defines the fundamental limit on the rate of errorfree transmission for a power-limited, band-limited Raussian channel. &o approach this limit, however, the noise must have statistical properties appro$imating those of white Raussian noise.
Pro"le s7
1. + voice-grade channel of the telephone network has a bandwidth of 2.( kK=. (+% "alculate the channel capacity of the telephone channel for a signal-to-noise ratio of 2; d:.
4B
1451(512
(:% "alculate the minimum signal-to-noise ratio re uired to support information transmission through the telephone channel at the rate of (F;; bits5sec. ("% "alculate the minimum signal-to-noise ratio re uired to support information transmission through the telephone channel at the rate of IB;; bits5sec.(8H+#:SanI<% 4. +lphanumeric data are entered into a computer from a remote terminal through a voicegrade telephone channel. &he channel has a bandwidth of 2.( kK=, and output signal-to-noise ratio of 4; d:. &he terminal has a total of 14F symbols. +ssume that the symbols are e uiprobable, and the successive transmission are statistically independent. (+% "alculate the channel capacity. (:% "alculate the ma$imum symbol rate for which error-free transmission over the channel is possible. (8H+#: #ay 1II<% 2. + black-and-white television picture may be viewed as consisting of appro$imately 2 $ 1;< elements, each one of which may occupy one 1; distinct brightness levels with e ual probability. +ssume (a% the rate of transmission is 2; picture frames per second, and (b% the signal-to-noise ratio is 2; d:. *sing the channel capacity theorem, calculate the minimum bandwidth re uired to support the transmission of the resultant video signal. (. /hat is the minimum time re uired for the facsimile transmission of one picture over a standardtelephone circuitM &here are about 4.4< $ 1;B picture elements to be transmitted and 14 brightness levels are to be used for good reproduction. +ssume all brightness levels are e uiprobable. &he telephone circuit has a 2-kK= bandwidth and a 2;-d: signal-to-noise ratio (these are typical parameters%.
4)
1451(512
The )inar! S!
etric Channel
*sually when a 919 or a 9;9 is sent it is received as a 919 or a 9;9, but occasionally a 919 will be received as a 9;9 or a 9;9 will be received as a 919. 3etLs say that on the average 1 out of 1;; digits will be received in error, i.e. there is a probability p > 151;; that the channel will introduce an error. &his is called a :inary -ymmetric "hannel ()SC%, and is represented by the following diagram. 0 (1-p) p p 1 (1-p) 1 0
Representation of the Binary Symmetric Channel with an error probability of p 7ow let us consider the use of this :-" odel . -ay we transmit one information digit coded with a single even parity bit . &his means that if the information digit is ; then the codeword will be ;; , and if the information digit is a 1 then the codeword will be 11. +s the codeword is transmitted through the channel, the channel may (or may not% introduce an error according to the following error patterns: 8 > ;; i.e. no errors 8 > ;1 i.e. a single error in the last digit 8 > 1; i.e. a single error in the first digit 8 > 11 i.e. a double error &he probability of no error , is the probability of receiving the second transmitted digit correctly on condition that the first transmitted digit was received correctly. Kere we have to remember our discussion on 'oint probability: p(+:% > p(+% p(:5+% > p(+% p(:% when the occurrence of any of the two outcomes is independent of the occurrence of the other. &hus the probabilty of no error is e ual to the probability of receiving each digit correctly. &his probability, according to the :-" model, is e ual to (1 - p%, where p is the probability of one digit being received incorrectly. &hus the probability of no error > (1 - p% ( 1- p% > (1 - p%4 . -imilarly, the probability of a single error in the first digit > p ( 1- p% and the probability of a single error in the second digit > (1 - p% p , i.e. the probability of a single error is e ual to the sum of the above two probabilities ( since the two events are mutually e$clusive%, i.e. the probability of a single error ( when a code with block length, n > 4 , is used, as in this case% is e ual to 4 p(1 - p% -imilarly the probability of a double error in the above e$ample ( i.e. the error pattern 8 > 11 % is e ual to p4 . In summary these probabilities would be
4F
1451(512
p(8 > ;;% p(8 > ;1% p(8 > 1;% p(8 > 11%
> > > >
(1 - p% (1 - p% p p (1 - p% p4 .
and if we substitute for p > .;1 ( given in the above e$ample% we find that p(8 > ;;% > (1 - p% > ;.II p(8 > ;1% > (1 - p% p > ;.;;II p(8 > 1;% > p (1 - p% > ;.;;II p(8 > 11% > p4 > ;.;;;1 &his shows that if p T 154 , then the probability of no error is higher than the probability of a single error occurring which in turn is higher than the probability of a double error. +gain, if we consider a block code with block length n > 2 , then the probability of no error p(8 > ;;;% > (1 - p%2 , probability of an error in the first digit p(8 > 1;;% > p (1 -p%4 , probability of a single error per codeword p(1e% > 2 p (1 -p% 4 , 4 4 probability of a double error per codeword > p(4e% > ( 2 4 % p (1 - p% > 2 p (1 - p% probability of a triple error per codeword > p(2e% > p2 . +nd again, if we have a code with block length n > (, then the probability of no error p(8 > ;;;;% > (1 - p%( , probability of an error in the first digit p(8 > 1;;;% > p (1 -p%2 , probability of a single error per codeword p(1e% > ( p (1 -p% 2 , 4 4 4 4 probability of a double error per codeword > p(4e% > ( ( 4 % p (1 - p% > B p (1 - p% 2 2 probability of a triple error per codeword > p(2e% > ( ( 2 % p (1 - p% > ( p (1 - p% probability of four errors per codeword > p((e% > p( . +nd again, if we have a code with block length n > <, then the probability of no error p(8 > ;;;;;% > (1 - p%< , probability of an error in the first digit p(8 > 1;;;;% > p (1 -p%( , probability of a single error per codeword p(1e% > < p (1 -p% ( , 4 4 4 4 probability of a double error per codeword > p(4e% > (< 4 % p (1 - p% > 1; p (1 - p% 2 4 2 4 probability of a triple error per codeword > p(2e% > (< 2 % p (1 - p% > 1; p (1 - p% ( ( probability of four errors per codeword > p((e% > (< ( % p (1 - p% > < p (1 - p%. probability of five errors per codeword > p(<e% > p<. From all of the disscussion, we realise that if the error pattern ( of length n % has weight of say $ then the probability of occurrence of 2 errors in a codeword with blocklength n is $ n-$ . (n $ % p (1 - p% /e also realise that, since p T 154 , we have (1 - p% p, and (1 - p%n p (1 - p%n-1 p4 (1 - p%n-4 ............... &herefore an error pattern of weight 1 is more likely to occur than an error pattern of weight 4., and so on
4I
1451(512
source
8ncoder
1ecoder
user
&he "ommunications -ystem from the channel "oding &heorem point of view
2;
1451(512
C-ANN+L CODING -uppose that we wish to transmit a se uence of binary digits across a noisy channel. If we send a one, a one will probably be received. if we send a =ero, a =ero will probably be received. 0ccasionally, however, the channel noise will cause a transmitted one to be mistakenly interpreted as a =ero or a transmitted =ero to be mistakenly interpreted as a one. +lthough we are unable to prevent the channel from causing such errors, we can reduce their undesirable effects with the use of coding. &he basic idea, is simple. /e take a set of k in'or ation digits which we wish to transmit, anne$ to them r chec* digits, and transmit the entire block of n > k A r channel digits. +ssuming that the channel noise changes sufficiently few of these transmitted channel digits, the r check digits may provide the receiver with sufficient information to enable it to detect and5or correct the channel errors. (&he detection and5or correction capability of a channel code will be discussed at some length in the following pages.% Riven any particular se uence of k message digits, the transmitter must have some rule for selecting the r check digits. &his is called channel encoding. +ny particular se uence of n digits which the encoder might transmit is called a code#ord. +lthough there are 4n different binary se uences of length n, only 4k of these se uences are codewords, because the r check digits within any codeword are completely determined by the k information digits. &he set consisting of these 4k codewords, of length n each, is called a code (some times referred to as a code book.% 7o matter which codeword is transmitted, any of the 4n possible binary se uences of length n may be received if the channel is sufficiently noisy. Riven the n received digits, the decoder must attempt to decide which of the 4k possible codewords was transmitted. Re%etition codes and single5%arit!5chec* codes +mong the simplest e$amples of binary codes are the repetition codes, with k > 1, r arbitrary, and n > k A r > 1 A r . &he code contains two codewords, the se uence of n =eros and the se uence of n ones. /e may call the first digit the information digit. the other r digits, check digits. &he value of each check digit (each ; or 1% in a repetition code is identical to the value of the information digit. &he decoder might use the following rule: "ount the number of =eros and the number of ones in the received bits. If there are more received =eros than ones, decide that the all-=ero codeword was sent. if there are more ones than =eros, decide that the all-one codeword was sent. If the number of ones e ual the number of =eros do not decide ('ust flag the error%.. &his decoding rule will decode correctly in all cases when the channel noise changes less than half the digits in any one block. If the channel noise changes e$actly half of the digits in any one block, the decoder will be faced with a decoding 'ailure (i.e. it will not decode the received word into any of the possible transmitted codewords% which could result in an +6U (automatic re uest to repeat the message%. If the channel noise changes more than half of the digits in any one block, the decoder will commit a decoding error. i.e. it will decode the received word into the wrong codeword. If channel errors occur infre uently, the probability of a decoding failure or a decoding error for a repetition code of long block length is very small indeed. Kowever repetition codes are not very useful. &hey have only two codewords and have very low in'or ation rate R 0 *An ( also called code rate%,all but one of the digits are check digits. /e are usually more interested in codes which have a higher in'or ation rate. 8$treme e$amples of such very high rate codes which use a single5%arit!5chec* digit. &his check digit is taken to be the modulo-4 sum (8$clusive-06% of the codeword (n -1% information digits. ( &he information digits are added according to the e$clusive-06 binary operation : ; A ; > ; , ; A 1 > 1, 1 A ; > 1, 1 A 1 > ; %. If the number of ones in the information word is even the modulo-4 sum of all
21
1451(512
the information digits will be e ual to =ero, If the number of ones in the information word is odd their modulo-4 sum will be e ual to one. +&en %arit! means that the total number of ones in the codeword is even, odd %arit! means that the total number ones in the codeword is odd. +ccordingly the parity bit (or digit% is calculated and appended to the information digits to form the codeword. &his type of code can only detect errors. + single digit error (or any number of odd digit errors% will be detected but any combination of two digit errors (or any number of even digit errors% will cause a decoding error. &hus the single-parity-check type of code cannot correct errors. &hese two e$amples, the repetitive codes and the single-parity-check codes, provide the e$treme, relatively trivial, cases of binary block codes. ( +lthough relatively trivial single-parity-checks are used uite often because they are simple to implement.% &he repetition codes have enormous error-correction capability but only one information bit per block. &he single-parity-check codes have very high information rate but since they contain only one check digit per block, they are unable to do more than detect an odd number of channel errors. &here are other codes which have moderate information rate and moderate error-correction5detection capability, and we will study few of them. &hese codes are classified into two ma'or categories: :lock codes , and "onvolutional codes. In "loc* codes, a block of k information digits is encoded to a codeword of n digits (n N k%. For each se uence of k information digits there is a distinct codeword of n digits. In con&olutional codes, the coded se uence of n digits depends not only on the k information digits but also on the previous 7 - 1 information digits (7 N 1%. Kence the coded se uence for a certain k information digits is not uni ue but depends on 7 - 1 earlier information digits. In block codes, k information digits are accumulated and then encoded into an n-digit codeword. In convolutional codes, the coding is done on a continuous, or running, basis rather than by accumulating k information digits. /e will start by studying block codes. (and if there is time we might come back to study convolutional codes%.
)LOC; COD+S &he block encoder input is a stream of information digits. &he encoder segments the input information digit stream into blocks of * information digits and for each block it calculates a number of r check digits and outputs a codeword of n digits, where n 0 * 3 r (or r > n - k%. &he code efficiency (also known as the code rate % is k5n. -uch a block code is denoted as an .n@*/ code. :lock codes in which the k information digits are transmitted unaltered first and followed by the transmission of the r check digits are called s!ste atic codes, as shown in figure 1 below. -ince systematic block codes simplify implementation of the decoder and are always used in practice we will consider only systematic codes in our studies. ( + non-systematic block code is one which has the check digits interspersed between the information digits. For 3inear block codes it can be shown that a non systematic block code can always be transformed into a systematic one%.
24
1451(512
31 32 ..................................... 31
1 information "i&its
..........
3n41 3n
r c ec1 "i&its
Fi&+re 1 an (n51) 6loc1 co"e!or" in s,stematic form
LIN+AR )LOC; COD+S 3inear block codes are a class of parity check codes that can be characteri=ed by the (n, k% notation described earlier. &he encoder transforms a block of k information digits (an information word% into a longer block of n codeword digits, constructed from a given alphabet of elements. /hen the alphabet consists of two elements (; and 1%, the code is a binary code comprised of binary digits (bits%. 0ur discussion of linear block codes is restricted to binary codes. +gain, the k-bit information words form 4k distinct information se uences referred to as *5tu%les (se uences of k digits%. +n n-bit block can form as many as 4n distinct se uences, referred to as n5tu%les. &he encoding procedure assigns to each of the 4k information k-tuples one of the 4n n-tuples. + block code represents a one-to-one assignment, whereby the 4k information k-tuples are uni uely mapped into a new set of 4k codeword n-tuples. the mapping can be accomplished via a look-up table, or via some encoding rules that we will study shortly. De'inition: +n (n, k% binary block code, is said to be linear if, and only if, the modulo-4 addition (Ci C:% of any two codewords, Ci and C: , is also a codeword. &his property thus means that (for linear block code% the all-=ero n-tuple ust be a member of the code book (because the modulo-4 addition of a codeword with itself results in the all-=ero n-tuple%. + linear block code, then, is one in which n-tuples outside the code book cannot be created by the modulo-4 addition of legitimate codewords (members of the code book%. For e$ample, the set of all 4( > 1B, (-tuples (or (-bit se uences % is shown below: ;;;; ;;;1 ;;1; ;;11 ;1;; ;1;1 ;11; ;111 1;;; 1;;1 1;1; 1;11 11;; 11;1 111; 1111 an e$ample of a block code ( which is really a subset of the above set % that forms a linear code is ;;;; ;1;1 1;1; 1111 It is easy to verify that the addition of any two of these ( code words in the code book can only yield one of the other members of the code book and since the all-=ero n-tuple is a codeword this code is a linear binary block code.
22
1451(512
Figure <. 12 illustrates, with a simple geometric analogy, the structure behind linear block codes. /e can imagine the total set comprised of 4n n-tuples. /ithin this set (also called vector space% there e$ists a subset of 4k n-tuples comprising the code book . &hese 4k codewords or points , shown in bold 9sprinkled9 among the more numerous 4n points, represent the legitimate or allowable codeword assignments.
+n information se uence is encoded into one of the 4k allowable codewords and then transmitted. :ecause of noise in the channel, a corrupted version of the sent codeword (one of the other 4n n-tuples in the total n-tuple set% may be received. &he ob'ective of coding is that the decoder would be able to decide whether the received word is a valid codeword, or whether it is a codeword which has been corrupted by noise ( i.e. detect the occurrence of one or more errors %. Ideally of course the decoder should be able to decide which codeword was sent even if this transmitted codeword was corrupted by noise, and this process is calld error5correction. :y thinking about it, if one is going to attempt to correct errors in a received word represented by a se uence of n binary symbols, then it is absolutely essential not to allow the use of all 4 n n-tuples as being legitimate codewords. If, in fact, every possible se uence of n binary symbols were a legitimate codeword, then in the presence of noise one or more binary symbols could be changed, and one would have no possible basis for determining if a received se uence was any more valid than any other se uence. "arrying this thought a little further, if one wished that the coding system would correct the occurrence of a single error, then it is both necessary and sufficient that each codeword se uence di''ers from every other codeword in at least ? positions. 2( 1451(512
In fact, if one wished that the coding system would correct the occurrence of e errors, then it is both necessary and sufficient that each codeword se uence di''ers from every other codeword in at least (4e + 1% positions. D+(INITION &he number of positions in which any two codewords differ from each other is called the -a distance, and is normally denoted by d . For e$ample: 3ooking at the (n,k% > ((,4% binary linear block code, mentioned earlier, which has the following codewords: C1 ;;;; C> ;1;1 C? 1;1; CB 1111 we see that the Kamming distance, d, : between C> and C? is e ual to ( between C> and CB is e ual to 4 between C? and CB is e ual to 4 /e also observe that the Kamming distance between "1 and any of the other codewords is e ual to the 9#eight9 that is the nu "er o' ones in each of the other codewords. /e can also see that the ini u -a ing distance ( i.e. the smallest Kamming distance between any pair of the codewords%, denoted by d in , of this code is e ual to 4 ( &he minimum Kamming distance of a binary linear block code is simply e ual to the minimum weight of its codewords. &his is due to the fact that the code ois linear, meaning that if any two codewords are added together modulo-4 the result will be another codeword. thus to find the minimum Kamming distance of a linear block code all we need to do is to find the minimum weight code%. 3ooking at the above code again, and keeping in mind what we said earlier about the 9Kamming distance9 property of the codewords for a code to correct a single error. /e said that, to correct a single error, this code must have any of its codewords differing from any of the other codewords by at least (4e A 1%, where e in our case is 1 (i.e. a single error%. &hat is the minimum Kamming distance of the code must be at least 2. &herefore the above mentioned code cannot correct the result of occurrence of a single error, (since its dmin > 4%, but it can detect it. &o e$plain this further let us consider the following diagram in figure ing
2<
1451(512
C1
C2
a) 7ammin& sp ere of ra"i+s e 8 1 aro+n" eac co"e!or" 7ammin& "istance 6et!een co"e!or"s 8 3 3o"e can correct a sin&le error since " 8 2e 9 1
C1
C2
6) 7ammin& sp ere of ra"i+s e 8 1 aro+n" eac co"e!or" 7ammin& "istance 6et!een co"e!or"s 8 2 3o"e can onl, "etect e 8 1 error 6+t cannot correct it 6eca+se " 8 e 9 1 ( i.e. " : 2e 9 1)
FIR*68 4 If we imagine that we draw a sphere ( called a Kamming sphere% of radius e > 1 around each codeword. &his sphere will contain all n-tuples which are at a distance 1 away from each codeword ( i.e. all n-tuples which differ from this code word in one position %. If the minimum Kamming distance of the code dmin T 4e A 1 (as in figure 4b, where d > 4% the occurrence of a single error will result in changing the codeword to the ne$t n-tuple and the decoder does not have enough information to decide if codeword "1 or "4 was transmitted. &he decoder however can detect that an error has occurred. If we look at figure 4a we see that the code has a dmin > 4e A 1 and that the occurrence of a single error results in the ne$t n-tuple being received and in this case the decoder can make an unambiguous decision, based on what is called nearest neigh"our decoding rule, as to which of the two codewords was transmitted.
2B
1451(512
If the corrupted received n-tuple is not too unlike (not too distant from% the valid codeword, the decoder could make a decision that the transmitted codeword was the code word 9nearest in distance9 to the received the word. &hus in general we can say that a binary linear code will correct e errors if d in 0 >e 3 1 (for odd dmin % if d in 0 >e 3 > (for even dmin %
A .C @ ?/ Linear )loc* Code +2a %le 8$amine the following coding assignment that describes a (B, 2% code. &here are 4k > 42 > F information words, and therefore eight codewords. &here are 4n > 4B > si$ty-four B-tuples in the total B-tuple set (or vector space% Information word "odeword c2c4c1 cBc<c(c2c4c1 ;;; ;;;;;; 1;; 11;1;; ;1; ;11;1; 11; 1;111; ;;1 1;1;;1 1;1 ;111;1 ;11 11;;11 111 ;;;111
parity check e uations for this code are c( > c1 A c4 c< > A c4 A c2 cB > c1 Ac4 and its K matri$ is 11;1;; ;11;1; 1;1;;1
It is easy to check that the eight codewords shown above form a linear code (the all-=eros codeword is present, and the sum of any two codeword is another codeword member of the code%. &herefore, these codewords represent a linear "inar! "loc* code. It is also easy enough to check that the minimum Kamming distance of the code is d min > 2 thus we conclude that this code is a single error detection code, since d in 0 >e 3 1 ('or odd d in % .
In the simple case of single-parity-check codes, the single parity was chosen to be the modulo-4 sum of all the information digits. 3inear block codes contain several check digits, and each check digit is a function of the modulo-4 sum of some (or all% of the information digits.
2)
1451(512
3et us consider the (B , 2% code, i.e. n > B, k > 2, and there are r > n-k > 2 chek digits. /e shall label the three information digits by "1,"4 ,"2 and the three check digits as "(,"< and "B. 3ets choose to calculate the check digits from the information digits according to the following rules: (each one of these e uations must be inde%ent of any or all of the others% "( > "1 A "4 "< > "1 A "2 "B > "4 A "2 C( 1 1 ; C1 or in matri$ notation C< = 1 ; 1 C 4 CB ; 1 1 C 2 &he full codeword consists of the digits "1,"4 ,"2, "(,"< ,"B. Renerally the n-tuple codeword is denoted as C > ?"1,"4 ,"2, "(,"< ,"B @ 8very codeword must satisfy the parity-check e uations "1 A "4 A "( >; "1 A "2 A "< >; "4 A "2 A "B > ; C1 C 4 1 1 ; 1 ; ; ; 1 ; 1 ; 1 ; C2 = ; C ( ; ; 1 1 ; ; 1 C < CB
or in matri$ notation
which can be written a little more compactly as 1 1 ; 1 ; ; ; 1 ; 1 ; 1 ;C t = ; ; 1 1 ; ; 1 ; Kere Ct denotes the column which is the transpose of the codeword C 0 ="1,"4 ,"2, "(,"< ,"B< 8ven more compactly, we can write these parity check e uations as - Ct 0 1 where 1 is the three dimensional column whose components are all =eros and - is called the %arit!5chec* atri2. &hus in our e$ample
2F
1451(512
1 1 ; 1 ; ; - 0 1 ; 1 ; 1 ; ; 1 1 ; ; 1 7ote that each row of the parity check matri$ is inde%endent of all othe other rows, we say that these rows are linearl! inde%endent (i.e. we cannot obtain any row by the linear addition of any combination of the other rows%. &he 42 > F codewords in the code are Information digits,
"1,"4 ,"2
"1,"4 ,"2, "(,"< ,"B
"odewords
;;; ;;1 ;1; ;11 1;; 1;1 11; 111
;;;;;; ;;1;11 ;1;1;1 ;1111; 1;;11; 1;11;1 11;;11 111;;;
+fter the information se uence is encoded into the full codeword, the codeword is transmitted across the noisy channel. &he channel adds to this codeword the 9noise word9, also called the error %attern, + > ?81,84 ,82, 8(,8< ,8B @ ; where 8i >D 1 if the channel changes the ith digit. if the channel does not change the ith digit
&he received word is given by the se uence R 0 =61,64 ,62, 6(,6< ,6B< where R 0 C + (i.e. 6i > "i 8i %
( note that + 0 R C since addition modulo-4 is the same as subtraction modulo-4 % for e$ample say that the transmitted codeword was C > ? 11;;11 @ and the received word was R > ? 11;111 @ /e can say that the error pattern was + > ? ;;;1;; @ If we multiplied the transpose of the received word by the parity-check matri$ what do we get M - Rt 0 - .C+/t 0 - Ct - +t 0 St &he r-tuple S > ? -1,-4 ,-2 @ is called the s!ndro e. &his shows that the s!ndro e test, whether performed on either the corrupted received word or on the error pattern that caused it, yields the same syndrome
2I
1451(512
-ince the syndrome digits are defined by the same e uations as the parity-check e uations, the syndrome digits reveal the parity check failures on the received codeword. (&his happens because the code is linear. +n important property of linear block codes, fundamental to the decoding process, is that the mapping between correctable error patterns and syndromes is one-to-one and this means that we not only can detect an error but we can also correct it.% For e$ample using the received word given above R >? 11;111@ 1 1 1 1 ; 1 ; ; 1 ; - Rt 0 1 ; 1 ; 1 ; = ; > St , 1 ; ; 1 1 ; ; 1 1 1 where S > ? -1,-4 ,-2 @ > ?1;;@ and as we can see this points to the fourth bit being in error. 7ow all the decoder has to do ( after calculating the syndrome% is to invert the fourth bit position in the received word to produce the codeword that was sent i.e C > ? 11;;11 @. having obtained a feel of what channel coding and decoding is about, lets apply this knowledge to a particular type of linear binary block codes called the -a ing codes.
-AMMING COD+S &hese are 3inear binary single-error-correcting codes having the property that the columns of the parity-check-matri$, -@ consist of all the distinct non-=ero r se uences of binary numbers. &hus a Kamming code has as many parity-check matri$ columns as there are single-error se uences. these codes will correct all patterns of single errors in any transmitted codeword. &hese codes have n > k A r , where n 0 >r 5 1 @ and * 0 >r 5 1 5 r . &hese codes have a guaranteed minimum Kamming distance dmin > 2 .
for e$ample the parity-check-matri$ for the (),(% Kamming code is 1 1 1 ; 1 ; ; - > 1 1 ; 1 ; 1 ; 1 ; 1 1 ; ; 1 a% 1etermine the codeword for the information se uence ;;11 b% If the received word, R, is 1;;;;1;, determine if an error has occurred. If it has, find the correct codeword. Solution7 a% since - Ct 0 1 , we can use this e uation to calculate the parity digits for the given
(;
1451(512
codeword as follows: C1 C 4 1 1 1 ; 1 ; ; C 2 1 1 ; 1 ; 1 ; C ( 1 ; 1 1 ; ; 1 C < C B C ) ; ; 1 1 1 ; 1 ; ; 1 1 1 ; 1 ; 1 ; 1 1 ; 1 1 ; ; 1 C < C B C )
>
; > ; ;
by multiplying out the left hand side we get 1.; 1.; 1.1 ;.1 1."< ;."B ;.") > ; ; ; 1 ; "< ; ; > ; i.e. 1 "< > ; and "< > 1 similarly by multiplying out the second row of the K matri$ by the transpose of the codeword we obtain 1.; 1.; ;.1 1.1 ;."< 1."B ;.") > ; ; ; ; 1 ; "B ; > ; i.e. 1 "B > ; and "B > 1 similarly by multiplying out the third row of the K matri$ by the transpose of the codeword we obtain 1.; ;.; 1.1 1.1 ;."< ;."B 1.") > ; ; ; 1 1 ; ; ") > ; i.e. 1 1 ") > ; and ") > ; so that the codeword is C 0 ="1,"4 ,"2, "(,"< ,"B, ")< 0 1111111
b% to find whether an error has occurred or not we use the following e uation - Rt 0 St @ i' the s!ndro e is Dero then no error has occurred@ i' not an error has occurred and is %in %ointed "! the s!ndro e8 &hus to compute the syndrome we multiply out the rows of K by the transpose of the received word.
(1
1451(512
1 ; 1 1 1 ; 1 ; ; ; 1 1 1 ; 1 ; 1 ; ; > ; 1 1 ; 1 1 ; ; 1 ; 1 ; because the syndrome is the third column of the parity-check matri$, the third position of the received word is in error and the correct codeword is 1111111.
(4
1451(512
&he Generator Matri2 of a linear binary block code /e saw above that the parity-check matri$ of a systematic linear binary block code can be written in the following (n-k% by n matri$ form K > ? h In5* @ &he Generator Matri2 of this same code is written in the following k by n matri$ form G > ? I* ht @ &he generator matri$ is useful in obtaining the codeword from the information se uence according to the following formula C> G
/here, C is the codeword ="1,"4 ,.........," n-1 ,"n< is the information digit se uence = 1 @ > @ 88888@ * < , and G is the generator matri$ of the code as given by the formula for G above. &hus if we consider the single-error-correcting (n,k% > (),(% Kamming code disscussed previously, its parity-check matri$ was 11 1 ; 1 ; ; -> 1 1 ; 1 ; 1 ; 1; 1 1 ; ; 1 and thus its generator matri$ would be 1 ; ; ; 1 1 1 ; 1 ; ; 1 1 ; G= ; ; 1 ; 1 ; 1 ; ; ; 1 ; 1 1 now if we had an information se uence given by the following digits ;;11 , the codeword would be given by C > G , i.e. 1 ; ; ; ; 1 ; ; ; ; 1 ; ; ; ; 1 1 1 1 ; 1 1 ; 1 1 ; = ;;1111; 1 1
"= ; ; 11
(2
1451(512
SAMPLING E PCM I7&601*"&I07 &he trend in the design of new communication systems has been toward increasing the use of digital techni ues. 1igital communications offer several important advantages compared to analog communications, for e$ample, allows &1# techni ues, higher performance in the presence of noise , greater versatility, easier to processs, and higher security. &o transmit analogue message signals, such as voice and video signals, by digital means, the signal has to be converted to a digital signal. &his process is known as the analogue-to-digital conversion. &wo important techni ues of analogue-to-digital conversion are %ulse code odulation (PCM% and delta odulation (DM%. PULS+ COD+ MODULATION &he essential processes of !"# are 're$uenc! "andli iting .i8e8 'iltering/@ sa %ling, $uantising, and encoding, as shown below in Fig 1.
m(t)
Filter
Sampler
;+antiser
-nco"er
Figure 1. !"# essential processes Sa %ling is the process in which a continuous-time signal is sampled by measuring its amplitude at discrete instants. 6epresenting the sampled values of the amplitude by a finite set of levels is called $uantising. 1esignating each uantised level by a code is called encoding. /hile sampling converts a continuous-time signal to a discrete-time signal, uantising converts a continuous-amplitude sample to a discrete-amplitude sample. &hus sampling and uantising operations transform an analogue signal to a digital signal. &he uantising and encoding operations are usually performed in the same circuit, which is called an analogue-to-digital (+51% converter. &he combined use of uantising and encoding distinguishes !"# from analogue pulse modulation techni ues. In the following sections, we discuss the operations of sampling and fre uency bandlimiting, and Pulse A %litude Modulation (PAM% before discussing uantising, encoding and !"# .
SAMPLING T-+OR+M 1igital transmission of analogue signals is possible by virtue of the sampling theorem , and the sampling operation is performed in accordance with the sampling theorem. A8 )and5Li ited Signals: + band-limited signal is a signal m(t% for which the Fourier transform of m(t% is identically =ero above a certain fre uency #: m(t% #(% > ; for GG N # > 4f# (1% .
)8 Sa %ling Theore : If a signal m(t% is a real-valued band-limited signal satisfying condition (1%, then m(t% can be
((
1451(512
uni uely determined from its values m(n&s% sampled at uniform intervals &s ? &s 15(4f#%@. In fact, the reconstructed m(t% is given by m (t % =
n =
m(nT %
s
sin M (t nTs % M (t nTs %
&s is called the sa %ling %eriod and fs > 15&s is called the sa %ling rate (i.e. fs samples per second%. &hus, the sa %ling theore states that a band-limited signal which has no fre uency components higher than f# K= can be recovered completely from a set of samples taken at the rate of 's >'M samples per second. &he above sampling theorem is often called the uniform sampling theorem for baseband or low-pass signals. &he minimum sampling rate, 4f# samples per second, is called the N!$uist sa %ling rate .also called N!$uist 're$uenc!/. its reciprocal 15( 4f# % (measured in seconds% is called the N!$uist inter&al.
SAMPLING + sampled signal consists of a train of pulses, where each pulse corresponds to the amplitude of the signal m(t% at the corresponding sampling time. &hus the signal is modulated in amplitude and hence the name Pulse A %litude Modulation (PAM%. -everal !+# signals can be multiple$ed together as long as they are kept distinct and are recoverable at the receiving end. &his system is one e$ample of Ti e Di&ision Multi%le2 (&1#/ trans ission (although, in practice, it is not really used nowadays% A8 Instantaneous Sa %ling: -uppose we sample an arbitrary signal m(t% ?Fig.4a@ whose fre uency spectrum is #(% ?fig. 4b@ instantaneously and at a uniform rate, once every & s seconds. &hen we obtain an infinite se uence of samples Dm(n&%E, where n takes on all possible integer values. &his ideal form of sampling is called instantaneous sa %ling (also called impulse sampling%. )8 Ideal Sa %led Signals: /hen sampling a signal m(t% by a unit impulse train &(t% ?figure 4c@ it is represented mathematically by m s (t % = m(t % Ts (t % =
n =
m(nT % (t nT %
s s
and the sampled signal ms(t% ?figure 4d @ is called the ideal sa %led signal8 &his sampled signal has a spectrum as shown in figure 4e where it is seen that the baseband spectrum of the signal is repeated (unattenuated% periodically and appears around all multiples of the sampling fre uency. ( &his is because the impulse train has a constant line fre uency spectrum repeating at the harmonics or multiples of the sampling fre uency%. C8 18 Practical Sa %ling: Natural sa %ling: +lthough instantaneous ideal sampling is a convenient model, a more practical way of sampling a "and5li ited analogue signal m(t% is performed by high-speed switching (< 1451(512
circuits. +n e uivalent circuit of a mechanical switch and the resulting sampled signal are shown in figure 2 aVb. Figure < shows the effect that sampling with pulses that have a #idth (as opposed to theoretical impulses% has on the fre uency spectrum of the resulting sampled signal. +s it can be seen the baseband is still repeated at multiples of the sampling fre uency but now these repeated baseband spectra are attenuated by the sin.2/A2 factor which results from the spectrum of the train of pulses that have width. &he sampled signal $ns(t% can be written as $ns(t% > m(t% $p(t% where $p(t% is the periodic train of rectangular pulses with period &s, and each rectangular pulse in $p(t% has width d and unit amplitude. &he sampling here is termed natural sampling, since the top of each pulse in $ns(t% retains the shape of its corresponding analogue segment during the pulse interval. >8 (lat5To% Sa %ling: &he simplest and thus the most popular practical sampling method is actually performed by a functional block termed the sample-and-hold (SA-% circuit shown in figure ( aVb. &his circuit produces a flat-top sampled signal $s(t% shown in figure 2b. It produces a sampled signal which has appro$imately the same repeated fre uency spectrum as was discussed for the natural sampling and shown in figure <. Aliasing +rror If a signal is under sa %led (sampled at a rate below the 7y uist rate% , the spectrum #s(% consists of overlapping repetitions of #(% , as shown in Figure B. :ecause of the overlapping tails , #s(% no longer has the complete information about #(% , and it is no longer possible to recover m(t% from ms(t% . If the sampled signal ms(t% is passed through a lowpass filter, we get a spectrum that is not #(% but is a distorted version as a result of two separate causes: 1% loss of the tail of #(% beyond GG N s54, and 4% this same tail appears inverted, or folded, onto the spectrum at the cut-off fre uency. &his tail inversion, known as aliasing, (or spectral folding or foldover distortion%, is shown shaded in Figure B. . &he aliasing distortion can be eliminated by cutting the tail of #(% beyond GG N s54 before the signal is sampled. :y so doing, the overlap of successive cycles in #s(% is avoided. &he only error in the recovery of m(t% is that caused by the missing tail for GG N s54. "utting the tail off reduces the error signal energy by half.
+ speech signal has fre uency components beyond 2.( kK= that contribute a negligible fraction of the total energy. /hen speech signals are transmitted by !"#, they are first passed through a lowpass filter of bandwidth 2<;; K=, and the resulting signal is sampled at a rate of F;;; samples per second. For a bandwidth of 2<;; K=, the minimum sampling rate (the 7y uist rate% is );;;. Kigher sampling rate (i.e. F;;; samples 5sec% permits recovery of the signal from its samples using relatively simpler filters i.e. it allows for guard "ands between the repetitions of #(%. /hen a practical signal m(t% is to be transmitted by its samples (as in !"#% , we must first estimate its essential bandwidth : and then cut off its spectrum beyond :. In essence, Aliasing distortion %roduces 're$uenc! co %onents in the desired 're$uenc! "and that did not e2ist in the original #a&e'or 8 &his is why the in%ut ust "e "andli ited , before (B 1451(512
sampling, to remove fre uency terms greater than fs54, even if these fre uency terms are ignored (i.e., are inaudible% at the destination. +liasing problems are not confined to speech digitisation processes. &he potential for aliasing is present in any sample data system. #otion picture taking, for e$ample, is another sampling system that can produce aliasing. + common e$ample occurs when filming moving stagecoaches in old /esterns. 0ften the sampling process is too slow to keep up with the stagecoach wheel movements, and spurious rotational rates are produced. If the wheel rotates 2<<o between frames, it looks to the eye as if it has moved backwards <o. Figure F demonstrates clearly the result of aliasing if a <.< kK= signal is sampled at an F kK= rate. 7otice that the sa %le &alues are identical to those obtained from a 4.< kK= input signal. &hus after the sampled signal passes through the ( kK= output filter, a 4.< kK= signal arises that did not co e from the source. &hus, a complete !+# system, shown as part of Figure I ( without the +51 V 15+% like in figure 1; , must include a bandlimiting filter before sampling to ensure that no spurious or source-related signals get 9folded9 back into the desired signal bandwidth. &he input filter may also be designed to cut off very low fre uencies to remove <; K= 9hum9 from power lines. Figure 1; shows the signal being recovered by a sample-and-hold circuit that produces a staircase appro$imation to the sampled waveform. /ith use of the staircase appro$imation, the power level of the signal coming out of the reconstructive filter is nearly the same as the level of the sampled input signal. &he bandlimiting and reconstructive filters shown in Figure 1; are implied to have ideal characteristics. -ince ideal filters are physically unrealisable, a practical implementation must consider the effects of non ideal implementations. Filters with realisable attenuation slopes at the band edge can be used if the input signal is slightly oversampled. +s indicated in Figure 4e, when the sampling fre uency fs is somewhat greater than twice the bandwidth, the spectral bands are sufficiently separated from each other that filters with gradual roll-off characteristics can be used. +s an e$ample, sampled voice systems typically use bandlimiting filters with a 2 d: cut-off around 2.< kK= and a sampling rate of F kK=. &hus the sampled signal is sufficiently attenuated at the overlap fre uency of ( kK= to ade uately reduce the energy level of the foldover spectrum. Figure 11 shows a filter template designed to meet ITU (International &elecommunications *nion% recommendations for out-of-band signal re'ection in !"# voice coders. 7otice that 1( d: of attenuation is provided at ( kK= .
()
1451(512
FUANTISATION in PULS+ COD+ MODULATION &he preceding section describes pulse amplitude modulation, which uses discrete sample times with analogue sample amplitudes to e$tract the information in a continuously varying analogue signal. !ulse code modulation (PCM% is an e$tension of !+# wherein each analogue sample value is uantised into a discrete value for representation as a digital code word. &hus, as shown in Figure I, a !+# system can be converted into a !"# system by adding a suitable analogue-to-digital (+51% converter at the source and a digital-to-analogue (15+% converter at the destination. Figure 14 depicts a typical uantisation process in which a set of uantisation intervals are associated in a one-to-one fashion with a binary codeword. +ll sample values falling in a particular uantisation interval are represented by a single discrete value located at the centre of the uantisation interval. In this manner the uantisation process introduces a certain amount of error or distortion into the signal samples. &his error, known as 9$uantisation noise,9 is minimised by establishing a large number of small uantisation intervals. 0f course, as the number of uantisation intervals increase, so must the number of bits increase to uni uely identify the uantisation intervals. FUANTISATION A8 Uni'or Fuantisation7 +n e$ample of the uantising operation is shown in figure 14. /e assume that the amplitude of the signal m(t% is confined to the range (-mp,Amp%, i.e. mp is the peak voltage value of the signal. +s illustrated in figure 14, this range is divided into L =ones, each of ste% siDe , given by 4m p (1% = L + sample amplitude value is appro$imated by the midpoint of the interval in which it lies. &he input-output characteristics of a uniform uantiser are shown in figure 12 )8 Fuantisation noise7 &he difference between the input and output signals of the uantiser becomes the $uatisation error@ or $uantisation noise. It is apparent that with a random input signal, the uantising error $e varies randomly in the interval q e + 4 4 It can be shown that, assuming the uantising error is e ually likely to lie anywhere in the range ( - 54 to 54 %, that the mean s uare uantising error (or the mean s uare noise power% is given by 4 q e4 = (4% 14
&hus by substituting from e uation 1 into 4 we get the uantisation noise power as given by (2% ?L &he uantisation error or distortion created by digitising an analogue signal is customarily e$pressed as the ratio of average signal power to average uantisation noise power. &hus the signal-to- uantisation noise ratio SFR (also called signal-to-distortion ratio or signal-to-noise ratio% can be determined as =
> $e > % >
(F
1451(512
SFR . d) / = 11 log11 .
. signal r s &oltage / > $e >
((%
"onsidering the sine wave with peak voltage mp and using e uation (2% we get: -U6 (d:% 0 1; log1;? ( mp m4 p 4 %4 23
4
@ > 1; log1; 2 34 > 1.)B A 4; log1; 3 4 .H/
SFR.d)/ 0 18GC 3 >1 log11 L
If 3 > 4n levels , where each level can be represented by n binary digit, then, SFR .d)/ 0 18GC 3 C n .C/
this last formula tells us that each time we increase the codeword by one bit we gain Bd: in the -U6% +2a %le7 + sine wave with 1 volt ma$imum amplitude is to be digitised with a minimum signal-to- uantisation noise ratio (-U6% of 2; d:. Kow many bits are needed to encode each sample.M ( mp 4 %4 m4 p 4 -ince e = and -U6 > 2; d: > 1; log1;? 4 @ m p 234 234 2; d: > 1; log1; 2 34 > 1.)B A 4; log1; 3 4 but since 3 > 4n , where n is the number of binary digits that can represent 3 levels 2; d: > 1.)B A4; log1; 4n > 1.)B A 4; n log1; 4 > 1.)B A Bn thus n > (.) i.e. n must be < bits 8$ample: + (;-#byte hard disk is used to store !"# data. -uppose that a JF (voice-fre uency% signal is sampled at F;;; samples5sec and the encoded !"# is to have an -U6 of 2; d:. Kow many minutes of JF conversation can be stored on this hard diskM
If all uantisation intervals have e ual lengths (uniform uantisation%, the uantisation noise is independent of the sample values and the signal-to- uantisation noise ratio is determined by m4 m4 SQR(dB % = 1; log1; ( 4 % = 1; log1; ( 4 % 14 qe m SQR(dB % = 1;.F + 4; log1; ( %
(I
1451(512
where
is the r s amplitude of an arbitrary input signal wave form (not necessarily a sine wave%.
In particular if the input is a sine wave with peak amplitude mp then m > mp54 , and SQR(dB % = 1; log1; ( mp
4 4
14
% %
SQR(dB % = ).)F + 4; log1; (
mp
+gain considering e uation (, if the input is a sine wave with peak amplitude less than mp54, say e ual to Jp, then -U6 ( d: % = 1; log1; ( Jp 4 4 mp 4 23 I%
4
% = 1; log1; (
Jp 4
mp
%( 4
234 % 4
SFR.d)/ 0 >1 log11 .
/ 3 18GC 3 C n
()%
&he last two terms of this e uation provide the -U6 when encoding a full range sine wave. &he first term indicates a loss in -U6 #hen encoding a lo#er le&el signal.
<;
1451(512
Again@ in relation to SFR7 /e assume that the amplitude of the signal m(t% is confined to the range (-mp,Amp%, i.e. mp is the peak voltage value of the signal. +s illustrated in figure 14, this range is divided into L =ones, each of ste% siDe , given by 4m p (1% = L It can be shown that, assuming the uantising error is e ually likely to lie anywhere in the range ( - 54 to 54 %, that the mean s uare uantising error (or the mean s uare noise power% is given by 4 q e4 = (4% 14
&hus by substituting from e uation 1 into 4 we get the uantisation noise power as given by
> $e
?L
> % >
(2%
&hus the signal-to- uantisation noise ratio SFR can be determined as (signalpowe r ) SQR (dB ) = 10 lo&10 ( ) 2 qe
and we could consider the following three cases:
1/ If we consider the ma$imum signal and the ma$imum signal power to uantisation noise ratio, then in this case SFR.d)/ 0 B8J 3 Cn
<1
1451(512
+s shown below: S @ > 1; log1;? 2 2 mp < qe >
mp
-U6 (d:% 0 1; log1;?
@ > 1; log1;? 3L2 @
3L2 > 1; log1; 2 A 1; log1;? L2 @ > 1; log1; 2 A 4; log1;? L @ > 1; log1; 2 A 4; log1;? 2 n @
> 1; log1; 2 A 4; n log1;? 2 @ > (.F A Bn >/ If we consider the average signal and the average signal power to uantisation noise ratio, then in this case SFR.d)/ 0 Cn +s shown below: &he average signal of a signal which can have any values between Amp and W mp with e ual probability can be shown to be e ual to m p
2
-U6 (d:% 0 1; log1;?
S @ > 1; log1;? 2 < qe > m
mp
2 p
3 3L2
@ > 1; log1;? L2 @
> 4; log1;? L @ > 4; log1;? 2 n @ > 4; n log1;? 2 @ > Bn ?/ If we consider the specific case of a sine wave, then the average signal power to uantisation noise ratio in this case will be SFR.d)/ 0 18GC 3 Cn +s shown below: &he root mean s uare of a sine wave signal of peak amplitude mp is
mp 2
, thus
-U6 (d:% 0 1; log1;?
S @ > 1; log1;? 2 < qe > m
mp
2 p
2 3L2
@ > 1; log1;? 3L @
2
> 1; log1;? 3 @ A 1; log1;? L2 @ > 1.)B A 4; log1;? 2 n @ > 1.)B A 4; n log1;? 2 @ > 1.)B A Bn 2
<4
1451(512
+2a %le7 +n audio signal with spectral components limited to the fre uency band 2;; to 22;; K=, is sampled at F;;; samples per second, uniformly uantised and binary coded. If the re uired output ma$imum signal-to- uantisation-noise is 2; d:, calculate: a% the minimum number of uniform uantisation levels needed, b% the number of bits per sample needed, c% the system output bit rate, a% -U6 2; > (.F A 4; log1; 3 3 > log-1 (2;-(.F%54; >1F.4 &hus the minimum number of re uired levels is 1I b% 1I > 4n , thus log1; 1I> n log1; 4 , n > (log1; 1I%5 log1; 4 > (.4 thus the minimum number of bits per sample is < (and the actual number of levels > 4< > 24 % c% F;;; $ < > (;;;; bits5sec Pro"le 7 It is re uired to design a new !"# which would improve on the -U6 of an e$isting !"# system by 4( d:. If the e$isting !"# system uses 1; bits to represent each sample, how many bits must the new !"# system use in order to satisfy the re uirementM Pro"le 7 If the input signal to a !"# system is a sine wave, and given that the mean s uare uantising 4 q e4 = error (or the mean s uare uantising noise power% is 14 prove that for a sine wave the ratio of average signal power to average uantisation noise power is given by SFR .d)/ 0 18GC 3 C n Pro"le 7 -how how does an increase or decrease of 1 bit affect the !"# system -U6.
<2
1451(512
Co %anding7 In a uniform !"# system the si=e of every uantisation interval is determined by the -U6 re uirement of the lowest signal level to be encoded. 3arger signals are also encoded with the same uantisation interval. +s indicated in e uation ) and Figure 12c , the -U6 increases with the signal amplitude + . For e$ample, a 4B d: -U6 for small signals and a 2; d: dynamic range produces a <B d: -U6 for a ma$imum amplitude signal. In this manner a uniform !"# system provides unneeded uality for large signals. #oreover, the large signals are the least likely to occur. For these reasons the code space in a uniform !"# system is very inefficiently utilised. + more efficient coding procedure is achieved if the uantisation intervals are not uniform but allowed to increase with the sample value. /hen uantisation intervals are directly proportional to the sample value, the -U6 is constant for all signal levels. /ith this techni ue fewer bits per sample provide a specified -U6 for small signals and an ade uate dynamic range for large signals. /hen the uantisation intervals are not uniform, a non-linear relationship e$ists between the code words and the samples they represent. Kistorically, the non-linear function was first implemented on analogue signals using non-linear devices such as specially designed diodes. &he basic process is shown in Figure 1(a , where the analogue input sample is first compressed and then uantised with uniform uantisation intervals. &he effect of the compression operation is shown in Figure 1(b. 7otice that successively larger input signal intervals are compressed into constant length uanti=ation intervals. &hus the larger the sample value, the more it is compressed before encoding. +s shown in Figure 1(a, a non-uniform !"# decoder e$pands the compressed value using an inverse compression characteristic to recover the original sample value. &he process of first compressing and then e$panding a signal is referred to as 9co %anding.9 /hen digitising, companding amounts to assigning small uantisation intervals to small samples and large uantisation intervals to large samples. Jarious compression-e$pansion characteristics can be chosen to implement a compandor. :y increasing the amount of compression, we increase the dynamic range at the e$pense of the signal-tonoise ratio for large amplitude signals. 5La# Co %anding 0ne family of compression characteristics used in North A erica and Sapan is the 5la# characteristic defined as: ln(1 + G x G% ( x % = sgn( x % ln(1 + % where $ is the input signal amplitude (- 1 $ 1 %, sgn($% is the polarity of $ , and is a parameter used to define the amount of compression. :ecause of the mathematical nature of the compression curve, companded !"# is sometimes referred to as log-!"#. + logarithm compression curve is ideal in the sense that uantisation intervals and hence, uantisation noise is proportional to the sample amplitude. &he inverse or e$pansion characteristic for a -law compandor is defined as 1 F1( y ) = s&n( y )( )=(1 + )/y / 1< where y is the compressed value > F($% ( -1 y 1%, sgn(y% is the polarity of y, and is the companding parameter. A5La# Co %anding &he companding characteristic recommended by ""I&& is referred to as an +-law characteristic. &his characteristic has the same basic features and implementation advantages as does the -law characteristic.
<(
1451(512
In particular, the +-law characteristic can also be well appro$imated by straight-line segments to facilitate direct or digital companding, and can be easily converted to and from a linear format. &he normalised +-law compression characteristic is defined as: +G $G 1 F+ ( $% = sgn( $%( % ; $ 1 + ln( + % + = sgn( $ %( 1 + lnG +$G % 1 + ln( + % 1 $1 +
and it also has an even more cumbersome formula for its inverse which we will not mention here, DI((+R+NTIAL PULS+ COD+ MODULATION 1ifferential pulse code modulation (1!"#% is designed specifically to take advantage of the sampleto-sample redundancies in a typical speech waveform. -ince the range of sample differences is less than the range of individual amplitude samples, fewer bits are needed to encode difference samples. &he sampling rate is often the same as for a comparable !"# system. &hus the bandlimiting filter in the encoder and the smoothing filter in the decoder are basically identical to those used in conventional !"# systems. &he simplest means of generating the difference samples for a 1!"# coder is to store the previous input sample directly in a sample-and-hold circuit and use an analog subtractor to measure the change. &he change in the signal is then uanti=ed and encoded for transmission. &he 1!"# structure shown in Figure 1< is more complicated, however, because the previous input value is reconstructed by a feedback loop that integrates the encoded sample differences. In essence, the feedback signal is an estimate of the input signal as obtained by integrating the encoded sample differences. &hus the feedback signal is obtained in the same manner used to reconstruct the waveform in the decoder. &he advantage of the feedback implementation is that uanti=ation errors do not accumulate indefinitely. If the feedback signal drifts from the input signa1, as a result of an accumulation of uanti=ation errors, the ne$t encoding of the difference signal automatically compensates for the drift. In a system without feedback the output produced by a decoder at the other end of the connection might accumulate uanti=ation errors without bound. +s in !"# systems, the analog-todigital conversion process can be uniform or companded. -ome 1!"# systems also use adaptive techni ues to ad'ust the uanti=ation step si=e in accordance with the average power level of the signal. &hese adaptive techni ues are often referred to as syllabic companding, in accordance with the time interval between gain ad'ustments. -yllabic companding is most often used with delta modulation systems.
D+LTA MODULATION 1elta modulation (1#% is another digiti=ation techni ue that specifically e$ploits the sample-to-sample redundancy in a speech waveform. In fact, 1# can be considered as a special case of 1!"# using only 1 bit per sample of the difference signal. &he single bit specifies merely the polarity of the difference sample and thereby indicates whether the signal has increased or decreased since the last sample. +n appro$imation to the input waveform is constructed in the feedback path by stepping up one uanti=ation level when the difference is positive (9one9% and stepping down when the difference is negative (9=ero9%. In this way the input is encoded as a se uence of 9ups9 and 9downs9 in a manner resembling a staircase. Figure 1B shows a 1# appro$imation of a typical waveform. 7otice that the feedback signal continues to step in one direction until it crosses the
<<
1451(512
input at which time the feedback step reverses direction until the input is crossed again. &hus when tracking the input signal the 1# output 9bounces9 back and forth across the input waveform allowing the input to be accurately reconstructed by a smoothing filter. -ince each encoded sample contains a relatively small amount of information (i bit%, delta modulation systems re uire a higher sampling rate than !"# or multibit 1!"# systems. In fact, the sampling rate is necessarily much higher than the minimum (7y uist% sampling rate of twice the bandwidth. From another viewpoint, 9oversamplingL is needed to achieve better prediction from one sample to the ne$t. 1elta modulation has attracted considerable interest as a method of digiti=ing various types of analog signals. 0ne of the main attractions of 1# is its simplicity. Figure 1) shows a basic implementation of a 1# encoder and decoder. 7otice that the +51 conversion function is provided by a simple comparator. + positive difference voltage produces a 1, and a negative difference voltage produces a ;. "orrespondingly, the 15+ function in the feedback path and in the decoder, is provided by a twopolarity pulse generator. In the simplest form the integrator can consist of nothing more than a capacitor to accumulate the charge from the pulse generator. In addition to these obvious implementation simplicities, a delta modulator also allows the use of relatively simple filters for bandlimiting the input and smoothing the output. &he spectrum produced by a sampling process consists of replicas of the sampled spectrum centered at multiples of the sampling fre uency. &he relatively high sampling rate of a delta modulator produces a wider separation of these spectrums, and, hence, foldover distortion is prevented with less stringent roll-off re uirements for the input filter.
<B
1451(512

An Intro To Digital Comms - Part 1

Uploaded by

Copyright:

Available Formats

An Intro To Digital Comms - Part 1

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

An Intro To Digital Comms - Part 1

Uploaded by

Copyright:

Available Formats

AN INTRODUCTION TO DIGITAL COMMUNICATIONS Part 1 Figure 1 shows the block diagram of a digital communication system.

0. 1egree &elecoms 2 3ecture notes

"hannel 8ncoder #odulator

"hannel 1ecoder 1emodulator

(igure 1 )loc* Diagra

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

&hus we can write : ; n+ 7

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

A#B# A AB# AB A#B B A (AB#)

FIG 2. $enn %ia&ram representin& 'nion an" Intersection of e(ents

FIG 3. $enn %ia&ram representin& )!o *+t+all, -.cl+si(e e(ents

fD+ :E the relative fre uency of occurrence of either + or : or both >

0. 1egree &elecoms 2 3ecture notes

which is identical to p(8% > p(+% A p(:% - p(+:%, since p( A ) = lim (

n A + n AB n + n AB n ) , p(B) = lim ( B ) , and p( AB) = lim ( AB ) n n n n n

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

12 > 02(1 0)2

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

for i > ;,1,4, ..., (k-1%

/I.s i / 1 < %.s i /

%.si / log > = %.s

K = p(s; % log 4 ? >

1 1 1 @ A p(s1 % log 4 ? @ A p(s4 % log 4 ? @ p(s; % p(s1 % p(s4 %

1 1 1 2 log 4 ( (% + log 4 ( (% + log 4 ( 4% = = 1. < bits 5 symbol ( ( 4 4

In'or ation Rate

%.si / log >= %.si / <

where, in this case k > <

K = p(s; % log 4 ? >

1 1 1 1 1 log 4 ( 4% + log 4 ( ( % + log 4 (F% + log (1B% + log 4 (1B% 4 ( F 1B 4 1B

= ;. < + ;. < + ;. 2)< + ;. 4< + ;. 4< = 1. F)< bits 5 symbol

&he entropy of such a source e uals:

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

Channel Coding Theorm

1 symbols5sec%, the channel capacity T

"its %er second8

0. 1egree &elecoms 2 3ecture notes

Signal to Noise Ratio .d)/ 0 1; log1;

Channel Capacity Theorm

"its %er second,

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

> > > >

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

Fi&+re 1 an (n51) 6loc1 co"e!or" in s,stematic form

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes

0. 1egree &elecoms 2 3ecture notes