B2P2 - Information theory and lossless compression

Question 1

ASCII coding

Answer 1

a standard 7-bit code for repping a source alphabet of 128 symbols, comprising the letters A-Z (upper and lower case), the numerals 0-9 and various other symbols and control characters;

ASCII = American Standard Code for Information Interchange;

Question 2

binary-coded decimal (BCD)

Answer 2

a code for binary rep of decimal numbers in which each of the decimal digits 0-9 is repped by a four-bit code word that is the binary equivalent of the decimal value;

Question 3

code tree (decision tree)

Answer 3

a graphical rep of a procedure for the generation and decoding of instantaneous codes;

[e.g. a Huffman code tree?]

Question 4

compression

Answer 4

in the context of source coding, the reduction of the number of bits required to rep a source;

compression may be either lossy or lossless;

Question 5

entropy

Answer 5

in information theory, the entropy of an information source is the theoretical minimum number of bits per symbol needed to rep the transmitted symbols;

it is a measure of the rate at which information is being transmitted from the source;

Question 6

Huffman coding

Answer 6

a procedure in which source symbols with the highest probabilities are allocated systematically to the shortest code words;

Huffman coding results in a maximally efficient source code;

Question 7

information theory

Answer 7

a body of theory that addresses fundamental performance limits of communications systems;

Question 8

instantaneously decodable code

Answer 8

a code that is not only uniquely decodable, but for which each received code word can be decoded immediately after it has been received;

it is not necessary to wait for any later code words;

Question 9

Lempel-Ziv-Welch (LZW)

Answer 9

a method of compression based on detecting patterns in data, assigning short codes to them, and then using those codes when the same patterns appear again;

[is a generalisation of RLE];

Question 10

lossless compression

Answer 10

any source coding technique that enables an exact reconstruction of the original source data from the compressed rep;

Question 11

lossy compression

Answer 11

any source coding technique where there is an irreversible loss of information, and only an approximate version of the original source data can be reconstructed from the compressed data;

Question 12

message

Answer 12

in the context of information theory as formulated by Claude Shannon, an information source generates a sequence of messages to be sent over a comms channel;

each message consists of a source symbol that is selected from the source alphabet;

Question 13

prefix

Answer 13

in the context of source coding, a code that also forms the first part of another code;

e.g. 11 would be a prefix code for the code 1101;

Question 14

pseudocode

Answer 14

a semi-formal description of an algorithm using the conventions of computer programming but intended for a human reader;

Question 15

run-length encoding (RLE)

Answer 15

a method fo data compression based on sending numbers that indicate the lengths of runs of symbols of the same type;

Question 16

source alphabet

Answer 16

in the context of information theory, the set of all possible source symbols that may be used for the message to be communicated over the channel;

Question 17

source coding

Answer 17

coding that can be either lossless or lossy, and has the aim of repping a source input signal by the minimum number of bits without exceeding some defined level of distortion;

Question 18

source extension

Answer 18

the effective source when source symbols are grouped together;

[A.to(generating new numbers out of the digits 0-9; generating new words out of the letters A-Z);

Question 19

uniquely decodable code

Answer 19

a code for which any sequence of code words has only one possible decoding;

a uniquely decodable code is not necessarily instantaneously decodable;

it may be necessary to wait until all of the code sequence has been received before earlier code words can be decoded;