Comments 41
А зачем 7? 6 достаточно…
К примеру нужно передать:
1011
последние два символа пусть отвечают на вопрос, равны ли между собой 1-й и 2-й, и 3-й и 4-й.
То есть если 1 и 0 то это 0, если 11, то это 1
получается
1011+01
Какой бы бит небыл испорчен, у нас достаточно информации, чтоб всё восстановить.
7-й можно использовать для проверки последних двух так же на равенство.
получится
1011010
Теперь при изменении любого бита (то есть не только если он потерян, но и изменён) можно востановить первые 4.
К примеру, если мы поменяли 6-й бит
1011000
то по 3-му, 4-му и 7-му вы востанавливаем 6-й.
К примеру нужно передать:
1011
последние два символа пусть отвечают на вопрос, равны ли между собой 1-й и 2-й, и 3-й и 4-й.
То есть если 1 и 0 то это 0, если 11, то это 1
получается
1011+01
Какой бы бит небыл испорчен, у нас достаточно информации, чтоб всё восстановить.
7-й можно использовать для проверки последних двух так же на равенство.
получится
1011010
Теперь при изменении любого бита (то есть не только если он потерян, но и изменён) можно востановить первые 4.
К примеру, если мы поменяли 6-й бит
1011000
то по 3-му, 4-му и 7-му вы востанавливаем 6-й.
+2
6 недостаточно, т.к. биты корректировки тоже могут быть испорчены т.е. если:
1 2 3 4 — данные
5=1|2; 6=3|4
в результате изменения 6-го бита данные уже восстановить нереально.
Вот подумал немного и оказывается даже 7-и наверно недостаточно…
1 2 3 4 — данные
5=1|2; 6=3|4
в результате изменения 6-го бита данные уже восстановить нереально.
Вот подумал немного и оказывается даже 7-и наверно недостаточно…
0
а как понять, какой из 2х первых испорчен, если у меня 0011010?
+4
садиска кэт может пожать до 3трёх и передать два раза ;)
-9
А похоже, что так:
1011 | 001, где 001 — это CRC: 0 — сравнение 1 и 2 бита, 0 — сравнение 2 и 3 бита, 1 — сравнение 3 и 4 бита.
Изменим первый бит:
0011 | 101 — CRC изменилось. Восстанавливаем: ага, 1 бит CRC неверен. С учетом того, что 2 бит остался прежним, то меняем первый, а не второй бит информации: 1011.
И так далее.
1011 | 001, где 001 — это CRC: 0 — сравнение 1 и 2 бита, 0 — сравнение 2 и 3 бита, 1 — сравнение 3 и 4 бита.
Изменим первый бит:
0011 | 101 — CRC изменилось. Восстанавливаем: ага, 1 бит CRC неверен. С учетом того, что 2 бит остался прежним, то меняем первый, а не второй бит информации: 1011.
И так далее.
0
Проблемку следующую выявил:
например кодируем мы как выше предложил leoneed 5-й и 6-й биты как 1=2 3=4 соответственно
7-й как 5=6
меняется например 1-й бит, сказать что изменился 1 или 2 мы можем а вот какой именно неизвестно => расшифровка невозможна.
если 7-й бит использовать как 3=4 то данные мы восстановить можем, но при ошибке в 3-х последних(контрольных) битах мы можем испортить и данные…
например кодируем мы как выше предложил leoneed 5-й и 6-й биты как 1=2 3=4 соответственно
7-й как 5=6
меняется например 1-й бит, сказать что изменился 1 или 2 мы можем а вот какой именно неизвестно => расшифровка невозможна.
если 7-й бит использовать как 3=4 то данные мы восстановить можем, но при ошибке в 3-х последних(контрольных) битах мы можем испортить и данные…
+1
А если
1011 | 001
изменили на
1011 | 000
то если восстанавливать, то получится
1011 | 001 или 1010 | 000
Думаю, что вариант
1011|01|0 более устойчивый. (последний бит сравнивает 5-й и 6-й, 5 и 6 сравнивает 1 и 2, 3 и 4 соответственно)
1011 | 001
изменили на
1011 | 000
то если восстанавливать, то получится
1011 | 001 или 1010 | 000
Думаю, что вариант
1011|01|0 более устойчивый. (последний бит сравнивает 5-й и 6-й, 5 и 6 сравнивает 1 и 2, 3 и 4 соответственно)
0
Да, да. Если брать в расчет, что CRC тоже может измениться (в задаче это не было указано явно, ибо задание гласит: «требуется передать 4 бита информации», а потом: «Любой бит информации (но только один) может быть испорчен»), тогда надо еще CRC на CRC :)
0
Сообщение адресовалось alfsoft
0
Задачка простая, сейчас брут форс напишу и ответ скажу, идея брута в следующем: считаем размерность пространства сообщений следующем образом. Берем пространство векторов из 7 битов и факторизуем его — два элемента считаются равными, если существуют две помехи, после применения которых два вектора равны побитово.
-2
Так вот, линейный блоковый код, который гарантированно выявит ошибку в одном бите, теория вкратце:
y*G=v, y — битовый вектор, который необходимо закодировать, G — порождающая матрица особого вида: G = [I|R], v — полученный вектор с проверочной частью в конце. Чтобы проверить правильность пришедшей информации (которая, в этом случае, состоит из 7 бит), необходимо вычислить вектор «синдрома» s = v*H, где H — проверочная матрица вида H = [RT, 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».
y*G=v, y — битовый вектор, который необходимо закодировать, G — порождающая матрица особого вида: G = [I|R], v — полученный вектор с проверочной частью в конце. Чтобы проверить правильность пришедшей информации (которая, в этом случае, состоит из 7 бит), необходимо вычислить вектор «синдрома» s = v*H, где H — проверочная матрица вида H = [RT, 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».
+7
UFO just landed and posted this here
UFO just landed and posted this here
Выше я уже описал алгоритм (конструктивное доказательство) того, что передать 4 бита информации возможно. Подробнее, если мощность множества сообщений с ошибкой меньше чем 16, то передать 4 бита невозможно. По ссылке я предоставил код программы, которая считает мощность множества сообщений с ошибкой. Результат — возможно.
0
Банальный RIAD 2.
-4
Пусть радистка разбивает сообщение по битам и множит каждый бит на 7
Это даст четырехкратную потерю скорости, зато враг ничего не сделает
Это даст четырехкратную потерю скорости, зато враг ничего не сделает
+3
банальный код хэмминга
+2
Код Хемминга.
0
У меня такая мысль… А если сделать так: первые 4 из 7 — настоящая информация.
5 — контрольная сумма первых 2 бит
6 — контрольная сумма вторых 2 бит
7 — контрольная сумма всех 5 бит информации.
мне кажется информации достаточно для расшифровки.
5 — контрольная сумма первых 2 бит
6 — контрольная сумма вторых 2 бит
7 — контрольная сумма всех 5 бит информации.
мне кажется информации достаточно для расшифровки.
0
Хмм… код Хемминга позволяет исправить ошибку в любом бите, независимо от того, ошибка была в данных или в контрольном бите. После преобразований контрольное число однозначно идентифицирует номер бита в сообщении, где была ошибка (имеется ввиду полное сообщение, вместе с контрольными битами). Для 6 бит необходимо 3 дополнительных контрольных, так что 3 контроьлных бита для 4х однозначно достаточно :)
+3
код хэмминга
0
только что делал лабораторную работу по этому коду :)
0
эх… 1ый курс
0
решение
Х — биты с информацией. Y — контрольные биты.
Расположение X1 X2 X3 X4 Y1 Y2 Y3
Y1 = X1 *X2 *X4
Y2 = X2*X3*X4
Y3 = X1*X2*X3
Используется логическое умножение.
Х — биты с информацией. Y — контрольные биты.
Расположение X1 X2 X3 X4 Y1 Y2 Y3
Y1 = X1 *X2 *X4
Y2 = X2*X3*X4
Y3 = X1*X2*X3
Используется логическое умножение.
0
В общем мое решение: использование битовой операции xor (исключающее или), которая и ассоциативна, и коммутативна, и вообще полна всяческих доблестей :) Итак:
x1 ^ x2 = y1
x3 ^ x4 = y2
y1 ^ y2 = z
Так мы получаем последовательность x1,x2,x3,x4,y1,y2,z
А расшифровываецца она так:
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 } }
0
Sign up to leave a comment.
Задачка с башорга