Московский государственный институт электроники и математики
(технический университет)
Кафедра ИКТ
Отчет по лабораторной работе
«Порождающая и проверочная матрицы. Кодирование и декодирование.»
По дисциплине: «Основы теории информации и кодирования»
Выполнил:
студент группы С-65
Преподаватель:
Оглавление
Цель и задачи лабораторной работы
Целью данной лабораторной работы является практическое освоение представления линейных кодов в матричном виде.
В процессе работы создана программа, наглядно показывающая кодирование любого двоичного слова с помощью порождающей и проверочной матрицы и декодирование полученного слова с исправлением любой одиночной ошибки.
Выполнение
Теоретические сведения
Одно из основных свойств линейных кодов заключается в том, что большая часть разрешённых комбинаций кода может получаться путём поразрядного сложения по mod2 других двух разрешённых комбинаций. Это свойство и даёт возможность представлять коды в матричном виде. Построить любой код это означает задание всех разрешённых комбинаций кода. Очевидно, что если информационная часть числа m, то количество разрешённых комбинаций 2m — мощность кода.
Оказывается, что среди всех разрешённых комбинаций имеются линйно независимые комбинации, называемые базовыми и линейно зависимые. Если кодовая комбинация:
a1, a2, … , am, e1, e2, … , ek,
где a — информационный разряд,
e — контрольный разряд;
то любой ei определяется как
ei=α1ia1+ α2ia2+ … + αmiam,
где αji — может быть нулем или единицей.
Базовые комбинации обладают следующими свойствами:
Все базовые комбинации должны быть различны. Нулевая комбинация не записывается, а подразумевается. Все базовые комбинации должны быть линейно независимыми. Количество единиц в каждой базовой комбинации должно быть не менее dmin. Минимальное кодовое расстояние между всеми базовыми комбинациями должно быть не менее заданного dmin.Базовых комбинаций с указанными свойствами оказывается ровно m.
Матрица состоящая из базовых комбинаций называется порождающей или образующей. Эта матрица состоит из двух подматриц:
В качестве базовых комбинаций информационной подматрицы удобно использовать единичную матрицу Em.
Таким образом окончательный вариант порождающей матрицы:
Если в качестве информационной используется единична подматрица, то легко сформулировать из обычных свойств базовых комбинаций свойства относящиеся к контрольной части матрицы, а именно:
Количество единиц в контрольной части базовой комбинации должно быть не менее dmin ‑ 1 Минимальное кодовое расстояние между контрольными комбинациями должно быть не менее dmin – 2Алгоритм образования значений контрольных разрядов кодовой комбинации по информационным разрядам с помощью матрицы Mn,m выглядит в следующем виде:
e1 = e11a1 + e21a2 + … + em1am
e2 = e12a1 + e22a2 + … + em2am
…
ek = e1ka1 + e2ka2 + … + emkam
Однако гораздо удобнее проверочные уравнения для расчета контрольных разрядов составлять с помощью проверочной матрицы, состоящей из k строк и n столбцов.
Получают её следующем способом:
- Вначале строят единичную матрицу Ek К ней слева приписывают подматрицу Dm,k содержащую m столбцов и k строк. Причём каждая её строка соответствует столбцу контрольных разрядов подматрицы Ck,m порождающей подматрицы. Т. е. Dm,k является транспонированной подматрицей по отношению к Ck,m
Таким образом в общем виде проверочная матрица выглядит:
С помощью этой матрицы операция кодирования осуществляется очень просто:
Позиции, занимаемые единицами в i строке подматрицы Dm,k определяют те информационные разряды, которые должны участвовать в формировании i контрольного разряда.
На основании матричного представления кодов можно сделать следующие выводы:
С помощью порождающей матрицы Mn,m можно представить весь набор кодовых разрешённых комбинаций в удобной и компактной форме. А так же довольно просто закодировать любую информационную часть числа. Проверочную матрицу Hn,k обычно используют при построении кодирующих и декодирующих устройств, т. к. она легко определяет алгоритм нахождения контрольных разрядов по информационным значениям. Кроме того, данная матрица очень удобна для нахождения номера ошибочных разрядов.Метод исправления ошибок с помощью синдрома основан на применении контрольных соотношений полученных по проверочной матрице при кодировании.
Ошибочные разряды определяются по рассчитанному синдрому.
Синдром это сумма по mod2 принятых контрольных разрядов и вычисленных по принятым информационным.
Характерная особенность синдрома заключается в том, что он не зависит от вида информационной части, а зависит только от характера и вида ошибок.
Для определения искаженного разряда необходимо сравнить полученный синдром со столбцами проверочной матрицы и те столбцы, которые совпадают — в этих разрядах произошли ошибки.
Синдром зависит только от характера ошибок и не зависит от вида передаваемой информации.
Количество разрядов синдрома для коррекции t ошибок определяется из следующего выражения:
Принцип работы программы
Программа написана на языке PHP и выполняется на веб-сервере с поддержкой PHP. Программа состоит из 2 html страниц.
На первой странице программа просит ввести кодируемое двоичное слово и регистр, в котором будет совершена ошибка.
На второй странице показан процесс кодирования и декодирования введённого слова. Сначала программа производит процесс вычисления переменных для построения порождающей и проверочной матрицы.
После этого программа строит порождающую и проверочную матрицы.
Затем по этим матрицам программа показывает процесс вычисления контрольных разрядов и выводит закодированное слово. Зелёным цветом отмечен разряд, в котором будет совершена ошибка, серым отмечены контрольные разряды.
В закодированном слове программа совершает ошибку и показывает процесс декодирования и поиска ошибки. В случае, если введенный номер регистра ошибок больше чем количество разрядов в слове, то ошибка совершается в разряде с максимальном номером. Красным цветом отмечен регистр с ошибкой.
В заключении программа выводит сводную таблицу с преобразованиями слова.
Код программы
index. html
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www. w3.org/TR/xhtml1/DTD/xhtml1-strict. dtd">
<html lang="ru">
<head>
<title>Курсовая работа по курсу "Теория Кодирования"</title>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
</head>
<body>
<h1>
Лабораторная работа по курсу "Теория Кодирования"
</h1>
<h2>
Порождающая и проверочная матрицы. Кодирование и декодирование.
</h2>
<center>
Введите исходные данные:
<form action="./code. php">
<table>
<tr>
<td>
Слово для кодирования:
</td>
<td>
<input type=text name=word>
</td>
</tr>
<tr>
<td>
Регистр с ошибкой:
</td>
<td>
<input type=text name=error>
</td>
</tr>
<tr>
<td colspan=2>
<center>
<input type=submit value="Отправить">
</center>
</td>
</tr>
</table>
</form>
</center>
<p>
<a href="http://validator. w3.org/check? uri=referer">
<img src="http://www. w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Transitional" height="31" width="88" border="0">
</a>
</p>
</body>
</html>
code. php
<?
// Функция поиска факториала
function Factorial($a)
{
if ($a==1) return 1; else return Factorial($a-1)*$a;
}
// Функция нахождения биноминального коэффициента
function BC($n,$m)
{
return Factorial($n)/(Factorial($m)*Factorial($n-$m));
}
// Функция XOR с числовым выводом
function myxor($a,$b)
{
if ($a==null) return $b;
else
{
if (($a=="0")and($b=="0")) return "0";
elseif (($a=="1")and($b=="1")) return "0";
else return "1";
}
}
$word=$_GET['word'];
$error=$_GET['error'];
$m=strlen($word);
$t=1;
$dmin=2*$t+1;
$flag=0;
$k=1;
$wc=0;
//Определяем количество единиц для построения кодирования по порождающей матрице
for ($i=0;$i<$m;$i++) { if ($word[$i]=="1") $wc++; }
// Поиск количества контрольных разрядов с помощью границы Хэмминга
while ($flag!= 1)
{
$i=1;
$summ=0;
do
{
$summ = $summ + BC($m+$k,$i);
$i++;
$z++;
}while ($i<floor($dmin-1)/2);
$Hamming = log(1+$summ)/log(2);
$Hamming = ceil($Hamming);
if ($k >= $Hamming) $flag=1; else $k++;
}
$n=$m+$k;
if ($error>$n) { $error=$n; }
//Порождающая матрица
//Единичная матрица
for ($i=1;$i<=$m;$i++)
{
for ($j=1;$j<=$n;$j++)
{
$Matrix[$i][$j]=0;
}
}
for ($i=1;$i<=$n;$i++) $Matrix[$i][$i]=1;
//Контрольные разряды
$flag=0;$i=1;$counter=1;
while($flag!= 1)
{
$temp=decbin($i);
$count=0;
for($j=0;$j<strlen($temp);$j++)
{
if ($temp[$j]==1) $count++;
}
if ($count>=$dmin-1)
{
for($j=strlen($temp);$j>0;$j--)
{
$Matrix[$counter][$n-$j+1]=$temp[strlen($temp)-$j];
}
$counter++;
}
if ($counter>$m) $flag=1;
$i++;
}
// Проверочная матрица
//Контрольные разряды
for ($i=1;$i<=$k;$i++)
{
for ($j=1;$j<=$n;$j++)
{
$HMatrix[$i][$j]=$Matrix[$j][$m+$i];
}
}
//Единичная матрица
for ($i=1;$i<=$k;$i++)
{
for ($j=1;$j<=$k;$j++)
{
$HMatrix[$i][$j+$m]=0;
if ($i==$j) $HMatrix[$i][$j+$m]=1;
}
}
?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www. w3.org/TR/xhtml1/DTD/xhtml1-strict. dtd">
<html lang="ru">
<head>
<title>Лабораторная работа по курсу "Теория Кодирования"</title>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
</head>
<body>
<center>
<h1>
Лабораторная работа по курсу "Теория Кодирования"
</h1>
<h2>
Тема: Порождающая и проверочная матрицы. Кодирование и декодирование.
</h2>
</center>
<h3 align="right">Выполнил студент группы С-65<br>Филимонцев Сергей</h3>
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
