persicum
Full Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Знакомлюсь с литературным творчеством BZ касательно кодов, исправляющих ошибки. Доступного неспециалистам материала по этой теме практически нет, поэтому читал с большим интересом, попутно припоминая некоторые вещи. Вообще, наука кодирования файлов, или, точнее, пакетов, является новой и по своим задачам существенно отличается от классической теории защиты информации, которая направлена скорее на низкоуровневую поддержку аппаратной части. Но в сетях, даже если все железо работает без сбоев (то есть на низком уровне коды функционируют), может возникать необходимость введения избыточных пакетов для повышения пропускной способности каналов из-за неравномерной доставки и хаотичного поведения абонентов.
Остановимся на некоторых, как мне кажется, неточностях.
1) Не названа причина высокой скорости и "бешеной популярности" LDPC, фонтанных и им подобных кодов. Мне представляется, что причина состоит в наличии нулей, особенно когда их число велико, в генераторной матрице. И простота базовой XOR-операции, кроме которой ничего не нужно. Удивительной способностью матриц с большим количеством нулей является их свойство восстанавливать ошибки практически ничем не хуже полновесных, честных, всюду обратимых матриц. А вычисляются они, конечно, в сотни и тысячи раз быстрее. Они имеют некоторые несущественные, косметические недостатки, или, скорее, особенности, которые на практике незаметны. Теория "несовершенных" кодов несоизмеримо сложнее теории MDS кодов, но, для начала, при проектировании "несовершенного" кода следует учесть две цифры. Это, во-первых, "критическая масса" блоков, ниже которой коды не работают, и число дополнительных блоков (относительно потерянных), необходимых для декодирования с вероятность отказа хорошего хеша. Если, например, критическая масса равна 100 блоков, а число экстра-блоков равно 3-м, то можно спокойно создавать, например, 2000 блоков восстановления, практическая разница с MDS кодом будет неощутима (а скорость выше). Такой систематический код будет работать, даже если потерять 95% блоков восстановления.
Об этом и нужно было поведать школьникам.
2) Корни из единицы, DFT и FFT есть в любых конечных полях. Тут следовало бы сказать, что сложность N log N у FFT достигается за счет применения тактики "разделяй и властвуй". Под этим подразумевается рекурсивный вызов процедуры для двух половин входных данных, и так далее. Другие общеизвестные примеры этого - умножение Карацубы, быстрая сортировка. Проще всего организовать FFT в полях, которые имеют корни порядка 2^N. Такие корни есть далеко не во всех полях. Примеры полей, где такие корни имеются в достаточном количестве - GF(65537) и GF(FFF00001h)
3) Предложенный BZ метод кодирования как FFT(iFFT), конечно, непрактичен. Во первых, набор корней единицы для FFT процедуры зависит от ее длины. Если добавить нулей - длина изменится и корни вместе с ней. Для FFT-2 это не так страшно - просто в систематическом коде проверочные символы окажутся вперемешку с информационными. Во вторых, нулями придется дополнять дважды. Например, сначала 5 символов до 8-ми для iFFT, потом 8 символов до 16-ти чтоб получить парити (вперемешку с исходными данными). Скорость такого кода будет в 2 раза меньше от возможной. В третьих, из такого кодирования не ясно, как раскодировать. Получается аналог архиватора Лыщенко, который паковал любой файл в один xor-байт, а распаковка обещалась в следующей версии.
Сходство матрицы Вандермонда и матрицы корней единицы сыграла с BZ злую шутку. На самом деле - корни FFT процедуры это ее внутренняя кухня и сами по себе они неважны (более того, меняются в зависимости от длины процедуры!!). А что нужно? Тут всплывает волшебное слово СВЕРТКА. Свертка нужна, а конкретные корни - нет. Заодно понятно и кодирование/декодирование. Если провести свертку с маской (из нулей и единиц), то эта маска и укажет, какие данные сохранились, а какие нужно восстановить. А при кодировании маску можно настроить на получение символов четности. Похожим целям служит и классический полином-локатор, но там это не так очевидно, как с маской. Используя внешнюю свертку, можно создать быстрые коды в любом поле, например, в GF(FFFFFFFBh) или даже в GF(2^32).
4) Предложен код, использующий матрицы Вандермонда k*k и k*n, но не сказано, какое кол-во операций необходимо для обращения матрицы k*k. Вдруг это N^3?
|
Всего записей: 462 | Зарегистр. 27-06-2007 | Отправлено: 22:23 21-12-2018 | Исправлено: persicum, 07:51 22-12-2018 |
|
ТС, обновите плиз)
