Московский государственный институт электроники и математики
Кафедра ИКТ
курсовая работа по дисциплине «Теория
информации и кодирования»
Код Хемминга
Выполнил:
Руководитель:
Москва 2009
Оглавление
Оглавление........................................................................................................................................ 2
Задание............................................................................................................................................... 3
Теоретические сведения.................................................................................................................. 3
Алгоритм программы..................................................................................................................... 4
Код программы................................................................................................................................ 5
Задание
Составить и отладить программу для кодирования и декодирования двоичных чисел кодом Хемминга с коррекцией.
Теоретические сведения
Коды Хемминга являются наиболее эффективными для коррекции одиночных ошибок (dmin=3) и для обнаружения двойной и коррекции одиночной (dmin=4).
В кодах Хемминга по определенным правилам производится разбиение на подмножества, и в соответствие контрольному разряду записывается дополнение до четности. При декодировании проверяется четность по подмножествам и, на основании полученной информации определяется номер искаженных разрядов.
В кодах Хемминга с dmin=4 выделяется еще один дополнительный контрольный разряд, куда записывается дополнение до четности всего кодового слова в целом. При декодировании проверяется четность как по основным подмножествам, так и всего слова в целом.
Для построения Кодов Хемминга достаточно приписать к каждому слову один добавочный (контрольный) двоичный разряд и выбрать цифру такого разряда так, чтобы общее количество единиц в изображении любого числа было, например, четным. Одиночная ошибка в каком-либо разряде передаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количества единиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичных цифр числа, могут давать сигнал о наличии ошибок.
Можно построить и такой код, который обнаруживал бы двойные ошибки и исправлял одиночные. Для этого к коду, рассчитанному на исправление одиночных ошибок, нужно приписать еще один контрольный разряд (разряд двойного контроля). Полное количество разрядов кода при этом будет m+k+1. Цифра в разряде двойного контроля устанавливается такой, чтобы общее количество единиц во всех m + k + 1 разрядах кода было четным. Этот разряд не включается в общую нумерацию и не входит ни в одну контрольную группу.
При этом могут быть следующие случаи:
1. В принятом коде в целом и по всем контрольным группам количество единиц четно. Если тройные ошибки и ошибки в большем количестве разрядов исключаются, то первый случай соответствует безошибочному приему кода.
2. В принятом коде в целом количество единиц нечетно, но во всех контрольных группах количество единиц четно. Второй случай - ошибки только в разряде двойного контроля.
3. В принятом коде в целом и в некоторых из контрольных групп количество единиц нечетно. Третий случай — одиночной ошибки в каком-либо из остальных разрядов
4. В принятом коде в целом количество единиц четно, но в некоторых контрольных группах имеется нечетное количество единиц - двойная ошибка. Исправление двойных ошибок невозможно.
Алгоритм программы
Программа кодировщик работает следующим образом :
Вводится входное слово, после чего в массив со словом добавляются пустые ячейки для контрольных разрядов. После этого входное слово разбивается на подмножества в которых считается сумма по модулю два, а результат записывается в соответствующую подмножеству ячейку массива. После чего берется сумма по модулю два от закодированного слова и в зависимости от результата в конец слова записывается 0 или 1 как дополнение до четности (в случае с dмин=4).
Программа декодировщик работает следующим образом:
Программа считает контрольные разряды снова, точно так же как это делал кодировщик, после чего она сравнивает посчитанные контрольные разряды с теми контрольными разрядами, которые были введены с закодированным словом, если контрольный разряд отличается, то в регистр ошибок записывается 1 на соответствующее место.
Если выражение в регистре ошибок равняется 0000 и совпала проверка четности слова, то ошибок нет.
Если выражение в регистре ошибок равно 0000 и не совпала проверка четности, то это значит, что в закодированном слове имеется одиночная ошибка в месте, где указывает выражение регистра ошибок.
Если выражение в регистре ошибок не равно 0000 ,а проверка четности совпал, то это значит что в закодированном слове двоичная ошибка, обнаружить которую невозможно.
Код программы
Кодирование
<?php
$a = array();
$str = $_POST['qq'];
for ($i=strlen($str)-1; $i>-1; $i--)
$a[]=$str[$i];
$aa = array();
$j = 0;
$i = 0;
$ii = 0;
while (1)
{
if (pow(2, $j) == ($i+1)) {$aa[]=5; $j++; } else {$aa[]=$a[$ii]; $ii++;}
if ($ii == count($a)) break;
$i++;
}
$aaa = $aa;
$kk = array();
$ppc = array();
for ($i=0; $i<$j; $i++)
{
$sum = 0;
$fg = 1;
$flag = false;
for ($k=0; $k<count($aa); $k++)
{
if ($fg == pow(2, $i)) {$flag = !$flag; $fg = 0;}
$fg++;
if ($flag && $aa[$k] != 5) {$ppc[$i][$k] = 5; $sum = $sum + $aa[$k];} else $ppc[$i][$k] = 'v';
if ($flag && $aa[$k] == 5) {$kk[$i]=$k;}
}
$aa[$kk[$i]] = $sum & 1;
}
echo '<table border="0"><tr><td bgcolor="#CCCCFF">Номера разрядов</td>';
for ($i=count($ppc[1]); $i>0; $i--)
echo "<td bgcolor='#CCCCFF'>".$i."</td>";
echo "</tr><tr><td bgcolor='#CCCCFF'>Число А</td>";
for ($t=count($aaa)-1; $t>-1; $t--)
if ($aaa[$t] == 5)
echo "<td bgcolor='#EEEEEE'> </td>";
else
echo "<td bgcolor='#CCCCCC'>".$aaa[$t]."</td>";
for ($i=0; $i<count($ppc); $i++)
{
echo '<tr><td bgcolor="#CCCCFF">Подмножество '.($i+1).'</td>';
for ($j=count($ppc[1])-1; $j>-1; $j--)
//for ($j=0; $j<count($ppc[1]); $j++)
{
echo "<td width='10'";
if ($ppc[$i][$j] == 5) echo 'bgcolor="#CCCCCC">'.$aa[$j].'</td>';
else if ($kk[$i] == $j) echo 'bgcolor="#FFCCCC">'.$aa[$j].'</td>';
else echo "bgcolor='#EEEEEE'> </td>";
}
echo '</tr>';
}
echo "<tr><td bgcolor='#CCCCFF'>Число А в коде Хэмминга c Dmin=3</td>";
$j = count($kk)-1;
for ($i=count($aa)-1; $i>-1; $i--) {
//for($i=0; $i<count($aa); $i++) {
echo "<td ";
if ($kk[$j] == $i) {echo 'bgcolor="#FFCCCC"'; $j--;} else echo 'bgcolor="#CCCCCC"';
echo ">".$aa[$i]."</td>";
}
$sum2=0;
for ($i=0; $i<count($aa); $i++)
$sum2=$sum2+$aa[$i];
$sum2=$sum2 & 1;
echo "<tr><td bgcolor='#CCCCFF'>Число А в коде Хэмминга c Dmin=4</td>";
$j = count($kk)-1;
for ($i=count($aa)-1; $i>-1; $i--) {
//for($i=0; $i<count($aa); $i++) {
echo "<td ";
if ($kk[$j] == $i) {echo 'bgcolor="#FFCCCC"'; $j--;} else echo 'bgcolor="#CCCCCC"';
echo ">".$aa[$i]."</td>";
}
echo "<td bgcolor='#CCFFCC'>".$sum2."</td>";
echo '</td></table><br>Число А в коде Хэмминга c Dmin=4 - ';
for ($i=count($aa)-1; $i>-1; $i--)
echo $aa[$i];
echo $sum2;
?>
Декодирование
<?php
$a = array();
$str = $_POST['q'];
function rep(array $q)
{
$sum=0;
for ($i=0; $i<count($q); $i++)
{
if ($q[$i]==1) $sum=$sum + pow(2, ($i));
}
return $sum;
}
for ($q=strlen($str)-2; $q>-1; $q--)
$aa[]=$str[$q];
$j = 0;
while(1)
{
if (pow(2, ($j)) > count($aa)) {break;} else $j++;
}
$aaa = $aa;
$error = array();
$kk = array();
$ppc = array();
for ($i=0; $i<$j; $i++)
{
$sum = 0;
$fg = 1;
$flag = false;
for ($k=0; $k<count($aa); $k++)
{
if ($fg == pow(2, $i)) {$flag = !$flag; $fg = 0;}
$fg++;
if ($flag && $aa[$k] != 5) {$ppc[$i][$k] = 5; $sum = $sum + $aa[$k];} else $ppc[$i][$k] = 'v';
if ($flag && $aa[$k] == 5) {$kk[$i]=$k;}
}
if ($aa[$kk[$i]] != ($sum & 1)) $error[]=1; else $error[]=0;
}
$sum=$str[strlen($str)-1];
for ($i=0; $i<count($aa); $i++)
{
$sum=$sum+$aa[$i];
}
$lolq = 0;
if (($sum & 1) == 0 && rep($error) == 0) echo "Ошибок не произошло";
if (($sum & 1) == 1 && rep($error) == 0) {echo "Ошибка произощла в 0 разряде (бит четности всего слова)"; $lolq = 1;}
if (($sum & 1) == 0 && rep($error) != 0) echo "Произошла двоичная ошибка<br>Определить место положение ошибок не удалось =(";
if (($sum & 1) == 1 && rep($error) != 0) echo "Произошла одиночная ошибка в ".rep($error)." разряде";
$omg = count($aa)-rep($error);
//$aa[rep($error)-1] = !$aa[rep($error)];
echo '<table>
<tr>
<td bgcolor="#CCCCFF">Номер разряда</td>';
for ($i=(count($aa)); $i>-1; $i--)
{echo "<td bgcolor='#CCCCFF'>".$i."</td>"; if ($omg == $i) $omg2 = $i;}
echo '</tr><tr>';
echo '<td bgcolor="#CCCCFF">Введенное слово</td>';
for ($i=(count($aa)-1); $i>-1; $i--)
{if ((count($aa)-1-$omg2) == $i) echo "<td bgcolor='#FFCCCC'>".$aa[$i]."</td>"; else echo "<td bgcolor='#CCFFCC'>".$aa[$i]."</td>";}
if ($lolq == 1)echo "<td bgcolor='#FFCCCC'>".$str[strlen($str)-1]."</td></tr></table>"; else
echo "<td bgcolor='#CCFFCC'>".$str[strlen($str)-1]."</td></tr></table>";
echo "Сигнатура указывающая на ошибку - ";
for ($d=(count($error)-1); $d>-1; $d--)
echo $error[$d];
;
?>
