caxapa.ru :: Олимпийская задачка. Дано: Двоичной число (0/1) разрядностью N, закодировать/раскодировать так, чтобы подряд шло не более К нулей. Например N=8 K=2 число 10000010, результат 10010010

IBAH (08.07.2021 19:24, просмотров: 5524)

Олимпийская задачка. Дано: Двоичной число (0/1) разрядностью N, закодировать/раскодировать так, чтобы подряд шло не более К нулей. Например N=8 K=2 число 10000010, результат 10010010

Ответить

- решение от дедов - 3лoйтpoLь(09.07.2021 15:46, , картинка)
- Всем спасибо, мой выбор - битстаффинг. Сначала он мне не понравился, тк. полностью рушится структура кадра, а потом сообразил, вставлять-удалять биты можно налету! А чтобы снизить вероятность этого самого битстафинга (снизить избыточность), кадр происключительноилить с 0х55 - IBAH(09.07.2021 15:22)
- "Манчестер" не катит? - Visitor(09.07.2021 10:12)
  - Не понятно что автор хочет получить. Можно ли закодировать один бит двумя состояниями линии? Нужна ли самосинхронизация? - Boвa(09.07.2021 12:06 - 12:09)
    - Автор питает устройство от единиц. Может пережить два нуля подряд, три - возможна излишняя просадка питания. Ну, и раз нет отдельного провода питания, значит, и самосинхронизация нужна. - Nikolay_Po(09.07.2021 12:09)
      - Подходит FM, MFM, манчестер и т.д. - Boвa(09.07.2021 12:10)
- См. "dc balanced codes". Эти коды широко применяются в компьютерных интерфейсах. Очень популярен 8B/10В, поскольку хорошо ложится на байты. Есть и с более длинными блоками, например 64В/66В. Само собой, чем больше блок, тем меньше избыточность. OldHobo(106 знак., 08.07.2021 23:09, , ссылка)
  - А чем 8B/10B отличается от 4В/5В? Мне казалось что при 8 бита избыточность должна быть поменьше - IBAH(08.07.2021 23:33)
    - Пожалуй, я поторопился с советом. Если отсутствие постоянки не нужно (а обычно в связи как раз это и нужно), то 8B/10B ничем не лучше. OldHobo(142 знак., 09.07.2021 00:10, )
    - тем, что легко выделить несколько 10-ти битных кодов, которым не соответствует никакая 8-и битная пара, и этими кодами кодировать особые случаи -на линии start/stop/idle/sync/preamble - Mahagam(09.07.2021 00:07)
- "К" критично? Если для радио, то последовательность данных "отбеливают" - просто XOR-ят с 0xAA или 0x55... - Гyдвин(08.07.2021 22:19)
  - ога, только в исходной последовательности совершенно "случайно" пролетит само 0xAA или 0x55 и кранты. - Mahagam(08.07.2021 23:17)
  - У меня не радио, но я так пока и сделал, и это как-то не спортивно... смотрю с сторону чего-нибудь ЛЧМ подобного (типа 10110010) или ПСП - IBAH(08.07.2021 22:49)
    - А потом в последовательности встретится код 10110010 или вся ваша ПСП (с практической точки зрения достаточно её части) и привет. - Boвa(09.07.2021 12:09)
      - Битстаффинг. Этот код становицца служебным и оформляецца соответствуюсчим образом. - mse homjak(09.07.2021 12:32)
        
        Да. В пределе вставлять в посылку каждый второй единичный бит. - Boвa(09.07.2021 13:19)
- Скремблирование - Evgeny_CD(08.07.2021 22:10, ссылка)
  - Тоже вариант. Но можно наскремблировать так, что одни нули останутся... - IBAH(08.07.2021 22:46)
- bit stuffing штоле? - SciFi(08.07.2021 21:41, ссылка)
  - Спасибо, теперь я знаю еще больше умных слов... Мне бы идеально подошел код 4В/5В, но чего-то как-то... IBAH(350 знак., 08.07.2021 22:29)
    - а пачки единичек подряд (по 8 штук) не беспокоят? и кстати, в выбранном вами наборе условие "больше двух нулей не собираться" нарушается. - Mahagam(08.07.2021 23:16)
      - у меня 1 питание, два нуля это для примера, меня бы и 3 устроило - IBAH(08.07.2021 23:30)
        
        Манчестер жи! Есть ещё Миллер. А лучше расскажите, что ваяете. Обычно получается, что всё немного по-другому. - SciFi(09.07.2021 08:42)
        
        у аффтара паразитное питание с линии данных, или паразитная линия данных на питании. так что тут чисто энергетически лучше всего 8b/10b кодирование, но не стандартное, а своё Mahagam(1055 знак., 09.07.2021 11:14)
        
        Аффтар молчит, аки рыба об лёд :-) А фантазировать пачимута неинтересно. Старею, наверное :-( - SciFi(09.07.2021 11:20)
  - Больше на дерево Хаффмана похоже. - CADiLO(08.07.2021 21:42)
    - "Дерево Хаффмана " имеется в виду алгоритм сжатия? - IBAH(08.07.2021 22:44, ссылка)
- А если число которое нужно закодировать 10010010 то на выходе 10010010 ? - Tpoeшник(08.07.2021 21:36)
  - Ага. это по науке называется "Коды, устраняющие длительные последовательности нулей и единиц" - IBAH(08.07.2021 22:47)
    - Я к науке отношусь с уважением но без пресмыкания. Если на выходе у алгоритма 10010010 А на входе или 10000010 или 10010010 то я не понимаю в чем смысл. - Tpoeшник(09.07.2021 00:05)

Средства и методы разработки