Разработка, производство и продажа радиоэлектронной аппаратуры
|
Карта сайта
|
Пишите нам
|
В избранное
Требуется программист в Зеленограде
- обработка данных с датчиков; ColdFire; 40 тыс.
e-mail:
jobsmp@pochta.ru
Телесистемы
|
Электроника
|
Конференция «Микроконтроллеры и их применение»
Подскажите код для поиска и исправления ошибок. Требования: Исправляет 1 бит, обнаруживает 2 искаженных. На входе - 4 байта, на выходе не более 12 байт. Минимальные затраты процессорного времени на формирование и проверку.
Отправлено
vmp
29 января 2009 г. 21:54
Составить ответ
|
Вернуться на конференцию.
Ответы
Всем спасибо за обсуждение. По здравому рассуждению пришел к такому решению: Сопровождать каждый байт данных еще одним байтом с кодом Хемминга.
-
vmp
(30.01.2009 11:54:32
10.0.1.100,87.245.155.198
, 239 байт)
а почему 5? 4 достаточно
-
ы
(30.01.2009 12:30:19
80.92.98.211
,
пустое
)
Ну 4 так 4. Лишь бы не больше 8.
-
vmp
(30.01.2009 12:38:58
10.0.1.100,87.245.155.198
,
пустое
)
4 недостаточно для детектирования двойных ошибок.
-
Oldring
(30.01.2009 13:01:20
91.77.242.105
,
пустое
)
Почему-то всегда приводятся примеры кодов (12,8). Код (13,8) практически не встречается. Я буду не слишком нахальным, если попрошу пример кода или его реализации?
-
vmp
(30.01.2009 13:18:39
10.0.1.100,87.245.155.198
,
пустое
)
Ответ:
-
ы
(30.01.2009 17:50:34
80.92.98.211
, 27675 байт)
правда тут фича, если одинарная то она уже учтена в таблице, а если 2-я то байт выдается как есть, т.е. признака 2-х ошибок нет как такогого
-
ы
(30.01.2009 17:52:42
80.92.98.211
,
пустое
)
Спасибо. Правда я уже откопал подходящую аппликуху AN427 от Моторолы и даже запустил ее.
-
vmp
(30.01.2009 17:56:2
10.0.1.100,87.245.155.198
,
пустое
)
Примера Хэмминга у меня нет. Но
-
Oldring
(30.01.2009 13:24:59
91.77.242.105
, 419 байт)
У samsung для NAND flash в даташитах есть(был) простенький алгоритм, наверное можно применить.
-
китаец
(30.01.2009 02:08:54
77.127.148.213
,
пустое
)
4 в 12? Дык это 300% вобщем хэмминг 12,8 (на 1 байт 4 бита) условия исправления як заданы.
-
ы
(30.01.2009 01:13:49
217.118.66.37
,
пустое
)
Во, и я тоже с этого начал. C такими условиями самый лучший способ исправле...{+}
-
VasilyS
(30.01.2009 08:01:8
80.92.96.25
, 202 байт)
куда ж ты его переспросишь, если это память?
-
koyodza
(30.01.2009 11:20:27
77.123.64.94
,
пустое
)
читал: Блейхут "Коды исправляющие ошибки"?
-
=L.A.=
(29.01.2009 23:42:23
94.29.98.79
,
пустое
)
Хотелось бы обойтись без привлечения тяжелой артиллерии. Думал, что для небольшого размера входных данных найдутся более быстрые решения.
-
vmp
(29.01.2009 23:53:31
77.232.15.245
, 406 байт)
Так я просто книгу предлагаю :)) Прочитаешь - станет понятен калибр твоей задачи вот и подберешь нужный боеприпас.
-
=L.A.=
(29.01.2009 23:56:40
94.29.98.79
,
пустое
)
Хемминг весьма прост и быстр, и под озвученные условия должен вполне подойти. Не надо лезть в БЧХ-коды типа Рида-Соломона и т.п.
-
koyodza
(29.01.2009 23:55:55
77.123.64.94
,
пустое
)
ИМХО, куда надо залезть гораздо виднее человеку, решающему задачу.
-
=L.A.=
(30.01.2009 00:00:11
94.29.98.79
,
пустое
)
а CRC только обнаруживает ошибки, но не исправляет.
-
=L.A.=
(29.01.2009 23:47:49
94.29.98.79
,
пустое
)
+1. Здесь вообще смешались в кучу кони-люди.
-
VasilyS
(29.01.2009 23:55:23
80.92.96.25
,
пустое
,
ссылка
)
Ответ:
-
koyodza
(30.01.2009 00:13:55
77.123.64.94
,
пустое
,
ссылка
)
Любой блочный код можно использовать для исправления ошибок в количестве, меньшем половины кодового расстояния ;)
-
Oldring
(30.01.2009 00:06:10
91.77.241.41
,
пустое
)
Гвозди забивать тоже можно разными предметами. Лампочкой напремер. Но никто...{+}
-
VasilyS
(30.01.2009 00:37:33
80.92.96.25
, 275 байт)
:D
-
Oldring
(30.01.2009 12:17:43
91.77.242.105
,
пустое
)
если читан - то не понят, если понят - то не так ;)
-
Oldring
(29.01.2009 23:48:57
91.77.241.41
,
пустое
)
Чет не понял. 4-->12 это же просто троекратный повтор 4-х байт? Тоесть мажор и всё?
-
VasilyS
(29.01.2009 22:50:18
80.92.96.25
,
пустое
)
Формально - да. Озвученным условиям задачи отвечает. (+)
-
Quasy
(30.01.2009 10:26:53
192.168.0.207,80.243.9.34
, 220 байт)
А если рассмотреть случай, когда попали две ошибки в одну и ту же позицию? Т.е. первая и вторая копия имеют одинаковую ошибку?
-
vmp
(30.01.2009 12:30:11
10.0.1.100,87.245.155.198
,
пустое
)
Дык паритет не совпадет.
-
Quasy
(30.01.2009 12:42:30
192.168.0.207,80.243.9.34
,
пустое
)
Где хранится паритет?
-
Oldring
(30.01.2009 13:07:24
91.77.242.105
,
пустое
)
Почему именно хранится? Он может формироваться при приеме.
-
Quasy
(30.01.2009 13:12:15
192.168.0.207,80.243.9.34
, 123 байт)
Как?
-
Oldring
(30.01.2009 13:26:53
91.77.242.105
,
пустое
)
Да как обычно, ксором. Или таблицей, я не настаиваю. Или вообще (+)
-
Quasy
(30.01.2009 13:33:3
192.168.0.207,80.243.9.34
, 83 байт)
Блин. Ксором чего? И как на основании этого ксора делать какие-то выводы?
-
Oldring
(30.01.2009 13:37:20
91.77.242.105
, 206 байт)
Вы невнимательны. Я же сказал: речь о унарной ошибке за 12 байт, а Вы?
-
Quasy
(30.01.2009 13:42:20
192.168.0.207,80.243.9.34
,
пустое
)
А я об исходной задаче. Детектирование при этом двух.
-
Oldring
(30.01.2009 13:43:22
91.77.242.105
,
пустое
)
Вот. Вот и добрались до паритета (+)
-
Quasy
(30.01.2009 13:58:45
192.168.0.207,80.243.9.34
, 238 байт)
А если была послана последовательность 01 01 01 01 01 01 02 02 02 03 03 03 и принято то, что в примере - не покажет?
-
Oldring
(30.01.2009 14:03:19
91.77.242.105
,
пустое
)
Всё покажет и вдобавок исправит. (+)
-
Quasy
(30.01.2009 14:30:16
192.168.0.207,80.243.9.34
, 469 байт)
Каким образом принято 00(1 ???);
-
Oldring
(30.01.2009 14:39:4
91.77.242.105
, 195 байт)
Паритет запрещен автором задачи? Не вижу. Он просил алгоритм (+)
-
Quasy
(30.01.2009 14:51:13
192.168.0.207,80.243.9.34
, 449 байт)
Не запрещен, если все вместе со всеми паритетами влезет в 96 бит, то есть пресловутые 12 байт, которые есть всего.
-
Oldring
(30.01.2009 15:14:8
91.77.242.105
,
пустое
)
Бу-га-га! Ты про старт и стоп-биты еще скажи! Куды ж их девать-то? :-))))
-
VasilyS
(31.01.2009 11:26:18
80.92.96.25
,
пустое
)
Если ты не в курсе - они тоже есть далеко не везде.
-
Oldring
(31.01.2009 15:39:26
91.77.243.136
,
пустое
)
Да уж, в ИРПР или КОП их не видел :-)
-
VasilyS
(31.01.2009 22:05:27
80.92.96.25
,
пустое
)
Память
-
vmp
(30.01.2009 13:12:46
10.0.1.100,87.245.155.198
,
пустое
)
Нет.
-
Oldring
(29.01.2009 22:51:42
91.77.241.41
,
пустое
)
Жаль. А может быть это?
-
VasilyS
(29.01.2009 22:58:26
80.92.96.25
,
пустое
,
ссылка
)
Пункт "что читать" подойдет.
-
Oldring
(29.01.2009 23:04:3
91.77.241.41
,
пустое
)
Серьезно? Штуки три из списка у меня стоят на книжной полке. Трубуются нечасто :-)
-
VasilyS
(29.01.2009 23:10:39
80.92.96.25
,
пустое
)
Может тогда прочесть хоть одну? ;)
-
Oldring
(29.01.2009 23:12:49
91.77.241.41
,
пустое
)
Тебе вслух или как?
-
VasilyS
(29.01.2009 23:14:5
80.92.96.25
,
пустое
)
Начни про себя. Осознавая написанное.
-
Oldring
(29.01.2009 23:15:23
91.77.241.41
,
пустое
)
Про меня там нет. Про тебя тоже не видел.
-
VasilyS
(29.01.2009 23:17:46
80.92.96.25
,
пустое
)
Не сомневаюсь. Но читать про себя тем не менее у некоторых получается.
-
Oldring
(29.01.2009 23:20:0
91.77.241.41
,
пустое
)
Пустое. Ни Хэмминг ни Соломон не в силах исправить горбатого.
-
VasilyS
(29.01.2009 23:27:32
80.92.96.25
,
пустое
)
Разумеется.
-
Oldring
(29.01.2009 23:33:8
91.77.241.41
,
пустое
)
Код Хемминга с битом чётности ("расширенный код Хемминга"), описан во всех учебниках дискр.математики
-
Шунт_гороховый
(29.01.2009 22:30:25
213.85.166.81
,
пустое
)
Хмм... Сейчас почитал даташит на SN74LS630 (она же 555ВЖ1). Похоже, что при программной реализации кода Хемминга (16+6) можно обойтись парой табличек по 256 байт. Для 32+7 получатся 4 таблички.
-
vmp
(30.01.2009 00:25:30
77.232.15.245
, 228 байт)
Это так для любого линейного кода.
-
Oldring
(30.01.2009 13:04:53
91.77.242.105
,
пустое
)
Хемминг достаточно прост, и избыточность значительно меньше. Для 32 бит достаточно 6 бит избыточности, а не 64
-
koyodza
(29.01.2009 23:40:15
77.123.64.94
,
пустое
,
ссылка
)
Не забудьте только про дополнение до четности ;)
-
Oldring
(29.01.2009 23:47:23
91.77.241.41
,
пустое
)
???
-
koyodza
(29.01.2009 23:51:16
77.123.64.94
,
пустое
)
У чистого кода хэмминга кодовое расстояние равно 3. Он не может детектировать двойные ошибки. Нужен код хэмминга, дополненный до четности. Который легко реализовать и как циклический код.
-
Oldring
(29.01.2009 23:59:15
91.77.241.41
, 201 байт)
Ответ:
-
koyodza
(30.01.2009 00:12:24
77.123.64.94
, 602 байт)
Почти это и называется дополнением до четности. Только код получится нециклический.
-
Oldring
(30.01.2009 00:17:36
91.77.241.41
, 241 байт)
=> ;)
-
Oldring
(29.01.2009 22:32:4
91.77.241.41
,
пустое
,
ссылка
)
CRC
-
Oldring
(29.01.2009 22:27:37
91.77.241.41
, 179 байт)
Да, похоже с CRC-8 идея хорошая. Только с полиномом не понял - 0x19B - это уже 9 бит?
-
vmp
(29.01.2009 23:38:31
77.232.15.245
, 578 байт)
хуже, чем "искать ошибку побитовым подбором" идею выдумать сложно
-
koyodza
(29.01.2009 23:50:50
77.123.64.94
,
пустое
)
Какая идея хуже? Считать программно номер ошибки вычисляя ксоры отдельных битиков синдрома.
-
Oldring
(30.01.2009 00:08:38
91.77.241.41
,
пустое
)
Для 32 бит данных? И только в случае ошибки?
-
vmp
(29.01.2009 23:55:18
77.232.15.245
,
пустое
)
Ответ:
-
koyodza
(30.01.2009 00:04:1
77.123.64.94
, 558 байт)
Если потребуется добавить два байта - счетчик будет считать не до 40, а до 56.
-
Oldring
(30.01.2009 00:20:21
91.77.241.41
,
пустое
)
Когда количество небольшое - оно как раз имеет значение.
-
vmp
(30.01.2009 00:13:51
77.232.15.245
, 652 байт)
Остаток от деления на него - 8 бит.
-
Oldring
(29.01.2009 23:41:19
91.77.241.41
,
пустое
)
а "Исправлять 1 бит вычерпыванием" - это как?
-
koyodza
(29.01.2009 23:12:56
77.123.64.94
,
пустое
)
Перебирая возможные позиции ошибки, в общем. Некорректно выразился.
-
Oldring
(29.01.2009 23:19:10
91.77.241.41
, 220 байт)
да уж...
-
koyodza
(29.01.2009 23:27:18
77.123.64.94
, 57 байт)
что-то не так?
-
Oldring
(29.01.2009 23:29:53
91.77.241.41
,
пустое
)
нет, всё ок, за исключением идеи пересчитывать CRC столько раз, сколько бит в блоке, в случае более чем одной ошибки
-
koyodza
(29.01.2009 23:53:23
77.123.64.94
,
пустое
)
и невозможности восстановить одиночную ошибку в самой CRC
-
koyodza
(30.01.2009 00:04:53
77.123.64.94
,
пустое
)
Возможно. Как - догадайтесь ;)
-
Oldring
(30.01.2009 00:10:44
91.77.241.41
,
пустое
)
нет и никогда не было такой идеи ;)
-
Oldring
(30.01.2009 00:04:38
91.77.241.41
, 386 байт)
Матрица. Чётность по строкам + чётность по столбцам. (н-р, в радиометке H4001, стр.4)
-
Юрий_СВ
(29.01.2009 22:18:7
217.12.195.250
,
пустое
,
ссылка
)
Тоже вариант. Жаль, сейчас в процессорах не делают команд определения четности.
-
vmp
(29.01.2009 23:44:37
77.232.15.245
,
пустое
)
Отправка ответа
Имя*:
Пароль:
E-mail:
Тема*:
Сообщение:
Ссылка на URL:
URL изображения:
если вы незарегистрированный на форуме пользователь, то
для успешного добавления сообщения заполните поле, как указано ниже:
введите число 123:
Перейти к списку ответов
|
Конференция
|
Раздел "Электроника"
|
Главная страница
|
Карта сайта
Web
telesys.ru