2/14/13  

1  

D R . R I S A N U R I H I D AYAT

PENYANDIAN KANAL

PERKENALAN

26/07/2011 Jurusan Teknik Elektro dan Teknologi Informasi UGM 2  

2/14/13  

2  

TATA TERTIB

� Masuk  Jam:  ............  � Apabila  Dosen  masuk  terlambat,  mahasiswa  harus  masuk  lebih  dulu  

� Tidak  boleh  buka  laptop  selama  kuliah  � PPT  di-­‐download  dan  di-­‐print  sebelum  kuliah  (bukan  setelah  kuliah)  

� Buku  Teks  &  Catatan  (PPT)harus  dibawa  � PR  dan  Quiz    setiap  saat  � PR  tidak  boleh  terlambat  � Mhs  harus  menjawab  dengan  jelas  ketika  ditanya  � Feed  back  perkuliahan  (anonim)  

26/07/2011 Jurusan Teknik Elektro dan Teknologi Informasi UGM 3  

RENCANA SILABUS

26/07/2011 Jurusan Teknik Elektro dan Teknologi Informasi UGM 4  

2/14/13  

3  

REVIEW MATA KULIAH

•  TEE571  –  Teknik  Penyandian  Kanal  •  Mata  Kuliah  Pilihan  (Sem  7  &  8)  •  Bersifat  Lanjut  •  Beberapa  MK  Dasar  

26/07/2011 Jurusan Teknik Elektro dan Teknologi Informasi UGM 5  

DIGITAL COMM SYSTEM

2/14/13  

4  

PENYANDIAN

PENDAHULUAN

•  In digital communication systems, data is transmitted through a channel, and the components which embody coding theory are called the •  channel encoder and •  channel decoder

•  The medium over which information is sent, together with its characteristics, is called the channel.

•  These characteristics consist of •  an input alphabet X, •  an output alphabet Y, and •  a transition probability function P.

•  The channel is assumed to be memoryless.

2/14/13  

5  

PENDAHULUAN

Binary Symmetric Channel (BSC),

DEFINITION

•  A channel (X, Y ; P ) consists of an alphabet X of input symbols, an alphabet Y of output symbols, and for each x in X and y in Y the conditional probability p(y|x) that symbol y is received, when symbol x was transmitted

• Σy∈Y p(y|x) = 1 for all x in X#

•  The Binary Symmetric Channel is the channel (X, Y ; P ) with both X and Y equal to {0,1} and P given by p(1|0) = p(0|1) = p and p(0|0) = p(1|1) = 1−p for some 0≤p≤1.

2/14/13  

6  

GAUSSIAN CHANNEL

•  Given by X = {−1, 1}, Y = IR and the probability density function p(y|x) which is the Gaussian distribution with x as mean and with some given variance, depending on the reliability of the channel

GAUSSIAN AND BSC

•  If the actual channel is Gaussian, one can reduce it to the BSC, by replacing every y ≥ 0 by 1 and every y < 0 by 0, and by writing 0 instead of the the input symbol −1.

•  By reducing the Gaussian channel to the BSC, one throws away information about the transmitted symbol

2/14/13  

7  

DEFINITION

•  The binary symmetric error and erasure channel is a channel (X,Y;P) with X = {0,1}, Y = {0,∗,1}, and P given by •  p(0|0) = p(1|1) = 1−p’ −p’’, •  p(1|0) = p(0|1) = p′ and •  p(∗|0) = p(∗|1) = p’’

•  for some non-negative p′ and p’’ with 0 ≤ p’ + p’’ ≤ 1.

•  The ∗ symbol means that there is too much ambiguity about the transmitted symbol. One speaks of an erasure (penghapusan).

ENCODER & DECODER

•  An encoder is a mapping (or algorithm) that transforms each sequence of symbols from the message alphabet A to a sequence of symbols from the input alphabet X of the channel, in such a way that redundancy is added (to protect it better against channel errors).

a x y a’

•  A decoder is an algorithm that transforms the received sequence of symbols of the output alphabet Y of the channel into a message stream over A. If a decoder sometimes fails to do this (because it is not able to do so or to avoid messages that are too unreliable) one speaks of an incomplete decoder.

2/14/13  

8  

DEFINITION

•  If the encoder maps k-tuples of symbols from the message alphabet A in a one-to-one way to n-tuples of symbols alphabet X of the channel, the resulting set of |A|k output n-tuples is called a block code. For the elements of a block code one uses the name codeword.

•  If the encoder maps k-tuples of symbols from the message alphabet A to n-tuples of symbols alphabet X in a way that also depends on the last m input k-tuples, where m is some fixed parameter, the resulting sequence of output n-tuples is called a convolutional code. These output sequences are also named codewords.

M-ARY

2/14/13  

9  

INFORMATION RATE (R)

•  Let M denote the size of A and let q denote the size of X.

•  If all k-tuples of M-ary symbols are equally likely, one needs k log2 M bits to denote one of them.

•  Similarly, n-tuples of q-ary symbols one needs n log2 q bits.

•  Let the information rate R denote the amount of information that an input symbol of the channel contains. It follows that

SHANNON’S PROVE

•  As long as the rate R is smaller than some quantity C, one can (for sufficiently long block lengths n) find encodings at rate R, such that the probability of incorrect decoding (when using maximum likelihood decoding) can be made arbitrarily small

[Shannon, C.E., A mathematical theory of communication, Bell Syst. Tech. J., 27, pp. 379-423, 623-656, 1948]

2/14/13  

10  

DEFINITION

•  The entropy function h(p) is defined for 0 ≤ p ≤ 1 by

SHANNON’S THEOREM

Consider the BSC with error probability p and let C = 1 − h(p). Then, for each rate R with R < C, an infinite sequence of encodings El exists, where El maps binary kl-tuples to binary nl-tuples with kl = [ Rnl ] (so El has rate > R), such that the corresponding maximum-likelihood decoding algorithms have a probability of incorrect decoding that goes exponentially fast to 0 as a function of nl, for l → ∞.

•  The quantity C is called the capacity of the channel.

•  For rates R greater than C, no encodings can be made with error probabilities tending to zero.

2/14/13  

11  

THE GOAL

•  The BSC with p = 1/2 cannot be used to transmit any information. The receiver may as well write down his own sequence of symbols instead of listening to the channel. At the other extreme, p = 0 and p = 1 imply that information can be sent at rate 1.

•  It is the ultimate goal of coding theory to find codes that approach the capacity of the BSC and that have efficient decoding algorithms.

PROBLEMS

•  Suppose that four messages are encoded into 000000, 001111, 110011 and 111100. These four messages are transmitted with equal probablity over a BSC with error probability p. If one receives a sequence different from the four sequences above, one knows that errors have been made during the transmission.

•  What is the probability that errors have been made during the transmission and that the receiver will not find out?

2/14/13  

12  

PROBLEMS

•  Suppose that either (−1, −1, −1) or (+1, +1, +1) is transmitted (each with prob- ability 1/2) over the Gaussian channel defined by the density function

•  What is the most likely transmitted sequence when the word (−1,+0.01,+0.01) is received?

REFERENSI

•  Henk C.A. van Tilborg, CODING THEORY a first course

•  http://www-math.ucdenver.edu/~wcherowi/courses/m7823/codln.html

26/07/2011 Jurusan Teknik Elektro dan Teknologi Informasi UGM 24  

2/14/13  

13  

DISCUSSION