Scribd
Upload
12 views9 pages

Student's Guide to Coding Theory

This document discusses different types of codes used in information theory including block codes, variable-length codes, non-singular codes, uniquely decodable codes, instantaneous codes, and prefix codes. Block codes take an information word and transform it into a fixed length codeword. Variable-length codes can be non-singular, uniquely decodable, or instantaneous. Non-singular codes map each source symbol to a unique bit string, uniquely decodable codes have non-singular extensions, and instantaneous codes allow decoding after the entire codeword is received. Prefix codes have a prefix property that allows message transmission without framing codewords.

Uploaded by

Khaleel Aboobackr.k
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
12 views9 pages

Student's Guide to Coding Theory

This document discusses different types of codes used in information theory including block codes, variable-length codes, non-singular codes, uniquely decodable codes, instantaneous codes, and prefix codes. Block codes take an information word and transform it into a fixed length codeword. Variable-length codes can be non-singular, uniquely decodable, or instantaneous. Non-singular codes map each source symbol to a unique bit string, uniquely decodable codes have non-singular extensions, and instantaneous codes allow decoding after the entire codeword is received. Prefix codes have a prefix property that allows message transmission without framing codewords.

Uploaded by

Khaleel Aboobackr.k
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Information Theory and Coding

Zaheer
Yousuf
Block code
The main characterization of a block code
is that it is a fixed length channel code

Typically, a block code takes a


information word, and transforms this into
fixed length n-digit codeword.

Simple block code can be a fixed length


binary counter.
Variable-length codes

Non-singular codes

Uniquely decodable

Instantaneous codes
Non-singular codes
A code is non-singular if each source
symbol is mapped to a different non-
empty bit string, i.e. the mapping from
source symbols to bit strings is one-to-
one.
The mapping M2 = {(a,0), (b,1), (c,00),
(d,01)} is non-singular  .Its extension will
generate a lossless coding, which will be
useful for general data transmission
Not non-singular code
For example the mapping M1 = {(a,0), (b,0),
(c,1)} is not non-singular because both "a"
and "b" map to the same bit string "0" ; any
extension of this mapping will generate a
lossy (non-lossless) coding. Such singular
coding may still be useful when some loss of
information is acceptable (for example when
such code is used in audio or video
compression, where a lossy coding becomes
equivalent to source quantification).
Uniquely decodable codes
A code is uniquely decodable if its
extension is non-singular.
The extension of the mapping M3 = {(a,0),
(b,01), (c,011)} is uniquely decodable (this
can be demonstrated by looking at the
follow-set after each target bit string in the
map, because each bitstring is terminated as
soon as we see a 0 bit which cannot follow
any existing code to create a longer valid
code in the map, but unambiguously starts a
new code).
Instantaneous codes
A code is instantaneous when symbols
can be decoded instantaneously after their
entire codeword is received.
The example mapping M3 in the previous
paragraph is not instantaneous because
we don't know after reading the bit string
"0" if it encodes a "a" source symbol, or if
it is the prefix of the encodings of the "b"
or "c" symbols.
Instantaneous codes
An example of an instantaneous variable-
length code is shown below.
Prefix code
A prefix code is a code, typically a variable-
length code, with the "prefix property“
Using prefix codes, a message can be
transmitted as a sequence of concatenated
code words, without any need to frame the
words in the message.

Example a =0
b = 10
c = 110
d = 1110

You might also like