Задачка с башорга

[@leoneed]

А зачем 7? 6 достаточно…
К примеру нужно передать:
1011
последние два символа пусть отвечают на вопрос, равны ли между собой 1-й и 2-й, и 3-й и 4-й.
То есть если 1 и 0 то это 0, если 11, то это 1
получается
1011+01
Какой бы бит небыл испорчен, у нас достаточно информации, чтоб всё восстановить.
7-й можно использовать для проверки последних двух так же на равенство.
получится
1011010
Теперь при изменении любого бита (то есть не только если он потерян, но и изменён) можно востановить первые 4.
К примеру, если мы поменяли 6-й бит
1011000
то по 3-му, 4-му и 7-му вы востанавливаем 6-й.

[@foff4ik]

6 недостаточно, т.к. биты корректировки тоже могут быть испорчены т.е. если:

1 2 3 4 — данные
5=1|2; 6=3|4

в результате изменения 6-го бита данные уже восстановить нереально.

Вот подумал немного и оказывается даже 7-и наверно недостаточно…

[@ithilion]

Достаточно, если применить знания о помехоустойчивом кодировании.
Чтобы можно было исправить одну ошибку, необходимо выполнение неравенства d0 >= 3,
где d0 в свою очередь можно ограничить сверху: d0 <= 7*2^3/(2^4-1)=3.7.

Для решения этой задачи достаточно использовать линейный блоковый код.

[@CharnaD]

а как понять, какой из 2х первых испорчен, если у меня 0011010?

[@almaz]

садиска кэт может пожать до 3трёх и передать два раза ;)

[@alfsoft]

А похоже, что так:

1011 | 001, где 001 — это CRC: 0 — сравнение 1 и 2 бита, 0 — сравнение 2 и 3 бита, 1 — сравнение 3 и 4 бита.

Изменим первый бит:
0011 | 101 — CRC изменилось. Восстанавливаем: ага, 1 бит CRC неверен. С учетом того, что 2 бит остался прежним, то меняем первый, а не второй бит информации: 1011.

И так далее.

[@CAH4A]

а если в CRC бит побился? )

[@foff4ik]

Проблемку следующую выявил:

например кодируем мы как выше предложил leoneed 5-й и 6-й биты как 1=2 3=4 соответственно
7-й как 5=6

меняется например 1-й бит, сказать что изменился 1 или 2 мы можем а вот какой именно неизвестно => расшифровка невозможна.

если 7-й бит использовать как 3=4 то данные мы восстановить можем, но при ошибке в 3-х последних(контрольных) битах мы можем испортить и данные…

[@leoneed]

А если
1011 | 001
изменили на
1011 | 000
то если восстанавливать, то получится
1011 | 001 или 1010 | 000

Думаю, что вариант
1011|01|0 более устойчивый. (последний бит сравнивает 5-й и 6-й, 5 и 6 сравнивает 1 и 2, 3 и 4 соответственно)

[@alfsoft]

Да, да. Если брать в расчет, что CRC тоже может измениться (в задаче это не было указано явно, ибо задание гласит: «требуется передать 4 бита информации», а потом: «Любой бит информации (но только один) может быть испорчен»), тогда надо еще CRC на CRC :)

[@leoneed]

А если использовать ваш метод, но 7-й, это сравнение 1-го и 4-го???

[@alfsoft]

Ну, я в том методе не учел, что CRC может измениться.

[@leoneed]

Сообщение адресовалось alfsoft

[@alfsoft]

Кстати, подумалось мне: не надежнее ли считать CRC не рядом стоящих битов, а через один? 1 и 3; 2 и 4?

[@shai_xylyd]

Задачка простая, сейчас брут форс напишу и ответ скажу, идея брута в следующем: считаем размерность пространства сообщений следующем образом. Берем пространство векторов из 7 битов и факторизуем его — два элемента считаются равными, если существуют две помехи, после применения которых два вектора равны побитово.

[@peterdemin]

Написали? А то не понятно о чем вы тут.

[@ithilion]

Так вот, линейный блоковый код, который гарантированно выявит ошибку в одном бите, теория вкратце:
y*G=v, y — битовый вектор, который необходимо закодировать, G — порождающая матрица особого вида: G = [I|R], v — полученный вектор с проверочной частью в конце. Чтобы проверить правильность пришедшей информации (которая, в этом случае, состоит из 7 бит), необходимо вычислить вектор «синдрома» s = v*H, где H — проверочная матрица вида H = [R^T, I], I — еденичная матрица. Если вектор синдрома не является нулевым, то информация с ошибкой. Чтобы найти тот бит, в котором ошибка, достаточно сделать следующее: найти битовый вектор вида f=(0, 0, ..., 1, 0, ...), который при умножении на H даст полученный «синдром» s: f*H == s. Например, f= (0, 1, 0, 0, 0, 0, 0) означает, что ошибка в 6 бите (с конца).

Кто желает проверить, вот, например, матрица G:
1 0 0 0 0 1 1
0 1 0 0 1 1 0
0 0 1 0 1 0 1
0 0 0 1 0 0 1
Умножать везде стоит «по модулю 2».

[@theKitich]

4й курс )))

[@loader]

у нас это было на 1 курсе

[@theKitich]

круто. а специальность какая?
у нас Computer Sciense — на Архитектуре компьютеров код Хемминга был )
хотя, может, и на 2м, и на3м — но слушали не так внимательно :)

[@fuCtor]

Курсовая по цифровой схемотехнике на 3ем курсе))

[@abchernin]

1 курс. Предмет назывался стебно: Теория Информационных Технологий и Систем. В народе Сиськи (ТИТиС) :)

[@shai_xylyd]

Выше я уже описал алгоритм (конструктивное доказательство) того, что передать 4 бита информации возможно. Подробнее, если мощность множества сообщений с ошибкой меньше чем 16, то передать 4 бита невозможно. По ссылке я предоставил код программы, которая считает мощность множества сообщений с ошибкой. Результат — возможно.

[@mirrik]

Банальный RIAD 2.

[@mirrik]

То есть RAID 2.

[@odessky]

Пусть радистка разбивает сообщение по битам и множит каждый бит на 7
Это даст четырехкратную потерю скорости, зато враг ничего не сделает

[@koct9i]

банальный код хэмминга

[@aaacmc]

банальный банальный
а мог бы и порадоваться за автора что он открыл для себя что-то новое

ЗЫ и ваще хреналь ты на работе халтеришь роспезд?!

[@Sap_ru]

Код Хемминга.

[@alexiznot]

У меня такая мысль… А если сделать так: первые 4 из 7 — настоящая информация.
5 — контрольная сумма первых 2 бит
6 — контрольная сумма вторых 2 бит
7 — контрольная сумма всех 5 бит информации.

мне кажется информации достаточно для расшифровки.

[@alexiznot]

нет, 7 — контрольная сумма второго и третьего бита. тогда будет ок

[@grokinn]

как одним битом закодировать контрольную сумму 2 бит? 2 бита могут принимать 4 состояния (11 00 10 01) а контрольный бит может принимать 2 состояния (1 0).

[@VlexZ]

Хмм… код Хемминга позволяет исправить ошибку в любом бите, независимо от того, ошибка была в данных или в контрольном бите. После преобразований контрольное число однозначно идентифицирует номер бита в сообщении, где была ошибка (имеется ввиду полное сообщение, вместе с контрольными битами). Для 6 бит необходимо 3 дополнительных контрольных, так что 3 контроьлных бита для 4х однозначно достаточно :)

[@T3xHuK]

кому интересно или кто хочет проверить свои знания в области теории информации и кодирования — вот тест у меня как раз сейчас такое в универе… 3й курс
тут есть и теория и тестирование =)

[@nix]

код хэмминга

[@nix]

только что делал лабораторную работу по этому коду :)

[@ExxY]

эх… 1ый курс

[@UrbanFace]

решение
Х — биты с информацией. Y — контрольные биты.
Расположение X1 X2 X3 X4 Y1 Y2 Y3

Y1 = X1 *X2 *X4

Y2 = X2*X3*X4

Y3 = X1*X2*X3

Используется логическое умножение.

[@LoneCat]

В общем мое решение: использование битовой операции xor (исключающее или), которая и ассоциативна, и коммутативна, и вообще полна всяческих доблестей :) Итак:

x1 ^ x2 = y1
x3 ^ x4 = y2
y1 ^ y2 = z

Так мы получаем последовательность x1,x2,x3,x4,y1,y2,z
А расшифровываецца она так:

if(y1 ^ y2 !== z) {
  // значит испорченный бит среди них, и исходное сообщение (первые четыре бита) можно читать без опаски
  if(x1 ^ x2 !== y1) {
    // значит испорченный бит y1
  } elseif(x3 ^ x4 !== y2) {
    // значит испорченный бит y2
  } else {
    // значит испорченный бит z
  }
} else {
  // значит испорчен один из битов данных
  if(x1 ^ x2 !== y1) {
    // испорчен один из первых двух битов данных
    // используя ассоциативность xor'а, заменяем в проверке поочередно один из битов его альтернативой: x1 = x2 ^ y1
    if((x1 ^ (x1 ^ y1)) ^ y2 !== z) {
      // значит испорчен бит x2, так как в подстановке мы использовали только его
    } elseif(((x2 ^ y1) ^ x2) ^ y2 !== z) {
      // значит испорчен бит x1, так как в подстановке мы использовали только его
    }
  } elseif(x1 ^ x2 !== y2) {
    // испорчен один из второй пары битов данных
    if(y1 ^ (x3 ^ (x3 ^ y2)) !== z) {
      // значит испорчен бит x3, так как в подстановке мы использовали только его
    } elseif(y1 ^ ((x4 ^ y2) ^ x4) !== z) {
      // значит испорчен бит x4, так как в подстановке мы использовали только его
    }
  } else {
    // а здесь, как пишут индусы, чистые деньги! :P
  }
}