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

Тема в разделе "C/C++/C#", создана пользователем TSY, 5 дек 2011.

  1. TSY

    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)

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

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

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

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

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

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Дай пример закодированного сообщения.

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

    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 переведенное,как я понял условие задачи, в десятичную с.с.
     
  4. TSY

    TSY Гость

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Невозможно решить задачу без верно поставленного условия.
    Либо объясни почему так, либо увы...
     
  6. TSY

    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
     
  7. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Ок. Ход мыслей понял. Я тоже об этом думал, но хотелось чтобы ты сам это подтвердил. Мне нужно время чтобы подумать...
     
  8. TSY

    TSY Гость

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

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Да, можно через scanf, gets или getchar.
    Я так понимаю что помощь в реализации алгоритма тебе больше не нужна?
     
  10. TSY

    TSY Гость

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

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Функция декодирования:
    Код (C++):
    void decode( unsigned char *d, unsigned char *s, int n )
    {
    for (; n--; s += 2 ) {
    *d++ = (s[0] & 0x0f) | ((s[1] & 0x0f) << 4);
    }
    }
    Как применять сообразишь сам:rolleyes:
     
  12. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    По поводу ввода символов. Я не знаю что имел в виду тот человек который дал тебе задание. Но если они должный вводиться в 16-ном виде, тогда придется обрабатывать вводимую строку.
     
  13. TSY

    TSY Гость

    Спасибо,покапаюсь,что-нибдь придумаю :rolleyes:
     
  14. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Что не получается то?
     
Загрузка...
Похожие Темы - Задача На Биты
  1. elzim
    Ответов:
    0
    Просмотров:
    928
  2. ShaoKahn
    Ответов:
    0
    Просмотров:
    1.112
  3. eremin-sanek
    Ответов:
    3
    Просмотров:
    1.101
  4. MonteCristo
    Ответов:
    1
    Просмотров:
    850
  5. bort
    Ответов:
    1
    Просмотров:
    1.176

Поделиться этой страницей