4.Approbation of the received results

To analyze solved tasks. To assimilate methodic and formula for determining informational features of information sources and connection channels.

To make conclusions.

5.Test questions

1. The notion about excess coefficient

2. The notion about source producing.

3. Information transmission speed by channel.

4. Shannon theory on coding for discrete channel

List of References

1. Дмитриев В.И. Прикладная теория информации. -М.: Высшая школа, 1989, 320с.

2. Кавчук С.В. Сборник примеров и задач по теории информации. Руководство для практических занятий на базе Mathcad 6.0 Plus. Таганрог: Изд-во ТРТУ, 2002. 64 с.

3. Thomas M. Cover J.O.Y A. Thomas. A Elements of Information Theory. Second Edition John Wiley &Sons, Inc., Publication, 2006, 774p.

Laboratory work 6 Effective coding of messages. Codes of Shannon – Fano, Haffman.

The Purpose: Study of effective coding methods

1.Short theoretical data.

Problems of effective coding consist in the following:

1. Storing of the maximum quantity of the information in the limited memory.

2. Maintenance of the maximum Bandwidth of a source of messages.

The maximum quantity information I which can be transferred by a signal, is defined under the formula:

(1)

Where my - quantity of conditions of a signal.

The actual volume of the transferable information is defined by entropy of its set of messages Н. Because basically in a transferred set of messages there are typical sequences, messages are transferred with relative redundancy D:

(2)

It is necessary to apply effective coding to reduction of redundancy of symbols. The way of coding is called as effective, at which:

1. There is no information loss.

2. The minimum quantity of code symbols Is required.

For performance of the second condition non - uniform codes, where length of a code word inversely proportional probabilities of its occurrence in the message are used.

Use of effective coding is expedient, if probabilities of occurrence of various letters essentially differ, as thus entropy of set of letters (blocks) essentially less than their information capacity.

Effective coding is reached thanks to the account of aprioristic statistical characteristics of a source of the information.

Limiting possibilities of effective coding are defined:

(3)

At non equal probability messages the channel appears uncoordinated with

Information source there Fourier it isn't used to the full.

For example, if on an input of the binary discrete channel zero the relay acting in a role of the discrete demodulator, practically always is in the disconnected condition, i.e. without business arrive mainly. On the contrary, in case of transfers of one units of the relay will be alive always, and it could to be put, having short - circuited a channel exit. Thus, if to consider that speed of transfer through the discrete channel is the average quantity of the information passing through the channel in

Time unit in the considered cases it is small. On the other hand the maximum Bandwidth of a recreation center is defined through a pass - band of the continuous channel Δfk and can be defined:

Bit,

Where τ₀ - duration of one symbol.

Such bandwidth of a discrete channel will be realized when the average quantity of the information having on a symbol of a source too is maximum, for example, if specific entropy of a binary source is equal 1 bit/symbol.

If entropy H of a source is less, the channel under loaded even in that case when through it passes 2Δfk symbols in a second. Productivity of source R will be less Bandwidth of signal With.

Shannon has shown that it is possible to code source messages so that the average quantity of the information having on a symbol of a source, will be close to the maximum. This position is formulated in the theorem of Shannon of coding for channels without hindrances. If productivity of source R is less than Bandwidth of channel Ck, its messages can be coded so that speed of transfer can be somehow close to Bandwidth of channel.

According to definition, where - entropy of a source, T - average duration of a code combination: , here n_i - length of i th code combination.

From here,

For equality performance it is necessary, that , i.e. coding needs to be carried out so that length of code combinations of messages to put in dependence on quantity of the information which is transferred by the given message or from probability of the given message. Often meeting, i.e. малоинформативные messages, it is necessary to code the short combinations, seldom meeting - long. In this case on the average all messages of a source will be coded by smaller number of symbols, than at any other way of coding. For this reason the given code is called as optimum or effective and since at its creation probabilities of messages are considered, it is called as statistical and without dividing signs, since probably unequivocal decoding if by transfer there are no errors at the expense of hindrances.

The algorithm of optimum statistical coding was offered by Fano and Haffman. The technique of Fano consists in the following:

1. Messages subject to coding have in the first column in decreasing order of their probabilities.

2. Messages break on two groups with approximately equal total probabilities. To the group having the big total probability, the most probable symbol of a code combination, for example - 0, the second group - 1 is attributed.

3. The messages entering into each of groups, break again on two groups with approximately equal probabilities. Here again, group with greater probability the symbol - 0, with smaller - 1 is appropriated.

This process proceeds until in each group doesn't remain on one element.

Application of statistical coding has the big practical value. For example, at time consolidation of communication lines at night the majority of subscribers doesn't use phone, and the group signal in the communication line mostly consists of zero. Productivity of a source is much less than bandwidth of signal. To disconnect subscribers it is impossible, but their messages can be recoded a statistical code, they become much shorter, and during released time it is possible to transfer other messages, for example, telegrams, texts of newspapers, etc.

Let's consider a technique of such coding. Let the statistics of a digital stream is that: probability of zero P (0) = 0,9 then P (1 =0,1.To the table of the appendix 1 we define entropy of a source. Н=0,469 bit/symbol. Speed of transfer is much less than bandwidth of signal. For the coordination of a source with channel Shannon suggests to integrate coded sequences.

Let's code messages groups of two symbols. We will receive four messages which together with their probabilities we will present the table:

Table 1

00	0.81	0			0
01	0.09	1	1		11
10	0.09		0	0	100
11	0.01			1	101

Let's find entropy of a source, using the same table of the appendix.

Н=0,246+0,312+0,312+0,066=0,938 Bit/message. Average length of a code combination n = 0,81+0,09 *2 + 0,09 *3 + 0,01 *3 = 1,29 bit/message. Specific entropy of a source is equal to entropy of a source of messages, divide for average length of combinations: Н/n=0,727 bit / this. This entropy essentially above, than has been received earlier (0,469), accordingly, became above and speed of information transfer. At coding by groups of three messages specific entropy will be even more, and at the further integration of coded sequences speed of transfer will be somehow close to bandwidth of signal, i.e. to 1 / τ. Naturally, increase of speed demands corresponding expenses.

The coding device according to table 1 works as follows. At receipt on its input of a combination 00 it gives out in the communication line 0, at a combination 01 – 11 etc. At coding by groups of three symbols the coding device becomes more difficult, it should form eight groups of target symbols. At change of entrance statistics of the scheme of coding continue coding, but with smaller speed.

Representation of messages in the broad sense of the word is meant coding in the form convenient for transfer on the given channel. Operation of restoration of the message on the accepted signal is called as decoding. One of the coding purposes - by redundancy elimination to lower average of the symbols which are required on a letter the message, Give to drink absence of hindrances to it directly gives a gain in time of transfer or in memory volume, i.e. raises system effectiveness. There Fourier such coding has received the name effective, or optimum.

At construction of optimum codes the greatest distribution was received by techniques of Shannon - Fano and Haffman.

According to a technique of Shannon - Fano construction of an optimum code of ensemble from messages is reduced to the following:

1 й a step. The set from messages settles down in decreasing order of probabilities.

2 й a step. The initial ensemble of coded signals breaks on two groups so that total probabilities of messages of both groups were whenever possible equal.

3 й a step. To the first group the symbol 0, and the second group - a symbol 1 is appropriated.

4 й a step. Each of the formed subgroups divide on two parts so that total probabilities of again formed subgroups were whenever possible equal.

5 й a step. To the first groups of each of subgroups again it is appropriated 0, and the second - 1.

Thus, we receive the second figures of a code. Then each of four groups shares again on equal (from the point of view of total probability) parts until in each of subgroups doesn't remain on one letter.

According to a technique of Haffman, for construction of optimum code N symbols of the primary alphabet leave in decreasing order of probabilities. The last n₀ symbols where 2≤ n₀ ≤m and - an integer, unite in some new symbol with the probability equal to the sum of probabilities of incorporated symbols. Last symbols taking into account the formed symbol unite again, receive a new, auxiliary symbol, again write out symbols in decreasing order of probabilities taking into account an auxiliary symbol and so on until the sum of probabilities m the remained symbols won't give the probability equal 1 in the sum. In practice usually don't make repeated выписывания probabilities of symbols taking into account probability of an auxiliary symbol, and manage the elementary geometrical constructions which essence is reduced to that symbols of the coded alphabet in pairs unite in new symbols, since the symbols having the least probability. Then taking into account again formed symbols by which value of total probability of two previous is appropriated, build a code tree in which top there is a symbol 1.

Constructed by the techniques specified above codes with non - uniform distribution of the symbols, having the minimum average length of a code word, name optimum non - uniform codes, or effective.

Having considered techniques of construction of effective codes, it is easy to be convinced that the effect is reached thanks to assignment of shorter code combinations to more probable letters. Thus, the effect is connected with distinction among symbols of code combinations. And it leads to difficulties at decoding. For this purpose the effective code is necessary for building so that any combination of a code didn't coincide with the beginning of longer combination. The codes, satisfying to this condition, are called prefix as codes. It is easy to be convinced that the codes received as a result of application of a technique of Shannon - Fano or Haffman are prefix.

Efficiency optimum non - uniform codes estimate by means of factor of statistical compression:

Ксс=Нмах/Iср,

Which characterizes reduction of quantity of binary signs by a message symbol at application optimum non - uniform codes in comparison with application of methods of no static coding and factor of relative efficiency of Koe=N/Isr which shows, statistical redundancy of the transferred message is how much used.