Шпоры по ТПИ


21). Пропускная способность дискретного канала, по которому передается  дискретных сигналов вычисляется по формуле :
, (4.8)
где    – скорость модуляции, бод;  – длительность сигнала;  – вероятность ошибки в канале. Заметим, что пропускная способность дискретного канала без помех при ():
.  
В частности пропускная способность двоичного канала ():
.
22). Рассмотрим спектральное разложение периодического сигнала. Будем считать, что периодический сигнал определен на бесконечном интервале и может представлен в виде ряда Фурье:
, (1.15)
где    ,     - амплитуда, - начальная фаза  - ой гармоники.

S(t) – прямоугольные импульсы,
23). Совокупность всех гармонических составляющих разложения функции в ряд Фурье называется спектром функции.периодический сигнал неограничен во времени, но ограничен по спектру.

24). Для спектрального представления непериодических (импульсных) сигналов , заданных на конечном интервале (, ) , непосредственно воспользоваться рядом Фурье нельзя. Для гармонического разложения сигнала мысленно дополняют его такими же импульсными сигналами до периодического с некоторым интервалом


25). Сигналы этих групп могут быть непрерывными или дискретными. Непрерывным называется сигнал, который принимает все возможные значения от xmin до xmax на заданном отрезке времени t. Дискретным называется сигнал квантованный по времени или уровню, или одновременно. q – шаг квантования (разрешающая способность преобразователя),ε – ошибка квантования
Ошибка ε является принципиальной для квантования по уровню. Она может быть уменьшена только увеличением разряда длины преобразователя n. n ограничена сверху наличием помех, начиная ,,, и при данной мощности помех реальное перемещение мощности не происходит, потому что n сравнима с уровнем ,,, ε считается случайной. Для ошибки, как для случайной величины принимается гипотеза стационарности, тогда математическое ожидание M[ε]=0, а дисперсия D=q2/12= ε2 => ε=q/2√3. Различают линейные и нелинейные шкалы квантования. Если величина q во всём диапазоне x постоянна, то шкала равномерная. Однако линейные шкалы не всегда выгодны. Целью применения линейных шкал является повышение точности в том диапазоне изменения шкалы, в которой он несёт информацию

26). Дискретизация значений непрерывной функции  по уровню называется амплитудным квантованием. В результате квантования непрерывный сигнал заменяется ступенчатой функцией. Шаг квантования  (расстояние между двумя соседними разрешенными уровнями) может быть как постоянным, так и переменным. Его обычно выбирают из условий обеспечения требуемой точности восстановления непрерывного сигнала из квантованного.

n=0, 1, 2 …T0 – период квантованияΔ – функции,x[nT0] – решётчатая функция, порожденная неопределённой функцией x(t).
U[nT0] – единичная последовательность, вырабатываемая, которая управляет ключом, замыкая его по закону Δ – функции.
x=∑∞n=0 x[nT0]. Для определения величины T0 используется теорема Котельникова: T0≤1/2fmax; fmax – максимальная частота спектра квантуемого сигнала.
27). Код — это набор условных обозначений (или сигналов) для записи (или передачи) некоторых заранее определенных понятий.
Кодирование информации – это процесс формирования определенного представления информации. В более узком смысле под термином «кодирование» часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки. В более узком смысле под термином "кодирование" часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки. Компьютер может обрабатывать только информацию, представленную в числовой форме. Вся другая информация (например, звуки, изображения, показания приборов и т. д.) для обработки на компьютере должна быть преобразована в числовую форму. Например, чтобы перевести в числовую форму музыкальный звук, можно через небольшие промежутки времени измерять интенсивность звука на определенных частотах, представляя результаты каждого измерения в числовой форме. С помощью программ для компьютера можно выполнить преобразования полученной информации, например "наложить" друг на друга звуки от разных источников.
Аналогичным образом на компьютере можно обрабатывать текстовую информацию. При вводе в компьютер каждая буква кодируется определенным числом, а при выводе на внешние устройства (экран или печать) для восприятия человеком по этим числам строятся изображения букв. Соответствие между набором букв и числами называется кодировкой символов.
Как правило, все числа в компьютере представляются с помощью нулей и единиц (а не десяти цифр, как это привычно для людей). Иными словами, компьютеры обычно работают в двоичной системе счисления, поскольку при этом устройства для их обработки получаются значительно более простыми. Ввод чисел в компьютер и вывод их для чтения человеком может осуществляться в привычной десятичной форме, а все необходимые преобразования выполняют программы, работающие на компьютере.
28). Шифрование — кодирование, призванное обеспечить её защиту от чтения, модификации, подделки злоумышленником. Иногда шифрованием называют любое кодирование.
Сжатие информации — разновидность кодирования, предназначенное для уменьшения объёма передаваемой или хранимой информации.
Помехоустойчивое кодирование — кодирование, предназначенное для передачи данных по каналам с помехами, обеспечивающее исправление возможных ошибок передачи вследствие помех.
Перекодирование между форматами файлов — преобразование одного формата в другой для возможности его использования определённым программным обеспечением. Частный случай — изменение кодировки символов.
29). Избыточным называется обратимое кодирование, если обратное перекодирование возможно по части кодированной информации. Иногда избыточность является побочным эффектом кодирования и от него стараются избавиться, но есть виды, избыточность которых играет основную роль.
Избыточными являются многие виды помехоустойчивого кодирования. В простейшем случае к данным добавляется контрольная сумма, обеспечивающая диагностику искажения информации. Продвинутые виды кодирования вносят дополнительную информацию, которая обеспечивает восстановление после определённых видов потерь и/или искажений. Известные и широкоиспользуемые методы — код Хемминга, код Рида-Соломона. Также помехоустойчивое кодирование применено во многих видах штрих-кодов. Неизбыточным помехоустойчивым кодированием является скремблирование. Различают обратимое и необратимое кодирование.
Обратимое кодирование это кодирование, для которого существует способ кодирования обратного, приводящего перекодированную информацию к точному исходному виду. Обратное кодирование обычно называется декодированием. В данном контексте кодированием называется преобразование из оригинального формата в кодированный, декодированием — приведение обратно в оригинальный. Под оригинальным форматом следует понимать формат, который можно использовать прямо по назначению, под кодированным — требующий декодирования.
Примерами обратимого кодирования являются шифрование, сжатие информации без потерь, помехоустойчивое кодирование. Эти виды кодирования всегда используются в паре с обратными: шифрование — дешифрование, сжатие — разжатие и т. п.
Необратимое кодирование обратного преобразования не имеет. Для некоторых способов необратимого кодирования существуют способы получения приблизительного восстановления, которые также называются декодированием.
Наиболее широко распространённым видом необратимого кодирования является сжатие информации с потерями (например при кодировании, т.н. "захвате" видеоинформации), которое сопровождается потерей незначимой или малозначимой информации.
Примером необратимого кодирования является аналого-цифровое преобразование. Декодирование (цифро-аналоговое преобразование) в этом случае воспроизводит исходную (имевшую место до кодирования) информацию лишь приблизительно, с искажениями, «потерями».
Хэширование является разновидностью кодирования, необратимость которого имеет первостепенное значение. Хотя хэширование ближе к подсчёту контрольных сумм, нежели к кодированию как таковому.
30). Коды, формирующие кодовые комбинации различной длины, называются неравномерными, а одинаковой – равномерными. Длина кодовых комбинаций равномерного кода называется значностью кода. Процесс обратный кодированию – декодирование. Суть декодирования в том, что по имеющийся кодовой комбинации с помощью правила Г, восстанавливается входное слово. Г-1(abaabababb)=qprrs. Важной проблемой является проблема однозначности, т.е. код должен быть таким, чтобы любая кодовая комбинация декодировалась в неповторяющиеся слова. Обычно входным алфавитом является символы естественного языка, математических действий, спец знаки ($,%). Символами выходного алфавита: 0 и 1.
Пример: A={p,q,r,s}, B={a,b}. Г(qprrs)=abaabababb.
31). Код Грея кодирования чисел так, что соседние числа имеют одну цифру , отличающихся 1. The term Gray code is often used to refer to a "reflected" code, or more specifically still, the binary reflected Gray code. Термин коде Грея часто используется для обозначения "отражение" код, или, более конкретно еще, двоичный код Грея отражение.
Чтобы преобразовать двоичный номер to its corresponding binary reflected Gray code, start at the right with the digit в соответствующий двоичный отраженный код Грея, начинаются с правой цифры (the ( th, or last, digit ). м, или последний, цифры ). If the Если is 1, replace 1, заменить by по ; otherwise, leave it unchanged. В противном случае, оставить его без изменений. Then proceed to Затем переходите к . . Continue up to the first digit Продолжить до первой цифры , which is kept the same since , Которая хранится же так is assumed to be a 0. Предполагается, что 0. The resulting number Полученное число is the reflected binary Gray code. является отражение двоичный код Грея. Чтобы преобразовать двоичный отраженный код Грея to a binary number, start again with the для бинарных номер, начать снова th digit, and compute го разряда, и вычислить

Если is 1, replace 1, заменить by по ; otherwise, leave it the unchanged. В противном случае, оставить его без изменений. Next compute Следующая вычислить
32). Стати́ческий ана́лиз ко́да (англ. static code analysis) — анализ программного обеспечения, производимый без реального выполнения исследуемых программ (анализ, производимый с выполнением программ называется динамический анализ кода). В большинстве случаев анализ производится над какой-либо версией исходного кода, хотя иногда анализу подвергается какой-нибудь вид объектного кода, например P-код или код на MSIL. Термин обычно применяют к анализу, производимому специальным ПО, тогда как ручной анализ называют пониманием или постижением программы.
В зависимости от используемого инструмента глубина анализа может варьироваться от определения поведения отдельных операторов до анализа, включающего весь имеющийся исходный код. Способы использования полученной в ходе анализа информации также различны — от выявления мест, возможно содержащих ошибки, до формальных методов, позволяющих математически доказать какие-либо свойства программы (например, соответствие поведения спецификации
33). Рассмотрим код Хаффмана: строится по алгоритму кодового дерева, построение графа начинается с висячих вершин. Их число соответствует количеству сообщений. Вес каждой вершины – это есть вероятность появления соответствующего сообщения. И перед началом работы висячие вершины упорядочиваются по мере увеличения высот. Шаг 1: определеяется число поддеревьев графа. Если оно меньше 2, то дерево построено, если нет – шаг 2. Шаг 2: выбирается 2 вершины с минимальными весами и сравниваются. Получаается новая вершина и 2 ребра. Новая вершина имеет вес = сумме исходных вершин. Левое ребро получается 1, правое – 0. Возврат к шагу 1. В результате построения дерева получается корень всегда = 1. Чтобы получить кодовую комбинацию i-го сообщения необходимо от корня дерева спустится по ребрам к i-ой висячей вершине, выписав при этом метки ребер этого пути.
ПРИМЕР: 8 сообщений, X={x1,…x8}, B={0,1}, P1=0,19, P2=0,16, P3=0,16, P4=0,15, P5=0,12, P6=0,11, P7=0,09, P8=0,02.
Пусть обратно (чем чаще сообщение, тем короче код), x1:01, x2:111, x3:110, x4:101, x5:100, x6:001, x7:0001, x8:0000. Самые мелкие вершины сращиваем
Оценим степень эффективности полученного кода. Для этого (**)
xi кодовая комбинация ni ni*Pi -Pi*log2 Pi
X1 11 2 0,38 -0,19*log20,19
X2 011 3 0,48 -0,16*log20,16
X3 010 3 0,48 -0,16*log20,16
X4 001 3 0,45 -0,15*log20,15
X5 000 3 0,36 -0,12*log20,12
X6 101 3 0,33 -0,11*log20,11
X7 1001 4 0,36 -0,09*log20,09
X8 1000 4 0,08 -0,02*log20,02
Посчитаем после nср = 2,92 бит, H(x)=2,85 бит.
H(x)/log2m = nmin = 2,85 бит, Kи=(nср – nmin)/nср = 0,024, 2,4% - избыточность кода Хаффмана для этого примера.

34). 1) вся последовательность символов упорядочивается по убыванию значения их вероятности. 2) последовательность разбивается на 2 по возможности равновероятные группы,
3) первой группе присваивается символ “0”, второй – “1”.
4) каждая получившаяся группа развивается по возможности равновероятные и т.д. пока деление на группы возможно.
Пример: 5 событий и p1=0,4, p2=0,3, p3=0,15, p4=0,1, p5=0,05.
nср = ∑[i=1, 5] Pi * ni = 2,05 бит,
H(x)= - ∑[i=1, 5] Pi * log2 Pi=2,01 бит,
log2m=1, Ки = (2,85 – 2,01)/2,05 =0,02=2%
Знание эффективных кодов позволяет
ответить на вопрос – какова должна
быть минимальная длина кодовых
комбинаций, чтобы передать
информацию, заложенную в источник сообщения при отсутствии помех. Меньше уровня не должно быть. На нем можно создавать надстройку, т.е. вводить дополнительные разряды для решения задач борьбы с помехами. Как правило, кодовые комбинации эффективных кодов имеют разную длину для разных сообщений. Это приводит к необходимости отмечать специальными символами начало и конец передачи сообщения, что усложняет и замедляет передачу. Коды, имеющие разную длину кодовых комбинаций, называются неравнозначными.
35). Расстояние Хэмминга — число позиций, в которых соответствующие цифры двух двоичных слов одинаковой длины различны[1]. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Наибольшее распространение среди линейных групповых кодов с использованием ошибки получили КОД ХЭММИНГА. Он имеет следующую структуру порождающей матрицы: (n, k). Код Хэмминга имеет структуру: (2in - 1, 2m-1-m), m=3,4… Если m=3, то (7,4).
Если построить матрицу H для этого кода, то она будет иметь такой вид:
H=||1101 100; 1011 010; 0111 001||. Количество строк = m. Каждый разряд образует m-разрядное двоичное число. H=||6537421||. Код Хэмминга настолько популярен, что выпускаются стандартные микросхемы, поэтому, когда организуется вычислительная сеть, то каждый компьютер снабжается кодером и декодером. Пользователь работает с информационными словами, но прежде чем уйти в канал связи сети, слово проходит через микросхему кодера и в принимаемом компьютере поступает в декодер.
СИСТЕМАЧЕСКИЕ И НЕСИСТЕМАТИЧЕСКИЕ.
Пользователь работает с информационными словами, но прежде чем уйти в канал связи сети, слово проходит через микросхему кодера и в принимаемом компьютере поступает в декодер.
Различают систематические и несистематические линейные групповые коды, в том числе и код Хэмминга. В систематических кодах информационное слово занимает первые k разрядов, а проверочное оставшиеся n-k. В несистематических кодах проверочные разряды вкраплены в определенные позиции кодового слова. В систематическом коде Хэмминга вид синдрома с номером ошибочного разряда связаны через таблицу. В несистематическом коде Хэмминга вид синдрома представляется двоичным числом, которое представляет собой номер ошибочного разряда.
Рассмотрим пример построения несистематического кода – построить код Хэмминга для n=17.
1) Определяется количество проверочных разрядов, в данном коде r ≥ ]log2(n+1)[ - ближайшее целое сверху. r = 5 для нашего случая.
Проверочные уравнения: a16+a17=0 (выписываем a, те где в таблице стоит
36) Код с проверкой четности. Код с проверкой четности образуется добавлением к группе информационных разрядов, представляющих простой (неизбыточный) код, одного избыточного (контрольного) разряда..код с проверкой четности имеет небольшую избыточность и не требует больших затрат оборудования на реализацию контроля. Этот код широко применяется в вычислительных машинах для контроля передач информации между регистрами и для контроля считываемой информации в оперативной памяти.
При построении схем определения четности суммы 1 слова используют логические элементы с парафазным выходом, подобные изображенному на рис. 1, a) и б). Показанные схемы выполняют операцию сложения по модулю 2 (условное обозначение М2) для двоичных переменных х и у. На рис. 1, в показана схема определения признака четности байтов.
Каждый информационный символ должен быть задан прямым и инверсным кодом. Структура схемы проверки четности является многоступенчатой, т. е. слово делится на несколько групп разрядов, в каждой из которых проверка четности производится прямым способом (первая ступень), далее производится проверка четности для групп второй ступени, образованных из групп первой ступени, четности которых в этом случае рассматриваются как обычные двоичные разряды, и т. д. до окончательной проверки четности суммы 1 всего слова. В последней ступени четность байта сравнивается со значением контрольного разряда КР.

37). При контроле по нечетности контролируется полное пропадание информации, поскольку кодовое слово, состоящее из О, относится к запрещенным. Если в математическом коде выделен один контрольный разряд (k=1), то к каждому двоичному числу добавляется один избыточный разряд и в него за-писывается 1 или 0 с таким условием, чтобы сумма цифр в каждом числе бы-ла по модулю 2 равна 0 для случая нечетности. Появление ошибки в кодиро-вании обнаружится по нарушению четности (нечетности).
38). Код с постоянным весом в каждой кодовой комбинации содержит одинаковое количество “1”.
(5,2)
045720
Коды с постоянным весом строятся по очень простому алгоритму и эффективны для установления факта одиночной ошибки. Корректирующая способность равна 0, обнаруживающая способность равна 1.
39). Правильность принятых комбинаций в кодах определяется подсчетом числа единиц и если, например, в коде принято не три единицы, то при передаче произошла ошибка. Код обнаруживает любые одиночные искажения, а также многие двойные, тройные и другие искажения.
В инверсном коде исходная n-разрядная двоичная комбинация дополняется другой также n-разрядной, составленной по определенному правилу. В линию посылается удвоенное число импульсов (2п). Правило образования кода следующее: если в исходной комбинации четное число единиц, то добавляемая комбинация повторяет исходную, а если нечетное, то в добавляемых п разрядах все нули превращаются в единицы, а единицы в нули. Таким образом комбинация 0101 в инверсном коде будет передана, как 01010101, а комбинация 1000 — как 10000111. Коэффициент избыточности этого кода /СИЗО = 0,5. При приеме кодовой комбинации выполняются две операции. Сначала суммируются единицы, содержащиеся в первых п элементах Если их число оказывается четным, то вторая группа из п элементов принимается без изменения, если нечетной, то вторая группа символов инвертируется (0->-1 и 1-»-0). После этого обе зафиксированные комбинации сравниваются поэлементно и при выявлении хотя бы одного несовпадения делается вывод о наличии искажения. Ошибка в данном коде будет обнаружена только в том случае, если одновременно исказятся два элемента в исходной комбинации и соответствующие им два элемента в повторяемой комбинации.
40). В корреляционном коде каждый элемент исходного кода преобразуется в два, при этом 1 преобразуется в 10, а 0 в 01. Так, например, комбинация 0110 исходного кода в корреляционном коде запишется, как 01101001 У корреляционного кода так же, как и у инверсного, Кизб=: 0,5. На приеме ошибка обнаруживается в том случае, если в парных элементах будут содержаться одинаковые символы, т. е. 00 или 11. Этот код обладает высокой помехоустойчивостью, ошибка не будет обнаружена только в том случае, если искажениям подвергнутся два рядом стоящих символа, соответствующие одному элементу исходного кода.
Под корреляционными подразумевают коды, обладающие хорошими корреляционными свойствами, важными при передаче сигналов вхождения в связь, для повышения защищенности от некоторых видов помех, извлечения сигналов из интенсивных шумов, обеспечения многостанционного доступа, построения асинхронно-адресных систем связи. Корреляционные коды включают в себя пары противоположных сигналов с хорошей функцией автокорреляции (метод внутриимпульсной модуляции), импульсно-интервальные коды, имеющие на фиксированном интервале времени постоянное для всех слов кода число импульсов с неперекрывающимися (при любом взаимном сдвиге слов во времени) значениями интервалов между импульсами, ансамбли сигналов с хорошими взаимокорреляционными свойствами
41). Блочный код заменяет каждый блок из символов более длинным блоком из символов, которые после передачи подлежат декодированию. Из соображений простоты и надежности большинство систем связи конструируются для передачи двоичных последовательностей, такими являются и -коды. Одним из ключевых понятий теории кодирования является понятие расстояния между двоичными словами. Расстояние между словами и равно числу позиций, в которых . Весом слова называется число единиц среди его координат. Тогда расстояние будет равно весу , т.е. .
42). Код Хэмминга представляет собой блочный код, который позволяет выявить и исправить ошибочно переданный бит в пределах переданного блока. Обычно код Хэмминга характеризуется двумя целыми числами, например, (11,7) используемый при передаче 7-битных ASCII-кодов. Такая запись говорит, что при передаче 7-битного кода используется 4 контрольных бита (7+4=11). При этом предполагается, что имела место ошибка в одном бите и что ошибка в двух или более битах существенно менее вероятна. С учетом этого исправление ошибки осуществляется с определенной вероятностью. Например, пусть возможны следующие правильные коды (все они, кроме первого и последнего, отстоят друг от друга на расстояние 4):
00000000111100000000111111111111
При получении кода 00000111 не трудно предположить, что правильное значение полученного кода равно 00001111. Другие коды отстоят от полученного на большее расстояние Хэмминга.

Приложенные файлы

  • docx 9123584
    Размер файла: 521 kB Загрузок: 0

Добавить комментарий