Comments 20
Было бы полезно, на мой взгляд, указать информацию о том какие типы ошибки может исправить и какие детектировать? Тот же код Хэмминга однократные фиксит, а двукратные обнаруживает
Про Чейза говорить о гарантированном числе исправляемых ошибок нельзя. Все зависит от веса ошибок. Вес ошибок зависит от уровня шума в канале передачи данных. Об этом постараюсь рассказать в ближайшем топике. Если чуть забегать вперёд и говорить терминами, не описанным в данной статье, то при уровне отношения сигнал/шум 9, без проблем можно получить всего один ошибочный бит на 10 000 000 переданных, т.е. вероятность ошибки 10^-7. Надеюсь не очень мудрёно ответил)
А меня вот наоборот статья о кодах Хэмминга, приведенная вами, в свое время сбила с правильного направления. Разбирались как раз недавно с блоками памяти, собранных на микросхемах 556РТ7. Так вот там используются еще и микросхемы 553ВЖ1, именно для проверки и корректирования 24-разрядной шины данных. В них используется модифицированный код Хэмминга.
На 24 разряда идут 6 разрядов Хэмминга и высчитываются по своему алгоритму, я так понял специально адаптированному под схемотехнику.
На 24 разряда идут 6 разрядов Хэмминга и высчитываются по своему алгоритму, я так понял специально адаптированному под схемотехнику.
Ну приведённая статья скорей наглядна. Показывает на пальцах сам принцип исправление ошибок. Вообще классическое описание Хэмминга немного отличается.
По поводу шин — скорей всего алгоритм был адаптирован, конечно. При m = 5 (число проверочных символов), длинна кодового слова для Хэмминга была бы n = 2^m — 1 = 31 из которых k = 2^m — m — 1 = 26 были бы информационными, а 5 проверочными. Уменьшение кол-ва информационных символов и увеличения проверочных скорей всего было нужно для просчёта каких то специфических для схемы значений, типа чётности в данной статье. но точно сказать трудно.
По поводу шин — скорей всего алгоритм был адаптирован, конечно. При m = 5 (число проверочных символов), длинна кодового слова для Хэмминга была бы n = 2^m — 1 = 31 из которых k = 2^m — m — 1 = 26 были бы информационными, а 5 проверочными. Уменьшение кол-ва информационных символов и увеличения проверочных скорей всего было нужно для просчёта каких то специфических для схемы значений, типа чётности в данной статье. но точно сказать трудно.
Да, интересно. Пишите про Витерби. Уже была статья, но хотелось бы еще.
… Что-то сложно… Про алгоритм Чейза ни разу не слышал… Это что, табличное декодирование по минимуму расстояния? И всё-таки, «жёсткий» или «мягкий» декодер? И почему помехи искажают вектор из нулей и единиц в дробные числа?.. Что-то я вообще в ауте, хотя преподаю кодирование…
Придётся что-нибудь написать :).
Придётся что-нибудь написать :).
С табличным декодированием признаться сам не сталкивался. Но относительно алгоритма Чейза такого термина ни разу не встречал, так что думаю что это не оно.
Декодер мягкий, потому что принимает на вход мягкие данные, внутри используется жесткий декодер, но это необходимо только для работы алгоритма, на вход жесткого ничего подавать не нужно.
Я писал, что искажение заслуживает отдельной статьи. Но вопрос справедливый.
В комменте ответить сложно. Постараюсь на пальцах. Надеюсь никто не обидится и не заклеймит меня. Это просто для понимания
Когда мы передаём бит в канал, он превращается в сигал (это всем ясно). Грубо говоря 0, это отсутствие сигнала, а один наличие сигнала, определённой амплитуды. Но вот появляется шум. Он добавляет/отнимает какую свою амплитуду от сигналу. Жесткий демудулятор тупо сравнит с 0.5 и значение принятое из канала. Если < 0.5 то 0, иначе 1. Но на сколько было отклонение не понятно. 0.49 и 0.51 очень близки, но в «жесткую» превратятся в 0 и 1 соответственно. Мягкий декодер изучит наименее «надёжные» биты, которые ближе к половине амплитуда — в данном случае 0.5 (в топике был 0) и рассмотрит какое решение ему ближе с 1 на данной позиции или 0 и возьмёт лучшее.
Надеюсь не запутал ещё больше. Тут для хорошего примера пару графиков нужно. Вообщем статья и мини-приложение с примером за мной.
Декодер мягкий, потому что принимает на вход мягкие данные, внутри используется жесткий декодер, но это необходимо только для работы алгоритма, на вход жесткого ничего подавать не нужно.
Я писал, что искажение заслуживает отдельной статьи. Но вопрос справедливый.
В комменте ответить сложно. Постараюсь на пальцах. Надеюсь никто не обидится и не заклеймит меня. Это просто для понимания
Когда мы передаём бит в канал, он превращается в сигал (это всем ясно). Грубо говоря 0, это отсутствие сигнала, а один наличие сигнала, определённой амплитуды. Но вот появляется шум. Он добавляет/отнимает какую свою амплитуду от сигналу. Жесткий демудулятор тупо сравнит с 0.5 и значение принятое из канала. Если < 0.5 то 0, иначе 1. Но на сколько было отклонение не понятно. 0.49 и 0.51 очень близки, но в «жесткую» превратятся в 0 и 1 соответственно. Мягкий декодер изучит наименее «надёжные» биты, которые ближе к половине амплитуда — в данном случае 0.5 (в топике был 0) и рассмотрит какое решение ему ближе с 1 на данной позиции или 0 и возьмёт лучшее.
Надеюсь не запутал ещё больше. Тут для хорошего примера пару графиков нужно. Вообщем статья и мини-приложение с примером за мной.
Прошу заранее прощения за возможно глупый вопрос, но не задать не могу, очень хочется знать ;)
Какого размера в байтах должны быть данными чтобы испорченный один бит можно было восстановить?
Какого размера в байтах должны быть данными чтобы испорченный один бит можно было восстановить?
Количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенство: 2^k >= k + m + 1,
где m — количество основных двоичных разрядов кодового слова.
где m — количество основных двоичных разрядов кодового слова.
Один испорченный бит гарантировано исправляется даже алгоритмом Хэмминга. Так что при ситуации, когда сильно искажается один из бит вы получите 100% исправление ошибки, при любой длине кода.
Если говорить об общем случае, то Чейз эффективен к относительное коротким блокам. В моделирование при длине кодового слова = 31 (m = 5), при p = v = 3 и отношение сигнал/шум = 7. получал ошибку 10^-6, т.е. 1 на 1 000 000 бит. Если память не изменяет. при m = 7 результаты были даже получше. Дальше m = 10 не совался, потому что уже начинает ресурсов не хватать. нужно компьютер обновлять)
Если говорить об общем случае, то Чейз эффективен к относительное коротким блокам. В моделирование при длине кодового слова = 31 (m = 5), при p = v = 3 и отношение сигнал/шум = 7. получал ошибку 10^-6, т.е. 1 на 1 000 000 бит. Если память не изменяет. при m = 7 результаты были даже получше. Дальше m = 10 не совался, потому что уже начинает ресурсов не хватать. нужно компьютер обновлять)
Хочу применить восстановление битов в своем протекторе исполняемых файлов. Другими словами я хочу сознательно портить код, так чтобы его читать было невозможно, а в последствии восстанавливать. Основной страх, т.к. еще не проверял, это боюсь что можно будет испортить только 1 бит на очень большой кусок кода. Мне же надо хотя бы на 10-20% куска кода. Вообщем мне хочется управлять степенью восстановления
хочется управлять степенью восстановления
то есть Вы имели ввиду «управлять степенью порчи»? Так тогда можно сознательно портить один символ на слово, два символа на слово, три и тому подобное. Код выбирать таким, чтобы он 100% восстанавливал однократную, двукратную, трёхкратную ошибки и так далее согласно степени порчи. Под символом можете понимать байт, два байта… в общем, всё, что покажется удобным. Позиция ошибки в слове будет случайной, но код её всё равно исправит, так как ему важна лишь кратность ошибки.
Да, Вы точнее сформулировал чем я. Действительно имел ввиду «степень порчи». Просто пока мне известны код Хэмминга, слышал о Рид-Соломона, но глубоких познаний нет. Только начал копать эту тему. Пока мое понимание, возможно не правильное, что ошибка может быть только один бит на на 1000 у более байтов. Мне хочется не слишком много доп. информации добавить, но при этом достаточно хорошо попортить данные )
Например, у двоичного кода Хэмминга, исправляющего все однократные ошибки, количество проверочных битов r и длина выходного кодового слова n связаны как n = 2^r — 1, так как количество ненулевых r-разрядных двоичных комбинаций как раз-таки и равно этому числу. То есть возможен ряд (n,k)-кодов (3,1), (7, 4), (15,11)… где k — количество информационных битов.
Для порчи следует применять несистематические коды, когда кодовое слово не делится на два блока, типа «ИИИИППП», где И — информационные символы, П — проверочные (контрольные). Иначе можно легко заметить закономерность.
Если требуется вводить две, три и более ошибок на слово, то можно посмотреть в сторону кодов Боуза-Чоудхури-Хоквингема.
А, вообще, странно защищать информацию избыточными кодами…
Для порчи следует применять несистематические коды, когда кодовое слово не делится на два блока, типа «ИИИИППП», где И — информационные символы, П — проверочные (контрольные). Иначе можно легко заметить закономерность.
Если требуется вводить две, три и более ошибок на слово, то можно посмотреть в сторону кодов Боуза-Чоудхури-Хоквингема.
А, вообще, странно защищать информацию избыточными кодами…
Ну странно вообще применять теорию обфускации после компиляторов ;))) Одни инженеры пишут как бы написать оптимизатор в компиляторе так чтобы было хорошо по скорости и памяти. А другие инженеры пишут так чтобы добавить больше кода для усложнения reverse-engineering, тем самым сводят на нет усилия оптимизатора в компиляторе.
Я просто ищу новые пути защиты, которые можно применить в моем протекторе ;)
Я просто ищу новые пути защиты, которые можно применить в моем протекторе ;)
У меня руководитель писал подобное приложение. Для демонстрации возможностей, перед продажей. Я его тыкал, но само кодирование не трогал. По мелочи кое что изменял.
Файл в качестве примера был аудио. Это очень наглядно, потому что можно воспроизвести несколько раз и сравнить — в начале, после внесения помех и после восстановления.
Там кстати использовался код Рида-Соломона. Код очень шустрый и эффективный, но не простой в реализации.
Могу дать совет — с такими вещами надо быть осторожными. Потому что если запишется ошибка в хедер файла, то вообще ничего может не воспроизвестись, не смотря на хорошие результаты работы алгоритма. Так что мы просто хедер мы передавали отдельно. Быстрое и сердитое решение)))))) но это был пример работы а не прод… так что посмотрите и уточните, есть ли в вашем файле критичные секции.
Файл в качестве примера был аудио. Это очень наглядно, потому что можно воспроизвести несколько раз и сравнить — в начале, после внесения помех и после восстановления.
Там кстати использовался код Рида-Соломона. Код очень шустрый и эффективный, но не простой в реализации.
Могу дать совет — с такими вещами надо быть осторожными. Потому что если запишется ошибка в хедер файла, то вообще ничего может не воспроизвестись, не смотря на хорошие результаты работы алгоритма. Так что мы просто хедер мы передавали отдельно. Быстрое и сердитое решение)))))) но это был пример работы а не прод… так что посмотрите и уточните, есть ли в вашем файле критичные секции.
Ладно с табличным декодированием, видимо терминология разная. Это самый примитивный способ декодирования, но и самый трудоёмкий (перебираем всю кодовую таблицу и считаем расстояния между принятым словом и всеми разрешёнными словами, затем выбираем то кодовое слово, которое ближе всего к принятому).
По-поводу «жёсткости». Демодулятор работает в мягком режиме и поэтому на вход декодера уже поступают не двузначные символы (биты), а многозначные (3, 4, 5… как правило, более восьми нет смысла делать). Ладно. Декодер всё-таки должен работать в жёстком режиме (на выходе имеется ввиду), так как потребителю, в конечном счёте, нужны биты. Из-за этого у меня путаница и возникла. По сути, демодулятор по принятому импульсу вычисляет число (уровень напряжения) и смотрит в какой интервал оно попало. Чем дальше от центра, тем более достоверным будет результат (в случае передачи битов). Насколько я помню, если область выходных значений демодулятора делится на три интервала (минимальная степень мягкости), то на вход декодера приходят биты 0 и 1 и так называемый стёртый символ (его можно обозначить как X). Линейные блочные коды (тем более и циклические) могут восстанавливать стёртые символы, причём на это требуется столько же ресурсов, сколько и на обнаружение. В этом-то и есть «фишка» мягкого режима, причём есть ещё плюс: с точки зрения теории информации декодеру будет поступать больше информации, чем при жёсткой демодуляции. С этих позиций чем отличается алгоритм Чейзера? Количеством интервалов (то есть там будут стёртые символы X1, X2, Xm)?
По-поводу «жёсткости». Демодулятор работает в мягком режиме и поэтому на вход декодера уже поступают не двузначные символы (биты), а многозначные (3, 4, 5… как правило, более восьми нет смысла делать). Ладно. Декодер всё-таки должен работать в жёстком режиме (на выходе имеется ввиду), так как потребителю, в конечном счёте, нужны биты. Из-за этого у меня путаница и возникла. По сути, демодулятор по принятому импульсу вычисляет число (уровень напряжения) и смотрит в какой интервал оно попало. Чем дальше от центра, тем более достоверным будет результат (в случае передачи битов). Насколько я помню, если область выходных значений демодулятора делится на три интервала (минимальная степень мягкости), то на вход декодера приходят биты 0 и 1 и так называемый стёртый символ (его можно обозначить как X). Линейные блочные коды (тем более и циклические) могут восстанавливать стёртые символы, причём на это требуется столько же ресурсов, сколько и на обнаружение. В этом-то и есть «фишка» мягкого режима, причём есть ещё плюс: с точки зрения теории информации декодеру будет поступать больше информации, чем при жёсткой демодуляции. С этих позиций чем отличается алгоритм Чейзера? Количеством интервалов (то есть там будут стёртые символы X1, X2, Xm)?
По поводу терминологии «мягкости». Чаще всего речь идёт именно о входных значениях. Когда говорят «Hard decision decoder» или «Soft decision decoder» имеются в виду входные значения. А вот когда речь идёт о выходных значениях, используют другой термин: soft output или hard output. Тот же SOVA — Soft Output Viterbi Algorithm. Хотя, обычно в таких случаях упоминаются и входные данные — Soft Input Soft Output.
Sign up to leave a comment.
Алгоритм Чейза