Задача На Биты

[TSY]

В рассматриваемом в задаче сообщение представляет собой поток байтов. При этом каждые четыре бита сообщения дополняются четырьмя проверочными битами, вычисленными по следующему правилу (символом ⊕ обозначена сумма по модулю 2, операция xor):
x4 = x0 ⊕ x1 ⊕ x2
x5 = x1 ⊕ x2 ⊕ x3
x6 = x0 ⊕ x2 ⊕ x3
x7 = x4 ⊕ x5 ⊕ x6

Таким образом, каждый байт сообщения кодируется двумя байтами, при этом первый по порядку байт содержит младшие четыре бита исходного байта сообщения и проверочные биты, а второй — старшие четыре бита исходного байта и проверочные биты, например:
Исходное сообщение длиной в один байт: 0xAE (двоичный код - 10101110), младшая половина 0xE (1110), старшая половина 0xA (1010).
Кодируем младшую половину:
x4 = 0 ⊕ 1 ⊕ 1 = 0
x5 = 1 ⊕ 1 ⊕ 1 = 1
x6 = 0 ⊕ 1 ⊕ 1 = 0
x7 = 0 ⊕ 1 ⊕ 0 = 1
Кодируем старшую половину:
x4 = 0 ⊕ 1 ⊕ 0 = 1
x5 = 1 ⊕ 0 ⊕ 1 = 0
x6 = 0 ⊕ 0 ⊕ 1 = 1
x7 = 1 ⊕ 0 ⊕ 1 = 0
Итоговые два байта: 0xAE (10101110) 0x5A (01011010)

необходимо написать программу для декодирования сообщения, сконструированного по заданным выше правилам

Программа получает закодированное сообщение на стандартный ввод, результат печатается на стандартный вывод.

Гарантируется (не требуется проверка), что при передаче сообщения исключены ошибки типа "потеря бита" и "включение бита". Другими словами длина биты сообщения гарантированно находятся на своих местах, а проверочные на своих. Длина сообщения в байтах гарантированно кратна двум. Также гарантируется, что каждый байт сообщения содержит не более одной битовой ошибки.

Необходимые битовые операции (установка заданного номером бита, например) должны быть оформлены в виде отдельных функций.

Написать программу для раскодирования сообщения, не обращая внимание на корректирующие коды (предполагая, что ошибок не было). Таким образом, достаточно собрать один байт из каждой пары, склеив младшие тетрады.

Подскажите хотя бы идейку,а то как-то совсем туго...

 

[lazybiz]

Дай пример закодированного сообщения.

Добавлено:
Сначала я был уверен что решить эту задачу не составляет труда....
Но теперь меня захлестнула волна недопониманий, а именно:
В алгоритме показано, что для кодирования используются 7 битов исходного байта:
x4 = x0 ⊕ x1 ⊕ x2
x5 = x1 ⊕ x2 ⊕ x3
x6 = x0 ⊕ x2 ⊕ x3
x7 = x4 ⊕ x5 ⊕ x6
но почему тогда для каждой тетрады разные шаблоны кодирования:
для младшей:
x4 = 0 ⊕ 1 ⊕ 1 = 0
x5 = 1 ⊕ 1 ⊕ 1 = 1
x6 = 0 ⊕ 1 ⊕ 1 = 0
x7 = 0 ⊕ 1 ⊕ 0 = 1
для старшей:
x4 = 0 ⊕ 1 ⊕ 0 = 1
x5 = 1 ⊕ 0 ⊕ 1 = 0
x6 = 0 ⊕ 0 ⊕ 1 = 1
x7 = 1 ⊕ 0 ⊕ 1 = 0
Я имею в виду биты, помеченные красным цветом. Ведь следуя логике алгоритма они берутся из исходного байта, и, следовательно, должны быть одинаковыми!
Я что-то не так понял или в задании что-то упущено?

 

[TSY]

Пример есть в самой задачи:

Исходное сообщение длиной в один байт: 0xAE (двоичный код - 10101110), младшая половина 0xE (1110), старшая половина 0xA (1010).
Кодируем младшую половину:
x4 = 0 ⊕ 1 ⊕ 1 = 0
x5 = 1 ⊕ 1 ⊕ 1 = 1
x6 = 0 ⊕ 1 ⊕ 1 = 0
x7 = 0 ⊕ 1 ⊕ 0 = 1
Кодируем старшую половину:
x4 = 0 ⊕ 1 ⊕ 0 = 1
x5 = 1 ⊕ 0 ⊕ 1 = 0
x6 = 0 ⊕ 0 ⊕ 1 = 1
x7 = 1 ⊕ 0 ⊕ 1 = 0
Итоговые два байта: 0xAE (10101110) 0x5A (01011010)
т.е. закодированное сообщение - это 1010111001011010 переведенное,как я понял условие задачи, в десятичную с.с.

 

[TSY]

хм. Да,я тоже не пойму,почему для кодирования старшей половины использован другой алгоритм...
Но такая задача существует и её нужно решить

 

[lazybiz]

Невозможно решить задачу без верно поставленного условия.
Либо объясни почему так, либо увы...

 

[TSY]

Я могу предположить,что
Кодируем старшую половину:
x4 = 0 ⊕ 1 ⊕ 0 = 1
x5 = 1 ⊕ 0 ⊕ 1 = 0
x6 = 0 ⊕ 0 ⊕ 1 = 1
x7 = 1 ⊕ 0 ⊕ 1 = 0

взялось с :т.к. старшая половина это 0xA (1010), то для неё x0 = 0, x1 = 1, x2 = 0, x3 = 1,эти значения подставляются для того,чтобы найти x4, x5 и x6, а x7 уже находится исходя из того,что получилось в x4,x5,x6

 

[lazybiz]

Ок. Ход мыслей понял. Я тоже об этом думал, но хотелось чтобы ты сам это подтвердил. Мне нужно время чтобы подумать...

 

[TSY]

Я думаю,что это все-таки взялось отсюда...

У меня главный вопрос заключается в том,что я не могу понять смысл предложения : "Программа получает закодированное сообщение на стандартный ввод"т.е. это может быть и набор букв?(раз "сообщение представляет собой поток байтов")И как это все вводить ,с помощью scanf,getchar или нужно как-то иначе?(использую язык Си)

 

[lazybiz]

Да, можно через scanf, gets или getchar.
Я так понимаю что помощь в реализации алгоритма тебе больше не нужна?

 

[TSY]

Нужна
Просто я не понимаю, как, если я ввожу число,букву и любой другой символ,найти его двоичный код,с помощью какой команды ,и как это реализовать?И еще,если я ввожу закодированное сообщение с помощью scanf, то разве символ не дудет иметь размер два байта?

 

[lazybiz]

Функция декодирования:

void decode( unsigned char *d, unsigned char *s, int n )
{
for (; n--; s += 2 ) {
*d++ = (s[0] & 0x0f) | ((s[1] & 0x0f) << 4);
}
}

Как применять сообразишь сам

 

[lazybiz]

По поводу ввода символов. Я не знаю что имел в виду тот человек который дал тебе задание. Но если они должный вводиться в 16-ном виде, тогда придется обрабатывать вводимую строку.

 

[TSY]

Спасибо,покапаюсь,что-нибдь придумаю

 

[lazybiz]

Что не получается то?