|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 26 May 2003 08:03:55
To : Alex Malkov
Subject : Re: Порождающий многочлен в БЧХ
--------------------------------------------------------------------------------
Sun May 25 2003 03:17, Alex Malkov wrote to Sergey Kabikov:
SK>> Предлагаю поступить проще : огласи исходную постановку задачи,
AM> [Sorry, skipped]
SK>> А если тебе не дело сделать, а экзамен сдать - это совсем другая
SK>> песня.
AM> Hу, не экзамен... лабораторную на зачет :)
А к лабам список литературы прилагается. А если нет - это честный повод для
легкого скандала на кафедре. Чем я во студенчестве иногда и спасался ;-)
AM> Hужно написать прогу, которая кодирует файл, размером не менее 64кб, и,
AM> используя чередование, добиться, чтобы имелась возможность восстановить
AM> любой искаженный блок, размером до 4кб. Код любой из: Рида-Мюллера,
AM> Хэмминга, БЧХ или просто проверки на четность.
Hу вот, стало понятнее. ИМХО, нужен тебе не Хемминг, а старый добрый
Рид-Соломон. Да еще с перемежением. Примерно так.
Hо если хочется Хэмминга - ради бога. Весь твой файл разбиваем на блоки по 4
КБ. Скажем, в твоем случае их будет не более 26, т.е. весь файл должен быть до
92 КБ размером. Эдак ты уложишься в ТЗ по размеру файла. Проверочные биты
займут 5 аналогичных блоков по 4 КБ каждый.
Используем код Хэмминга (31, 26, 3), причем следующим образом :
- для первого кодового слова берем младший бит первого байта каждого блока
(всего до 26 бит), вычисляем проверочные биты (5 штук) и записываем их в
младшие биты первого байта проверочных блоков.
- для второго кодового слова берем второй бит первого байта каждого блока
(всего до 26 бит), и проделываем с ними то же самое.
И так далее. После 4096*8 = 32768 циклов все проверочные биты будут созданы.
Медленно, но верно ;-) Теперь "любой искаженный блок, размером до 4кб"
приведет к появлению не более чем одного искаженного бита в каждом отдельно
взятом кодовом слове.
И, дабы не быть голословным, вот тебе простой кодек Хэмминга
// ------------------------------------------------------------------------
// File: hamming.c
// Encoding and decoding of a Hamming code.
// ------------------------------------------------------------------------
// This program is complementary material for the book:
// R.H. Morelos-Zaragoza, The Art of Error Correcting Coding, Wiley, 2002.
// This and other programs are available at http://the-art-of-ecc.com
// ------------------------------------------------------------------------
#include <math.h>
#include <stdio.h>
#include <float.h>
#include <limits.h>
#include <stdlib.h>
#define MAX_RANDOM LONG_MAX // Maximum value of random()
int i,j,l,index;
int n, k;
int code[1024];
int red[1024], info[1024];
int m;
int parity[10];
int syn;
int error;
int test, result;
main(int argc, char *argv[])
{
if (argc != 3)
{
printf("Usage: %s m position_error\n", argv[0]);
exit(0);
}
sscanf(argv[1],"%d", &m);
sscanf(argv[2],"%d", &error);
n = pow(2,m)-1;
k = n - m;
// Compute parity positions
parity[1] = 1;
for (i=2; i<=m; i++)
parity[i] = (parity[i-1]<<1) & 0xfffffffe;
printf("parity positions: ");
for (i=1; i<=m; i++) printf("%2d ", parity[i]); printf("\n");
// Generate random message
for (i=1; i<=k; i++)
info[i] = ( random() >> 10) & 0x01;
printf("information bits = ");
for (j=1; j<=k; j++) printf("%1d", info[j]);
printf("\n");
// Compute parity bits
for (j=1; j<=m; j++)
{
red[j] = 0;
l = 0;
for (i=1; i<=n; i++)
{
// Check that "i" is not a parity position = not a power of 2
result = 0;
test = 1;
for (index=1; index<=m; index++)
{
if (i==test) result = 1;
test *= 2;
}
if (!result)
{
l++;
if ( (i>>(j-1)) & 0x01 )
red[j] ^= info[l];
}
}
}
printf("parity bits = ");
for (j=1; j<=m; j++) printf("%1d", red[j]);
printf("\n");
// Transmit codeword
i = 1;
l = 1;
for (j=1; j<=n; j++)
if (j==parity[l] && l<=m)
{
code[j] = red[l]; l++;
}
else
{
code[j] = info[i]; i++;
}
printf("codeword = ");
for (j=1; j<=n; j++) printf("%1d", code[j]);
printf("\n");
// Add a hard error
code[error] ^= 1;
printf("received = ");
for (j=1; j<=n; j++) printf("%1d", code[j]);
printf("\n");
// Compute syndrome
syn = 0;
for (i=1; i<=n; i++)
if (code[i]) syn ^= i;
printf("syndrome = %d\n", syn);
// Correct error if needed
if (syn)
code[syn] ^= 1;
printf("estimate = ");
for (j=1; j<=n; j++) printf("%1d", code[j]);
printf("\n");
}
С уважением
Сергей
...Hу, маньяк. С кем не бывает... (с) Р.Асприн
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
