конспект ТЭС кодирование сообщений нов

ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖ СВЯЗИ

ТЕОРИЯ ЭЛЕКТРИЧЕСКОЙ СВЯЗИ

Конспект лекций

Минск

2010

МИНИСТЕРСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ РЕСПУБЛИКИ БЕЛАРУСЬ Учреждение образования

«ВЫСШИЙ ГОСУДАРСТВЕННЫЙ КОЛЛЕДЖ СВЯЗИ» Кафедра радиосвязи и радиовещания

ЭФФЕКТИВНОЕ И ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ СООБЩЕНИЙ

конспект лекций по дисциплине

«ТЕОРИЯ ЭЛЕКТРИЧЕСКОЙ СВЯЗИ»

для студентов специальности 2-45 01 02 — Системы радиосвязи, радиовещания и телеви-

дения

Минск

2010

2

УДК 621.3 ББК 32.88 Т11

Рекомендовано к изданию кафедрой радиосвязи и радиовещания , протокол №

Составитель В. И. Лупачева, преподаватель первой категории

кафедры радиосвязи и радиовещания

Рецензент А. И. Корзун, зав. кафедрой радиосвязи и радиовещания,

доцент, канд. техн. наук

Теория электрической связи : конспект лекций по теме «Эф-

Т11 фективное и помехоустойчивое кодирование сообщений» для студентов специальности 2-45 01 02 – Системы радиосвязи, радиовещания и телевидения, / сост.В. И. Лупачева. – Минск : ВГКС, 2010. – с.

ISBN 978-985-6866-96-1.

В конспекте лекций изложены основы помехоустойчивого и статистического эффективного кодирования дискретных сообщений. Рассмотрены методы эффективного кодирования сообщений неравномерными кодами Шеннона-Фано и Хаффмана. Приведены сведения о словарных методах сжатия информации. Подробно описаны алгоритмы кодирования и декодирования блочных помехоустойчивых кодов Хэмминга, циклических кодов и др. Излагаемый материал поясняется рисунками и многочисленными примерами.

Для студентов и преподавателей ВГКС.

	УДК 621.3
	ББК 32.88
ISBN 978-985-6866-96-1	© Учреждение образования
978-985-6866-35-0	«Высший государственный
	колледж связи», 2010

3

ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ

Кодирование − процесс преобразования элементов сообщения в кодовые комбинации (слова, последовательности) с целью их передачи, обработки и хранения. Устройство, осуществляющее кодирование информации, называется кодером.

Кодовая комбинация (слово, последовательность) − конечная совокупность кодовых символов, соответствующая определенному сообщению.

Код − совокупность символов и система определенных правил, при помощи которых дискретные сообщения могут быть представлены в виде кодовых комбинаций из этих символов. Коды могут задаваться различными способами: в виде таблиц, матриц, формул, графиков и т. д.

Основание кода m − количество стандартных символов, с помощью которых производится кодирование сообщения. В электросвязи чаще всего применяют двоичные коды (m=2). Кроме двоичных, существуют многопозиционные (недвоичные) коды (m>2), например, квазитроичные.

Первичный алфавит кода − набор знаков, из которых формируется сообщение.

Алфавит кода, или вторичный алфавит, − символы, исполь-

зуемые для составления любого кодового слова. В рассматриваемых ниже двоичных кодах алфавит содержит два символа: "0" и "1". Обычно в качестве стандартного электрического сигнала символу "1" соответствует прямоугольный импульс тока или напряжения положительной полярности, а символу "0"- отсутствие импульса. Иногда символу "0" соответствует импульс отрицательной полярности.

Разряд кода − одна двоичная цифра ("0" или "1"), входящая в кодовое слово. Так, двоичное слово "1101"- четырехразрядное.

Равномерный код − код, кодовые слова которого содержат одинаковое число символов n, где n − разрядность (значность) кода.

Неравномерный код − код, кодовые слова которого содержат разное число символов.

Декодирование − восстановление знаков сообщения из кодовых слов. Устройство, выполняющее эту операцию, называется

4

декодером. Зачастую кодер и декодер объединяются в единое устройство − кодек.

Мощность кода М − число кодовых комбинаций, выбранных для передачи сообщений.

Другие термины и определения будут приведены далее по тексту по мере необходимости.

КОДИРОВАНИЕ СООБЩЕНИЙ В ЦИФРОВЫХ СИСТЕМАХ ПЕРЕДАЧИ

Цифровые системы передачи обладают рядом несомненных преимуществ перед аналоговыми системами. В частности, цифровые системы обеспечивают возможность кодирования сообщений с целью уменьшения их избыточности, повышения помехоусойчивости передачи и устранения возможности несанкционированного доступа к передаваемой информации.

Обобщенная структурная схема тракта передачи сигналов электросвязи с кодированием сообщений приведена на рисунке

1.

1			2			3			4			5			6				8			9			10			11			12
															7

Рисунок 1 − Обобщенная структурная схема тракта передачи сигналов электросвязи с кодированием сообщений

1. источник дискретных сообщений; 2. эффективный кодер; 3. криптографический кодер; 4. помехоустойчивый кодер; 5. линейный кодер; 6. линия передачи; 7. источники помех; 8. линейный декодер; 9. помехоустойчивый декодер; 10. криптографический декодер; 11. эффективный декодер; 12. получатель сообщений.

Как видно на рисунке 1, на стороне передатчика поэтапно осуществляются различные виды кодирования передаваемых сообщений, а на стороне приемника соответствующее декодиро-

5

вание. При этом сообщения должны быть дискретными. Если исходный сигнал непрерывный, он должен быть преобразован в дискретный.

На стороне передатчика сообщения из источника дискретных сообщений 1 поступают в эффективный кодер 2, обеспечивающий сжатие объема передаваемой информации (компрессию) с целью сокращения ее избыточности. Причем сжатие может осуществляться как с потерями информации, так и без потерь. С выхода эффективного кодера 2 информация в виде кодовых комбинаций, соответствующих определенным сообщениям (цифровой сигнал), поступает на криптографический кодер 3 (от греческого «kryptos» - тайный, скрытый и «grapho» - пишу). В криптографическом кодере информация шифруется (засекречивается) с целью предотвращения несанкционированного доступа к передаваемым сообщениям как для извлечения из них сведений, так и для введения в них ложной информации. В помехоустойчивом кодере 4 кодовые комбинации символов, полученных из кодера 3, вновь кодируются. Причем в них вводится определенным образом избыточность и число разрядов в каждой из кодовых комбинаций при этом увеличивается. Эта сознательно водимая избыточность позволяет на приемной стороне обнаруживать и исправлять ошибки передачи цифрового сигнала. В линейном кодере 5 цифровой сигнал приводится к виду, пригодному для его представления в линии передачи 6. При этом учитывается среда распространения сигнала. Например, в случае радиолинии линейный кодер 5, кроме прочего, должен содержать модулятор.

В линии передачи 6 сигналы электросвязи подвергаются воздействию помех от различных источников 7, в результате чего в передаваемый сигнал вносятся ошибки.

На стороне приемника, поступивший из линии передачи 6 сигнал в линейном декодере 8 приводится к виду, удобному для декодирования. Вначале помехоустойчивый декодер 9 по определенному алгоритму анализирует принятые комбинации символов и, благодаря имеющейся в них избыточности (введена в

помехоустойчивом кодере 4), обнаруживает и исправляет ошибки передачи. С выхода декодера 9 исправленные кодовые комбинации (без избыточности) поступают в криптографический

6

декодер 10, обеспечивающий раскрытие зашифрованной информации, то есть ее дешифрацию. Далее в эффективном декодере 11 осуществляется разжатие (декомпрессия) информации и восстановление ее первоначального содержания с потерями или без потерь (в зависимости от алгоритма сжатия). К получателю сообщений 12 информация поступает в удобном для его восприятия виде.

В общем случае в цифровых системах передачи криптографический и помехоустойчивый кодеры можно поменять местами, но тогда необходимо поменять местами и соответствующие им декодеры. Эффективный кодер всегда подключают к источнику дискретных сообщений, поэтому этот кодер еще называют «кодером источника». В зависимости от вида передаваемых сообщений кодеры и соответствующие им декодеры могут отсутствовать. Например, в случае телевизионного вещания нет необходимости в криптографическом кодировании. Ниже будут рассмотрены основы эффективного и помехоустойчивого кодирования сообщений.

ЭФФЕКТИВНОЕ КОДИРОВАНИЕ

Общие сведения

Кодирование, обеспечивающее уменьшение избыточности в закодированном сообщении, называют эффективным. Избыточность источника может быть вызвана статистическими свойствами сообщений (наличие статистических связей между сообщениями и/или различные вероятности появления отдельных сообщений), психофизиологическими особенностями восприятия звука и изображения органами чувств человека и другими причинами.

Количественно избыточность источника дискретных сообщений определяется коэффициентом избыточности

	æ =	Hmax ( A ) −H( A )	=1−	H( A )	,
				Hmax ( A )
		Hmax ( A )

7

где Hmax (A) − максимальная энтропия источника, формирую-

щего М независимых равновероятных сообщений;

H( A )− энтропия источника, вычисленная на основе стати-

стических характеристик М разновероятных сообщений. Коэффициент æ показывает, какая доля максимально воз-

можной энтропии не используется источником. Максимальная энтропия двоичного источника дискретных сообщений опреде-

ляется по формуле Нmax ( A ) = log2 M . Фактическая энтропия

источника	H( A )	определяется	выражени-
	M
емH( A ) = −∑p( ai )log2		p( ai ) ,

i=1

где р(аi)- вероятность появления сообщения аi.

Сокращение избыточности возможно путем сжатия (компрессии) объема передаваемой источником информации. Сокращение статистической избыточности проводится без потери информации. Энтропия источника при этом не уменьшается. При сокращении психофизиологической избыточности происходит необратимая потеря части информации, несущественной для получателя и энтропия источника уменьшается. Оставшуюся часть сообщения, существенную для получателя, подвергают далее повторному кодированию с целью уменьшения статистической избыточности.

Для характеристики эффективности сжатия применяют коэффициент сжатия или обратную ему величину − степень сжатия.

Коэффициент сжатия − это отношение длины сжатых данных к длине соответствующих им несжатых данных.

Степень сжатия − отношение длины несжатых данных к длине соответствующих им сжатых данных.

Эффективные коды можно использовать в тех случаях, когда кодовая последовательность не подвергается воздействию помех. При наличии помех ошибочный прием всего лишь одного кодового символа может изменить переданное сообщение до неузнаваемости. Поэтому эффективными кодами кодируют только источники сообщения. Эффективное статистическое кодирование без потери информации можно реализовать путем

8

создания специальных словарей или используя неравномерные коды (в зависимости от причин избыточности). Для сокращения психо - физиологической избыточности разработаны специальные стандарты сжатия информации с потерями.

Кодирование неравномерными кодами

Эффективное кодирование неравномерными кодами применяют для устранения или уменьшения избыточности источника с различными вероятностями появления отдельных сообщений. При этом более вероятные сообщения кодируют короткими кодовыми словами, а менее вероятные - длинными. По такому принципу построена азбука Морзе, в которой часто используемым символам поставлены в соответствие короткие последовательности точек и тире, а редко встречающимся - длинные.

Для обеспечения однозначности декодирования необходимо после каждого сообщения передавать некоторый разделитель, не совпадающий ни с одной из кодовых комбинаций. Это значительно снижает эффективность кодирования. Чаще идут по другому пути - используют неравномерные коды, удовлетворяющие префиксному свойству: никакое более короткое слово кода не является началом (префиксом) другого более длинного слова кода. В таблице 1 пять сообщений закодированы двумя неравномерными кодами, из них код 1 - непрефиксный, а код 2 - префиксный. Существует несколько алгоритмов построения префиксных кодов. Рассмотрим коды Шеннона-Фано и Хаффмана.

Таблица 1 − Примеры кодов

	Сообщение			и	соответству-
Номер кода	ющее ему кодовое слово						Вид кода
	а1	а2		а3	а4	а5
1	0	01		10	00	010	Непрефиксный
2	10	110		01	111	000	Префиксный

Коды Шеннона-Фано

9

Алгоритм кодирования кодом Шеннона-Фано состоит в следующем:

1 Все сообщения источника располагают в таблице в один столбец в порядке убывания их вероятностей.

2 Сообщения разбивают на две группы таким образом, чтобы суммарные вероятности каждой из этих групп были, по возможности, почти равными.

3 Сообщениям верхней группы в качестве первого символа кодового слова присваивают символ - "0", а нижнего - "1" (или наоборот).

4 Каждая из полученных групп, если она содержит более одного сообщения, делится на две подгруппы, имеющие, по возможности, равные суммарные вероятности. В качестве второго символа кодового слова используется "0" или "1" в зависимости от принадлежности сообщений верхней или нижней подгруппе (как в п. «Кодирование неравномерными кодами»).

5 Процесс повторяется до тех пор, пока в каждой подгруппе не останется по одному сообщению.

Пример 1 Требуется закодировать кодом Шеннона-Фано во-

семь сообщений а1, а2, а3, а4, а5, а6, а7, а8, имеющих следующие вероятности появления р(а1)=0,12;

р(а2)=0,03; р(а3)=0,2; р(а4)=0,15; р(а5)=0,07; р(а6)=0,13; р(а7)=0,10; р(а8)=0,2.

Результаты кодирования сообщений кодом Шеннона-Фано приведены в таблице 2

Таблица 2− Кодирование сообщений кодом Шеннона-Фано

	Сообщения	Вероят-	Этапы разбиения на группы				Кодовая
		ности	и подгруппы				комбина-
	аi	p( ai )					ция
			1-й	2-й	3-й	4-й
	а3	0,2	0	0			00
	а8	0,2		1	0		010
	а4	0,15			1		011
	а6	0,13	1	0	0		100

10