Как найти коды вектора - Исправление недочетов и поиск решений вместе с Examum.ru

Вектор (std::vector) и строка (std::string) — это важные базовые контейнеры стандартной библиотеки C++. Они хранят свои элементы в непрерывном фрагменте памяти. Оба этих контейнера предоставляют доступ к элементам по индексу и позволяют эффективно добавлять новые элементы в конец.

Контейнер `std::vector`

В стандартной библиотеке C++ вектором (std::vector) называется динамический массив, обеспечивающий быстрое добавление новых элементов в конец и меняющий свой размер при необходимости. Вектор гарантирует отсутствие утечек памяти (об этом мы поговорим в других главах, сейчас просто считайте, что это хорошо).

Для работы с вектором нужно подключить заголовочный файл vector.

Элементы вектора должны быть одинакового типа, и этот тип должен быть известен при компиляции программы. Он задаётся в угловых скобках после std::vector: например, std::vector<int> — это вектор целых чисел типа int, а std::vector<std::string> — вектор строк.

Само имя std::vector не является типом данных: это шаблон, в который требуется подставить нужные параметры (тип элемента), чтобы получился конкретный тип данных. Подробнее о том, что такое шаблоны и как их применять, мы расскажем в главе 1.9.

Рассмотрим пример программы, которая заполняет вектор элементами и печатает их через пробел:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5};
    for (int elem : data) {
        std::cout << elem << " ";
    }
    std::cout << "n";
}

Здесь мы инициализируем вектор через список инициализации, в котором элементы перечислены через запятую. Другой способ инициализации вектора — указать число элементов и (при необходимости) образец элемента:

#include <string>
#include <vector>

int main() {
    std::vector<std::string> v1;  // пустой вектор строк
    std::vector<std::string> v2(5);  // вектор из пяти пустых строк
    std::vector<std::string> v3(5, "hello");  // вектор из пяти строк "hello"
}

Обращение к элементам

Выше мы использовали для печати элементов вектора цикл range-for. Но иногда удобнее работать с индексами. Вектор хранит элементы в памяти последовательно, поэтому по индексу элемента можно быстро найти его положение в памяти. Индексация начинается с нуля:

std::vector<int> data = {1, 2, 3, 4, 5};
int a = data[0];  // начальный элемент вектора
int b = data[4];  // последний элемент вектора (в нём пять элементов)
data[2] = -3;  // меняем элемент 3 на -3

Чтобы узнать общее количество элементов в векторе, можно воспользоваться функцией size:

std::cout << data.size() << "n";

Отрицательные индексы, как в некоторых других языках программирования, не допускаются.

Обратите внимание: когда мы обращаемся по индексу через квадратные скобки, проверки его корректности не происходит. Это ещё одно проявление принципа «мы не должны платить за то, что не используем».

Встроенные валидаторы замедляют программу: предполагается, что программист пишет правильный код и уверен, что индекс i в выражении data[i] неотрицателен и удовлетворяет условию i < data.size(). В этом случае они ему не нужны.

Если всё же обратиться к вектору по некорректному индексу, то программа во время выполнения попадёт в неопределённое поведение: фактически она попробует прочитать память, не принадлежащую вектору.

Если вам не хочется делать много лишних проверок, а в корректности индекса вы не уверены, то можно использовать функцию at:

std::vector<int> data = {1, 2, 3, 4, 5};
std::cout << data[42] << "n";  // неопределённое поведение: может произойти всё что угодно
std::cout << data.at(0) << "n";  // напечатается 1
std::cout << data.at(42) << "n";  // произойдёт исключение std::out_of_range — его можно будет перехватить и обработать

Про работу с исключениями мы поговорим отдельно в главе 3.5.

Рассмотрим функции вектора front и back, которые возвращают его первый и последний элемент без использования индексов:

std::vector<int> data = {1, 2, 3, 4, 5};
std::cout << data.front() << "n";  // то же, что data[0]
std::cout << data.back() << "n";  // то же, что data[data.size() - 1]

Важно учитывать, что вызов этих функций на пустом векторе приведёт к неопределённому поведению.

Для проверки вектора на пустоту вместо сравнения data.size() == 0 принято использовать функцию empty, которая возвращает логическое значение:

if (!data.empty()) {
   // вектор не пуст, с ним можно работать
}

Итерация по индексам

Так сложилось, что в стандартной библиотеке индексы и размеры контейнеров имеют беззнаковый тип. Вместо unsigned int или unsigned long int для него используется традиционный псевдоним size_t (а точнее, std::vector<T>::size_type). Тип size_t на самом деле совпадает с uint32_t или uint64_t в зависимости от битности платформы. Его использование в программе дополнительно подчёркивает, что мы имеем дело с индексами или с размером.

Итерацию по элементам data с помощью индексов можно записать так:

for (size_t i = 0; i != data.size(); ++i) {
    std::cout << data[i] << " ";
}

Это каноническая форма записи такого цикла: в ней принято использовать сравнение != и префиксный ++i. Для целых чисел не будет разницы, если написать это как-то иначе (например, через < и постфиксный i++), но потом, когда вы будете писать аналогичные циклы для итераторов других контейнеров, разница появится. Давайте привыкнем всегда оформлять цикл по индексам так.

Беззнаковость типа возвращаемого значения функции size порождает следующую проблему. По правилам, унаследованным ещё от языка C, результат арифметических действий над беззнаковым и знаковым типами приводится к беззнаковому типу. Поэтому выражение data.size() - 1, например, тоже будет беззнаковым. Если data.size() окажется нулём, то такое выражение будет вовсе не минус единицей, а самым большим беззнаковым целым (для 64-битной платформы это $2^{64} — 1$).

Рассмотрим следующий ошибочный код, который проверяет, есть ли в векторе дубликаты, идущие подряд:

// итерация по всем элементам, кроме последнего:
for (size_t i = 0; i < data.size() - 1; ++i) {
    if (data[i] == data[i + 1]) {
        std::cout << "Duplicate value: " << data[i] << "n";
    }
}

Эта программа будет некорректно работать на пустом векторе. Условие i < data.size() - 1 на первой итерации окажется истинным, и произойдёт обращение к элементам пустого вектора. Правильнее было бы переписать это условие через i + 1 < data.size() или воспользоваться внешней функцией std::ssize, которая появилась в C++20. Она возвращает знаковый размер вектора:

for (std::int64_t i = 0; i < std::ssize(data) - 1; ++i) {
    if (data[i] == data[i + 1]) {
        std::cout << "Duplicate value: " << data[i] << "n";
    }
}

Добавление и удаление элементов

В вектор можно эффективно добавлять элементы в конец и удалять их с конца. Для этого существуют функции push_back и pop_back. Рассмотрим программу, считывающую числа с клавиатуры в вектор и затем удаляющую все нули в конце:

#include <iostream>
#include <vector>

int main() {
    int x;
    std::vector<int> data;
    while (std::cin >> x) {  // читаем числа, пока не закончится ввод
        data.push_back(x);  // добавляем очередное число в вектор
    }

    while (!data.empty() && data.back() == 0) {
        // Пока вектор не пуст и последний элемент равен нулю
        data.pop_back();  // удаляем этот нулевой элемент
    }
}

Добавление элементов в другие части вектора или их удаление неэффективно, так как требует сдвига соседних элементов. Поэтому отдельных функций, например, для добавления или удаления элементов из начала у вектора нет. Это можно сделать с помощью общих функций insert/erase и итераторов. Мы рассмотрим такие примеры позже.

Удалить все элементы из вектора можно с помощью функции clear.

Резерв памяти

Вектор хранит элементы в памяти в виде непрерывной последовательности, друг за другом. При этом в конце последовательности резервируется дополнительное место для быстрого добавления новых элементов. Когда этот резерв заканчивается, при вставке очередного элемента происходит реаллокация: элементы вектора копируются в новый, более просторный блок памяти.

Реаллокация — довольно дорогая процедура, но если она происходит достаточно редко, то её влияние незначительно. Можно доказать, что если размер нового блока выбирать в два раза больше предыдущего размера, то амортизационная сложность добавления элемента будет константной.

Текущий резерв вектора можно узнать с помощью функции capacity (не путайте её с функцией size).

Рассмотрим программу, в которой в вектор последовательно добавляются элементы и после каждого шага печатается размер и резерв:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> data = {1, 2};
    std::cout << data.size() << "t" << data.capacity() << "n";

    data.push_back(3);
    std::cout << data.size() << "t" << data.capacity() << "n";

    data.push_back(4);
    std::cout << data.size() << "t" << data.capacity() << "n";

    data.push_back(5);
    std::cout << data.size() << "t" << data.capacity() << "n";
}

Вот вывод этой программы:

Видно, что размер вектора увеличивается на единицу, а резерв удваивается после исчерпания. Так, при добавлении четвёрки используется имеющаяся в резерве память, а при добавлении тройки и пятёрки происходит реаллокация.

Иногда требуется заполнить вектор элементами, причём число элементов известно заранее. В таком случае можно сразу зарезервировать нужный размер памяти с помощью функции reserve, чтобы при добавлении элементов не происходили реаллокации. Пусть, например, нам сначала задаётся число слов, а потом сами эти слова, и нам требуется сложить их в вектор:

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> words;

    size_t words_count;
    std::cin >> words_count;

    // Размер вектора остаётся нулевым, меняется только резерв:
    words.reserve(words_count);

    for (size_t i = 0; i != words_count; ++i) {
        std::string word;
        std::cin >> word;
        // Все добавления будут дешёвыми, без реаллокаций:
        words.push_back(word);
    }
}

Если передать в reserve величину меньше текущего резерва, то ничего не поменяется — резерв останется прежним.

Функцию reserve не следует путать с функцией resize, которая меняет количество элементов в векторе. Если аргумент функции resize меньше текущего размера, то лишние элементы в конце вектора удаляются. Если же он больше текущего размера, то при необходимости происходит реаллокация и в вектор добавляются новые элементы с дефолтным значением данного типа.

#include <vector>

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5};

    data.reserve(10);  // поменяли резерв, но размер вектора остался равным пяти

    data.resize(3);  // удалили последние элементы 4 и 5
    data.resize(6);  // получили вектор 1, 2, 3, 0, 0, 0
}

Многомерные векторы

Воспользуемся вектором векторов, чтобы сохранить матрицу (таблицу) целых чисел. Пусть на вход программы сначала поступают число строк и число столбцов матрицы, а потом — сами элементы построчно:

#include <iostream>
#include <vector>

int main() {
    size_t m, n;
    std::cin >> m >> n;  // число строк и столбцов

    // создаём матрицу matrix из m строк, каждая из которых — вектор из n нулей
    std::vector<std::vector<int>> matrix(m, std::vector<int>(n));

    for (size_t i = 0; i != m; ++i) {
        for (size_t j = 0; j != n; ++j) {
            std::cin >> matrix[i][j];
        }
    }

    // напечатаем матрицу, выводя элементы через табуляцию
    for (size_t i = 0; i != m; ++i) {
        for (size_t j = 0; j != n; ++j) {
            std::cout << matrix[i][j] << "t";
        }
        std::cout << "n";
    }
}

В этом примере мы заранее создали матрицу из нулей, а потом просто меняли её элементы.

Сортировка вектора

Рассмотрим типичную задачу — отсортировать вектор по возрастанию. Для этого в стандартной библиотеке в заголовочном файле algorithm есть готовая функция sort. Гарантируется, что сложность её работы в худшем случае составляет $O(n log n)$, где $n$ — число элементов в векторе. Типичные реализации используют алгоритм сортировки Introsort.

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6};

    // Сортировка диапазона вектора от начала до конца
    std::sort(data.begin(), data.end());

    // получим вектор 1, 1, 2, 3, 4, 5, 6, 9
}

В функцию sort передаются так называемые итераторы, ограничивающие рассматриваемый диапазон. В нашем случае мы передаём диапазон, совпадающий со всем вектором, от начала до конца. Соответствующие итераторы возвращают функции begin и end (не путать с front и back!). Итераторы можно считать обобщёнными индексами (но они могут быть и у контейнеров, не допускающих обычную индексацию). Подробнее про итераторы мы поговорим в отдельной главе.

Для сортировки по убыванию можно передать на вход обратные итераторы rbegin() и rend(), представляющие элементы вектора в перевёрнутом порядке:

std::sort(data.rbegin(), data.rend());  // 9, 6, 5, 4, 3, 2, 1, 1

В C++20 доступен более элегантный способ сортировки через std::ranges::sort:

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6};

    std::ranges::sort(data);  // можно передать сам вектор, а не его диапазоны
}

Для сортировки по умолчанию используется сравнение элементов с помощью оператора <. Этот оператор работает и для самих векторов: они сравниваются лексикографически. Поэтому можно без проблем отсортировать, например, строки в матрице (векторе векторов целых чисел).

Строки

Контейнер std::string можно рассматривать как особый случай вектора символов std::vector<char>, имеющий набор дополнительных функций. В частности, у строки есть все те же рассмотренные нами функции, что и у вектора (например, pop_back или resize). Рассмотрим некоторые специфические функции строки:

#include <iostream>
#include <string>

int main() {
    std::string s = "Some string";

    // приписывание символов и строк
    s += ' ';  // добавляем отдельный символ в конец, это аналог push_back
    s += "functions";  // добавляем строку в конец
    std::cout << s << "n";  // Some string functions

    // выделение подстроки
    // подстрока "string" из 6 символов начиная с 5-й позиции
    std::string sub1 = s.substr(5, 6);
    // подстрока "functions" с 12-й позиции и до конца
    std::string sub2 = s.substr(12);

    // поиск символа или подстроки
    size_t pos1 = s.find(' ');  // позиция первого пробела, в данном случае 4
    size_t pos2 = s.find(' ', pos1 + 1);  // позиция следующего пробела (11)
    size_t pos3 = s.find("str");  // вернётся 5
    size_t pos4 = s.find("#");  // вернётся std::string::npos
}

Вставку, замену и удаление подстрок можно сделать через указание индекса начала и длины подстроки:

#include <iostream>
#include <string>

int main() {
    std::string s = "Some string functions";

    // вставка подстроки
    s.insert(5, "std::");
    std::cout << s << "n";  // Some std::string functions

    // замена указанного диапазона на новую подстроку
    s.replace(0, 4, "Special");
    std::cout << s << "n";  // Special std::string functions

    // удаление подстроки
    s.erase(8, 5);  // Special string functions
}

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

В C++20 появились удобные функции starts_with и ends_with для проверки префикса или суффикса строк:

#include <iostream>
#include <string>

int main() {
    std::string phrase;
    std::getline(std::cin, phrase);

    if (phrase.starts_with("hello")) {
        std::cout << "Greetingn";
    }

    if (phrase.ends_with("bye")) {
        std::cout << "Farewelln";
    }
}

Источник

Примеры задач с решениями

Задача 1. Приняты две кодовые комбинации: 0001 и 1111. Определить значность кодовых комбинаций, их вес и кодовое расстояние между комбинациями.

Решение. 1. Значность кодовых комбинаций соответствует количеству разрядов — п. В принятых кодовых комбинациях п_х = п₂ = 4.

2. Вес определяется по количеству «1» в комбинации. В принятых кодовых комбинациях V_x = 1; V₂ =4.
3. Кодовое расстояние между комбинациями определяется как вес суммы по модулю 2 кодовых комбинаций. В принятых кодовых комбинациях d = 000101111 = 1110 = 3.

Задача 2. Принята кодовая комбинация 101011. Известно, что вектор ошибки ё = 101000 . Найти исходную кодовую комбинацию.

Решение. Для нахождения исходной кодовой комбинации определим сумму по модулю 2 для принятой комбинации и вектора ошибки, т.е. «’ = 101011, ё = 101000 , получим « = «’0ё = 1О1О1101О1ООО = ОООО11.

Задача 3. Передана кодовая комбинация 1100. Известно, что вес вектора ошибки V- =2. Найти возможные варианты искаженных комбинаций и кодовое расстояние, необходимое для обнаружения и устранения всех ошибок.

Решение. 1. Возможные варианты искаженных комбинаций состоят из тех комбинаций, которые отличаются от исходной двумя позиционными местами, так как т_е = 2. Возможные варианты искаженных комбинаций: 1010, 1001, ОНО, 0101, 0000.

Проверим комбинации, сложив их по модулю 2 с исходной комбинацией,т.е. ё = а®а‘.Получим ё_х =110001010 = 0110; е₂ =110001001 = 0101; ё₃ =110000110 = 1010; ё₄ =110000101 = 1001; ё₅ = 110000000 = 1100.

2. Для обнаружения и устранения всех ошибок необходимо, чтобы кодовое расстояние составляло d > t + 6 -г 1, где Г — обнаруживаемые ошибки; б — исправляемые ошибки. При разрядности нашего числа

п = 4 могут возникнуть четырехкратные ошибки. Следовательно, для их исправления и обнаружения необходимо, чтобы кодовое расстояние удовлетворяло условию 4 + 4 +1 > 9 , т.е. необходимо увеличить разрядность кода.

Задача 4. Определить корректирующую способность кода, имеющего разрешенные комбинации 00000, 01110, 10101 и 11011.

Код Рида-Соломона

Важной задачей кодологии при обработке информационных потоков кодированных сообщений в каналах систем связи и компьютерных является разделение потоков и селектирование их по заданным признакам. Выделенный поток расчленяется на отдельные сообщения и для каждого из них выполняется углубленный анализ с целью установления кода и его характеристик с последующим декодированием и доступом к семантике сообщения.

Так, например, для определенного Рида-Соломона кода (РС-кода) необходимо установить:

длину n кодового слова (блока);
количество k информационных и N-k проверочных символов;
неприводимый многочлен р(х), задающий конечное поле GF(2 r );
примитивный элемент α конечного поля;
порождающий многочлен g(x);
параметр j кода;
используемое перемежение;
последовательность передачи кодовых слов или символов в канал и еще некоторые другие.

Здесь в работе рассматривается несколько другая частная задача — моделирование собственно РС-кода, являющаяся центральной основной частью названной выше задачи анализа кода.

Описание РС-кода и его характеристик

Для удобства и лучшего уяснения сущности устройства РС-кода и процесса кодирования вначале приведем основные понятия и термины (элементы) кода.

Рида – Соломона коды (РС-код) можно интерпретировать как недвоичные коды БЧХ (Боуза – Чоудхури – Хоквингема), значения кодовых символов которых взяты из поля GF(2 r ), т. е. r информационных символов отображаются отдельным элементом поля. Коды Рида – Соломона – это линейные недвоичные систематические циклические коды, символы которых представляют собой r-битовые последовательности, где r – целое положительное число, большее 1.

Коды Рида – Соломона (n, k) определены на r-битовых символах при всех n и k, для которых:
0 r + 2, где
k – число информационных символов, подлежащих кодированию,
n – число кодовых символов в кодируемом блоке.

Для большинства (n, k)-кодов Рида – Соломона; (n, k) = (2 r –1, 2 r –1–2∙t), где
t – количество ошибочных символов, которые может исправить код, а
n–k = 2t – число контрольных символов.

Код Рида – Соломона обладает наибольшим минимальным расстоянием (числом символов, которыми отличаются последовательности), возможным для линейного кода. Для кодов Рида – Соломона минимальное расстояние определяется следующим образом: dmin = n–k +1.

Определение. РС-кодом над полем GF(q=р m ), с длиной блока n = q m -1, исправляющим t ошибок, является множество всех кодовых слов u_(n) над GF(q), для которых 2t последовательных компонентов спектра с номерами равны 0.

Тот факт, что 2t последовательных степеней α — корни порождающего многочлена g(x) или что спектр содержит 2t последовательных нулевых компонентов, является важным свойством кода, позволяющим исправлять t ошибок.

Информационный многочлен Q. Задает текст сообщения, которое делится на блоки (слова) постоянной длины и оцифровывается. Это то, что подлежит передаче в системе связи.
Порождающий многочлен g(x) РС-кода — многочлен, который преобразует информационные многочлены (сообщения) в кодовые слова путем перемножения Q·g(x)= С =u_(n) над GF(q).

Проверочный многочлен h(x) позволяет устанавливать наличие искаженных символов в слове.
Синдромный многочлен S(z). Многочлен, содержащий компоненты соответствующие ошибочным позициям. Вычисляется для каждого принятого декодером слова.
Многочлен ошибок E. Многочлен с длиной равной кодовому слову, с нулевыми значениями во всех позициях, кроме тех, что содержат искажения символов кодового слова.

Многочлен локаторов ошибок Λ(z) обеспечивает нахождение корней, указывающих позиции ошибок в словах, принятых приемной стороной канала связи (декодером). Корни его могут быть найдены методом проб и ошибок, т.е. путем подстановки по очереди всех элементов поля, пока Λ(z) не станет равным нулю.
Многочлен значений ошибок Ω(z)≡Λ(z)·S(z) (modz 2t ) сравним по модулю z 2t с произведением многочлена локаторов ошибок на синдромный многочлен.

Неприводимый многочлен поля р(x). Конечные поля существуют не при любом числе элементов, а только в случае, если число элементов является простым числом р или степенью q=р m простого числа. В первом случае поле называется простым (его элементы-вычеты чисел по модулю простого числа р), во втором-расширением соответствующего простого поля (его q элементов-многочленов степени m-1 и менее — это вычеты многочленов по модулю неприводимого над простым полем многочлена р(x) степени m)

Примитивный многочлен. Если корнем неприводимого многочлена поля является примитивный элемент α, то р(x) называют неприводимым примитивным многочленом.

В ходе изложения действий с РС-кодом нам потребуется неоднократно обращение к полю Галуа, поэтому сразу здесь поместим рабочую таблицу с элементами этого поля при разных представлениях элементов (десятичным числом, двоичным вектором, многочленом, степенью примитивного элемента).

Таблица П — Характеристики элементов конечного поля расширения GF(2 4 ), неприводимый многочлен p(x) = x 4 +x+1, примитивный элемент α =0010= 2₁₀

Пример 1. Над конечным полем GF(2 4 ), задан неприводимый многочлен поля p(x) = x 4 + x + 1, примитивный элемент α =2, и задан (n, k)- код Рида-Соломона (РС-код). Кодовое расстояние этого кода равно d = n — k + 1 = 7. Такой код может исправлять до трёх ошибок в блоке (кодовом слове) сообщения.

Порождающий многочлен g(z) кода имеет степень m =n-k = 15-9 = 6 (его корнями являются 6 элементов поля GF(2 4 ) в десятичном представлении, а именно элементы 2, 3, 4, 5, 6, 7) и определяется соотношением, т.е. многочленом от z с коэффициентами (элементами) из GF(2 4 ) в десятичном представлении при i = 1(1)6. В рассматриваемом РС-коде 2 9 = 512 кодовых слов.

Кодирование сообщений РС-кодом

В таблице П эти корни имеют и степенное представление .

Здесь z- абстрактная переменная, а α -примитивный элемент поля, через его степени выражены все (16) элементы поля. Многочленное представление элементов поля использует переменную х.
Вычисление порождающего многочлена g(x)=А·В РС-кода выполним частями (по три скобки):

Векторное представление (через коэффициенты g(z) элементами поля в десятичном представлении) порождающего многочлена имеет вид

g(z) = G = (1, 11, 15, 5, 7, 10, 7).

После формирования порождающего многочлена РС-кода, ориентированного на обнаружение и исправление ошибок, задается сообщение. Сообщение представляется в цифровом виде (например, ASCII- кодом), от которого переходят к многочленному или векторному представлению.

Информационный вектор (слово сообщения) имеет k — компонентов из (n, k). В примере k = 9, вектор получается 9-компонентный, все компоненты – это элементы поля GF(2 4 ) в десятичном представлении Q = (11, 13, 9, 6, 7, 15, 14, 12, 10).

Из этого вектора формируется кодовое слово u — вектор с 15 компонентами. Кодовые слова, как и сами коды, бывают систематическими и несистематическими. Несистематическое кодовое слово получают умножением информационного вектора Q на вектор, соответствующий порождающему многочлену

После преобразований получаем несистематическое кодовое слово (вектор) в виде
Q·g = .

При систематическом кодировании сообщение (информационный вектор) представляют многочленом Q(z) в форме Q(z)=q(z)·g(z) + R(z), где степень degR(z) n — k (в примере Z n — k = Z 6 ) и выполняют после сдвига деление Q(z)·Z n — k на g(z). В результате находят остаток от деления R(z). Все операции выполняют над полем GF(2 4 )

(11, 13, 9, 6, 7, 15, 14, 12, 10, 0, 0, 0, 0, 0, 0) =
=(1, 11, 15, 5, 7, 10, 7)·(11, 15, 9, 10,12,10,10,10, 3) + (1, 2, 3, 7, 13, 9) = G·S + R.

Остаток при делении многочленов вычисляется обычным способом (уголком см.здесь Пример 6). Деление выполняется по образцу: Пусть Q = 26, g(z) = 7 тогда 26 = 7·3 +R(z), R(z)=26 -7·3 =26-21 = 5. Вычисление остатка R(z) от деления многочленов. Приписываем к вектору Q справа остаток R.

Получаем u — кодовое слово в систематическом виде. Этот вид явно содержит информационное сообщение в k старших разрядах кодового слова

u = (11,13,9,6,7,15,14,12,10; 1, 2, 3, 7, 13, 9)

Разряды вектора нумеруются справа налево от 0(1)14. Шесть младших разрядов справа являются проверочными.

Декодирование кодов Рида-Соломона

После получения блока декодер обрабатывает каждый блок (кодовое слово) и исправляет ошибки, которые возникли во время передачи или хранения. Декодер делит полученный многочлен на порождающий многочлен кода РС. Если остаток равен нулю, то ошибок не обнаружено, в противном случае — имеют место ошибки.

Типичный РС-декодер выполняет пять этапов в цикле декодирования, а именно:

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

Завершается цикл извлечением сообщения из кодовых слов (снятие кода).

Генерация синдрома из принятого кодового слова является первым этапом процесса
декодирования. Здесь вычисляются синдромы и определяется, есть ли ошибки в полученном кодовом слове или нет

Декодирование кодовых слов РС – кода может быть организовано разными способами. К классическим способам относится декодирование с привлечением алгоритмов, работающих во временной или в частотной области, которые используют вычисление синдрома, либо не используют. Не углубляясь в теорию этого вопроса, остановим свой выбор на декодировании с вычислением синдромов кодовых слов во временной области.

Обнаружение искажений

Синдромный , где вектор последовательно определяется для каждого из полученных декодером на его входе кодовых слов. При нулевых значениях компонентов вектора синдрома , декодер считает, что в принятом слове ошибки нет. Если же хотя бы для одного , то декодер делает вывод о наличии ошибок в кодовом векторе и приступает к их выявлению, что является 1-м шагом работы декодера.

Вычисление синдромного многочлена
Умножение на приемной стороне кодового слова С на проверочную матрицу Н может давать в результате два исхода:

синдромный вектор S=0, что соответствует отсутствию ошибок в векторе C;
синдромный вектор S≠0, что означает наличие ошибок (одной или более) в компонентах вектора C.

Интерес представляет второй случай.

Кодовый вектор с ошибками представлен в виде C(E) =C + E, E– вектор ошибок. Тогда

Компоненты Sj синдрома определяются либо соотношением суммирования
для n = q-1 и j = 1(1)m = n-k, либо схемой Горнера:

Пример 2. Пусть вектор ошибок имеет вид Е = . Он искажает в кодовом векторе символы на 3-й и 10-й позициях. Значения ошибок соответственно 8 и 12 — эти значения также являются элементами поля GF(2 4 ) и заданы в десятичном (табл. П) представлении. В векторе Е нумерация позиций от младших справа налево, начиная с 0(1)14.

Сформируем теперь кодовый вектор с двумя ошибками в 3-ем разряде и в 10-ом со значениями 8 и 12 соответственно. Это осуществляется суммированием в поле GF(2 4 ) по правилам арифметики этого поля. Суммирование элементов поля с нулем не изменяет их значения. Ненулевые значения (элементы поля) суммируются после преобразования их к многочленному представлению, как обычно суммируются многочлены, но коэффициенты при неизвестной приводятся по mod 2.

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

Ниже показано вычисление искажённых ошибками значений в 10 и 3 позициях кодового слова:

Декодер вычисления выполняет по общей формуле для компонентов Sj, j=1(1)m. Здесь (в модели) используем соотношение , так как E задаём (моделируем) в программе сами, то ненулевые слагаемые получаются только при i = 3 и i = 10.

Специально ниже покажем вычисления по этой формуле в развернутом виде.

Проверочная матрица РС – кода

Как только сформулирован порождающий многочлен кода, появляется возможность построения проверочной матрицы для кодовых слов, а также определение количества исправляемых ошибок (см.здесь, декодер ). Построим вспомогательную матрицу [7×15], из которой могут быть получены две разные проверочные матрицы: первые шесть строк – одна и последние шесть строк – другая.

Сама матрица формируется специальным образом. Первые две строки очевидны, третья строка и все последующие получены вычитанием из предыдущей (второй) строки отрезка чисел натурального ряда 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 по mod 15. При возникновении нулевого значения оно заменяется числом 15, отрицательные вычеты преобразуются в положительные.

Каждая матрица соответствует своему порождающему многочлену для систематического и несистематического кодирования.

Определение коэффициентов синдромного многочлена

Далее будем определять коэффициенты синдромного многочлена при j=1(1)6.
Относительно кодового слова с длиной , поступающего на вход декодера мы допускаем, что оно искажено ошибками.

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

количество искаженных позиций у кодового слова
;
номера (положение) искаженных позиций в кодовом слове ;
значения (величины) искажений .

Как вычисляется и используется далее синдромный вектор (многочлен) S? Его роль при декодировании кодовых слов очень значительна. Покажем это с иллюстрацией на числовом примере.

Пример 3. (Вычисление компонентов синдромного вектора >$» data-tex=»inline»/> )

то в итоге имеем >=(S_1,S_2,S_3,S_4,S_5,S_6)$» data-tex=»inline»/> =

Для дальнейшего рассмотрения введем новые понятия. Величину будем называть локатором ошибок, здесь искаженный символ кодового слова на позиции , α – примитивный элемент поля GF(2 4 ).

Множество локаторов ошибок конкретного кодового слова рассматривается далее как коэффициенты многочлена локаторов ошибок σ(z), корнями которого являются значения , обратные локаторам.

При этом выражения обращаются в нуль.

всегда свободный член уравнения всегда свободный член уравнения .
Степень многочлена локаторов ошибок равна v – количеству ошибок и не превышает величины .

Все искаженные символы находятся на разных позициях слова, следовательно, среди локаторов , не может быть повторяющихся элементов поля, а многочлен σ(z)=0 не имеет кратных корней.

Величины ошибок для удобства записи переобозначим символом . Для коэффициентов синдромного многочлена ранее рассматривались нелинейные уравнения. В нашем случае v=1 начало отсчета компонентов синдрома.

где — неизвестные величины, а — известные, вычисляемые на первом этапе декодирования, параметры (компоненты синдромного вектора).

Методы решения подобных систем нелинейных уравнений неизвестны, но решения отыскивают, используя ухищрения (обходные пути). Выполняется переход к Ганкелевой (теплицевой) системе линейных уравнений относительно коэффициентов многочлена локаторов.

Преобразование к системе линейных уравнений

В уравнение многочлена локаторов ошибок подставляется значение его корней . При этом многочлен обращается в нуль. Образуется тождество, обе части которого умножаем на , получаем:

Таких равенств получаем

Суммируем эти равенства по всем , при которых эти равенства выполняются. Так как многочлен σ(z) имеет v корней , раскроем скобки и перенесем коэффициенты за знак суммы:

В этом равенстве согласно системе нелинейных уравнений, приведенной
ранее, каждая сумма равна одному из компонентов вектора синдрома. Отсюда заключает, что относительно коэффициентов можно выписать систему уже линейных уравнений.

Знаки «–» при вычислениях над двоичным полем опускаются, так как со-ответствуют «+». Полученная система линейных уравнений является ганкелевой и ей соответствует матрица с размерами бит.

Эта матрица не вырождена, если число ошибок в кодовом слове C(E) строго равно , т.е. способность помехоустойчивости данного кода не нарушилась.

Решение системы линейных уравнений

Полученная система линейных уравнений в качестве неизвестных содержит коэффициенты многочлена локаторов ошибок для кодового слова C(E). Известными считаются вычисленные ранее компоненты синдромного вектора . Здесь t – количество ошибок в слове, m – количество проверочных позиций в слове.

Существуют разные методы решения сформированной системы.

Отметим, что матрица (ганкелева) не вырождена для размерностей, ограниченных количеством допустимым в отдельном слове (меньшем 0.5m) ошибок. При этом система уравнений однозначно разрешается, а задача может быть сведена просто к обращению ганкелевой матрицы. Желательно было бы снять ограничение на размерность матриц, т.е. над бесконечным полем.

Над бесконечными полями известны методы решения ганкелевой системы линейных уравнений:

итеративный метод Тренча – Берлекэмпа — Месси (ТБМ-метод); (1)
прямой детерминированный Питерсона — Горенштейна — Цирлера; (ПГЦ — метод); (2)
метод Сугиямы, использующий алгоритм Евклида для нахождения НОД (С-метод).(3)

Не рассматривая других методов, остановим свой выбор на ТБМ-методе. Мотивировка выбора следующая.

Метод (ПГЦ) прост и хорош, но для малого количества исправляемых ошибок, С-метод сложен для реализации на ЭВМ и ограниченно опубликован (освещен) в источниках, хотя С-метод как и ТБМ-метод по известному многочлену синдромов S(z) обеспечивает решение уравнения Падэ над полем Галуа. Это уравнение сформировано для многочлена локаторов ошибок σ(z) и многочлена ω(z), в теории кодирования называется ключевым уравнением Падэ:

Решением ключевого уравнения является совокупность корней многочлена σ(z), и соответственно локаторов , т.е. позиции ошибок. Значения (величины) ошибок определяются из формулы Форни в виде

где и — значения многочленов σ(z) и ω(z) в точке , обратной корню многочлена σ(z);
i — позиция ошибки; — формальная производная многочлена σ(z) по z;

Формальная производная многочлена в конечном поле

Имеются различия и сходство для производной по переменной в поле вещественных чисел и формальной производной в конечном поле. Рассмотрим многочлен

– это элементы поля, i = 1(1)n

Элементы поля. Задан код над вещественным полем GF(2 4 ). Производная по z имеет вид:

В бесконечном вещественном поле операции умножить на n и суммировать n раз совпадают. Для конечных полей производная определяется иначе.

Производная по аналогии определяется соотношением:

где ((i)) = 1+1+. +1, (i) раз, суммируемых по правилам конечного поля: знак + обозначает операцию «суммировать столько-то раз», т.е. элемент повторить 2 раза, элемент повторить 3 раза, элемент повторить n раз.

Ясно, что эта операция не совпадает с операции умножения в конечном поле. В частности, в полях GF(2 r ) сумма четного числа одинаковых слагаемых берется по mod2 и обнуляется, а нечетного – равна самому слагаемому без изменений. Следовательно, в поле GF(2 r ) производная получает вид

вторая и старшие четные производные в этом поле равны нулю.

Из алгебры известно, если многочлен имеет кратные корни (кратность р ), то производная многочлена будет иметь этот же корень, но с кратностью р-1. Если р = 1, то f(z) и f ‘(z) не имеет общего корня. Следовательно, если многочлен и его производная имеют общий делитель, то существует кратный корень. Все корни производной f ‘(z) эти корни кратные в f(z).

Метод решения ключевого уравнения

ТМБ (Тренча-Берлекэмпа-Месси) — метод решения ключевого уравнения. Итеративный алгоритм обеспечивает определение многочленов σ(z) и ω(z), и решение уравнения Падэ (ключевого).

Исходные данные: коэффициенты многочлена степени n-1.
Цель. Определение в явном (аналитическом) виде многочленов σ(z) и ω(z).

В алгоритме используются обозначения: j — номер шага, — степень многочлена, — разложение многочлена по степеням и — промежуточные переменные и функции на j-м шаге алгоритма;

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

Пример 4. Выполнение итеративного алгоритма для вектора
S=(8,13,7,13,15,15). Определяются многочлены и .

Таблица 2 – Расчет многочленов локаторов ошибок

Итак , =7z+8.

Многочлен локаторов ошибок σ(z) над полем GF(2 4 ) с неприводимым многочленом p(x) = x 4 + x + 1 имеет корни

и , в этом легко убедиться непосредственной проверкой, т.е. и 13=4^<-1>$» data-tex=»inline»/>. Подстановка корней в
=
=;
=
=.

Взяв формальную производную от σ(z), получаем σ_2(z) =2·14+13 =13, так как 14z берется в сумме 2 раза и по mod 2 обращается в нуль.

С использованием формулы Форни найдем выражения для расчета величин ошибок .

Подстановкой значений i = 3 и i = 10 позиций в последнее выражение
находим

= =8$» data-tex=»inline»/>;
= =12$» data-tex=»inline»/>.

Архитектура построения программного комплекса

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

Исходными данными для программного комплекса является цифровой поток информации, выгруженной с помощью дампа из файла. Для удобства анализа и наглядности работы комплекса предполагается использование .txt файлов.

Загруженный цифровой поток представляется в виде массивов данных, в ходе работы комплекса над которыми применяются различные вычислительные действия.

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

Результаты работы программного комплекса представляются в виде числовых данных, отображающихся в таблицах.

Сохранение промежуточных и окончательных результатов анализа производится в файлы.

Схема функционирования программного комплекса

Работа с комплекса начинается с загрузки цифрового потока с помощью дампа из файла. После загрузки пользователю предоставляется возможность визуального представления двоичного содержимого файла и его текстового содержимого.

В рамках данного интерфейса должны реализовываться следующие функциональные задачи:

Загрузка исходного сообщения;
Преобразование сообщения в дамп;
Кодирование сообщения;
Моделирование перехваченного сообщения
Построение спектров полученных кодовых слов с целью анализа их визуального представления;
Вывод на экран параметров кода.

Описание работы программного комплекса

При запуске исполняемого файла программы на экране появляется окно представленное на рисунке 2, в котором отображён основной интерфейс программы.

На вход программы подается файл, который нужно передать по каналу связи. Для его передачи по реальным каналам связи требуется кодирование – добавление к нему проверочных символов, необходимых для однозначного декодирования слова на источнике-получателе. Для начала работы комплекса необходимо с помощью кнопки “Загрузить файл” выбрать нужный текстовый файл. Его содержимое будет отображено в нижнем поле главного окна программы.

Двоичное представление сообщения будет представлено в соответствующем поле, двоичное представление информационных слов – в поле “Двоичное представление информационных слов”.

Число бит исходного сообщения и общее число слов в нем отображаются в полях “Количество бит в передаваемом сообщении” и “Количество слов в передаваемом сообщении”.

Сформированные информационные и кодовые слова отображаются в таблицах в правой части основного окна программы.

Окно программы с промежуточными результатами представлено на рисунке 3.

Рисунок 3 – Промежуточное представление результатов работы программного комплекса

Рисунок 4. Результаты загрузки файла сообщения

Рисунок 5. Результаты кодирования файла

Рисунок 6. Вывод сообщения с внесенными в него ошибками.

Рисунок 7. Вывод результатов декодирования и сообщения с внесенными в него ошибками

Рисунок 8. Вывод декодированного сообщения.

Заключение

АНБ США является главным оператором глобальной системы перехвата «Эшелон». «Эшелон» располагает разветвлённой инфраструктурой, включающей в себя станции наземного слежения, расположенные по всему миру. Отслеживаются практически все мировые информационные потоки.

Исследование возможностей получения доступа к семантике кодированных информационных сообщений в настоящее время активной информационной борьбы как в области технологий, так и в политике — стало очередным вызовом и одной из актуальных и востребованных задач современности.

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

Найти кодовые векторы по информационным блокам

В обычном равномерном непомехоустойчивом коде число разрядов n в кодовых комбинациях определяется числом сообщений и основанием кода.

Коды, у которых все кодовые комбинации разрешены, называются простыми или равнодоступными и являются полностью безызбыточными. Безызбыточные коды обладают большой «чувствительностью» к помехам. Внесение избыточности при использовании помехоустойчивых кодов связано с увеличением n – числа разрядов кодовой комбинации. Таким образом, все множество комбинаций можно разбить на два подмножества: подмножество разрешенных комбинаций, обладающих определенными признаками, и подмножество запрещенных комбинаций, этими признаками не обладающих.

Помехоустойчивый код отличается от обычного кода тем, что в канал передаются не все кодовые комбинации N, которые можно сформировать из имеющегося числа разрядов n, а только их часть Nk , которая составляет подмножество разрешенных комбинаций. Если при приеме выясняется, что кодовая комбинация принадлежит к запрещенным, то это свидетельствует о наличии ошибок в комбинации, т.е. таким образом решается задача обнаружения ошибок. При этом принятая комбинация не декодируется (не принимается решение о переданном сообщении). В связи с этим помехоустойчивые коды называют корректирующими кодами. Корректирующие свойства избыточных кодов зависят от правила их построения, определяющего структуру кода, и параметров кода (длительности символов, числа разрядов, избыточности и т. п.).

Первые работы по корректирующим кодам принадлежат Хеммингу, который ввел понятие минимального кодового расстояния dmin и предложил код, позволяющий однозначно указать ту позицию в кодовой комбинации, где произошла ошибка. К информационным элементам k в коде Хемминга добавляется m проверочных элементов для автоматического определения местоположения ошибочного символа. Таким образом, общая длина кодовой комбинации составляет: n = k + m.

Метричное представление n,k-кодов

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

Почти все блочные коды относятся к разделимым кодам, кодовые комбинации которых состоят из двух частей: информационной и проверочной. При общем числе n символов в блоке число информационных символов равно k, а число проверочных символов:

К основным характеристикам корректирующих кодов относятся:

— число разрешенных и запрещенных кодовых комбинаций;
— избыточность кода;
— минимальное кодовое расстояние;
— число обнаруживаемых или исправляемых ошибок;
— корректирующие возможности кодов.

Для блочных двоичных кодов, с числом символов в блоках, равным n, общее число возможных кодовых комбинаций определяется значением

Число разрешенных кодовых комбинаций при наличии k информационных разрядов в первичном коде:

Очевидно, что число запрещенных комбинаций:

а с учетом отношение будет

где m – число избыточных (проверочных) разрядов в блочном коде.

Избыточностью корректирующего кода называют величину

Эта величина показывает, какую часть общего числа символов кодовой комбинации составляют информационные символы. В теории кодирования величину Bk называют относительной скоростью кода. Если производительность источника информации равна H символов в секунду, то скорость передачи после кодирования этой информации будет

поскольку в закодированной последовательности из каждых n символов только k символов являются информационными.

Если число ошибок, которые нужно обнаружить или исправить, значительно, то необходимо иметь код с большим числом проверочных символов. Чтобы при этом скорость передачи оставалась достаточно высокой, необходимо в каждом кодовом блоке одновременно увеличивать как общее число символов, так и число информационных символов.

При этом длительность кодовых блоков будет существенно возрастать, что приведет к задержке информации при передаче и приеме. Чем сложнее кодирование, тем длительнее временная задержка информации.

Минимальное кодовое расстояние – dmin. Для того чтобы можно было обнаружить и исправлять ошибки, разрешенная комбинация должна как можно больше отличаться от запрещенной. Если ошибки в канале связи действуют независимо, то вероятность преобразования одной кодовой комбинации в другую будет тем меньше, чем большим числом символов они различаются.

Если интерпретировать кодовые комбинации как точки в пространстве, то отличие выражается в близости этих точек, т. е. в расстоянии между ними.

Количество разрядов (символов), которыми отличаются две кодовые комбинации, можно принять за кодовое расстояние между ними. Для определения этого расстояния нужно сложить две кодовые комбинации «по модулю 2» и подсчитать число единиц в полученной сумме. Например, две кодовые комбинации xi = 01011 и xj = 10010 имеют расстояние d(xi,xj) , равное 3, так как:

Здесь под операцией ⊕ понимается сложение «по модулю 2».

Заметим, что кодовое расстояние d(xi,x0) между комбинацией xi и нулевой x0 = 00. 0 называют весом W комбинации xi, т.е. вес xi равен числу «1» в ней.

Расстояние между различными комбинациями некоторого конкретного кода могут существенно отличаться. Так, в частности, в безызбыточном первичном натуральном коде n = k это расстояние для различных комбинаций может изменяться от единицы до величины n, равной разрядности кода. Особую важность для характеристики корректирующих свойств кода имеет минимальное кодовое расстояние dmin, определяемое при попарном сравнении всех кодовых комбинаций, которое называют расстоянием Хемминга.

В безызбыточном коде все комбинации являются разрешенными и его минимальное кодовое расстояние равно единице – dmin=1. Поэтому достаточно исказиться одному символу, чтобы вместо переданной комбинации была принята другая разрешенная комбинация. Чтобы код обладал корректирующими свойствами, необходимо ввести в него некоторую избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешенными комбинациями не менее двух – dmin ≥ 2..

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

Число обнаруживаемых или исправляемых ошибок

При применении двоичных кодов учитывают только дискретные искажения, при которых единица переходит в нуль («1» → «0») или нуль переходит в единицу («0» → «1»). Переход «1» → «0» или «0» → «1» только в одном элементе кодовой комбинации называют единичной ошибкой (единичным искажением). В общем случае под кратностью ошибки подразумевают число позиций кодовой комбинации, на которых под действием помехи одни символы оказались замененными на другие. Возможны двукратные (g = 2) и многократные (g > 2) искажения элементов в кодовой комбинации в пределах 0 ≤ g ≤ n.

Минимальное кодовое расстояние является основным параметром, характеризующим корректирующие способности данного кода. Если код используется только для обнаружения ошибок кратностью g0, то необходимо и достаточно, чтобы минимальное кодовое расстояние было равно dmin ≥ g0 + 1.

В этом случае никакая комбинация из go ошибок не может перевести одну разрешенную кодовую комбинацию в другую разрешенную. Таким образом, условие обнаружения всех ошибок кратностью g0 можно записать

Чтобы можно было исправить все ошибки кратностью gu и менее, необходимо иметь минимальное расстояние, удовлетворяющее условию dmin ≥ 2gu

В этом случае любая кодовая комбинация с числом ошибок gu отличается от каждой разрешенной комбинации не менее чем в gu+1 позициях. Если условие не выполнено, возможен случай, когда ошибки кратности g исказят переданную комбинацию так, что она станет ближе к одной из разрешенных комбинаций, чем к переданной или даже перейдет в другую разрешенную комбинацию. В соответствии с этим, условие исправления всех ошибок кратностью не более gи можно записать:

Из и следует, что если код исправляет все ошибки кратностью gu, то число ошибок, которые он может обнаружить, равно go = 2gu. Следует отметить, что эти соотношения устанавливают лишь гарантированное минимальное число обнаруживаемых или исправляемых ошибок при заданном dmin и не ограничивают возможность обнаружения ошибок большей кратности. Например, простейший код с проверкой на четность с dmin = 2 позволяет обнаруживать не только одиночные ошибки, но и любое нечетное число ошибок в пределах go 3 = . Нулевой синдром (000) указывает на то, что ошибки при приеме отсутствуют или не обнаружены. Всякому ненулевому синдрому соответствует определенная конфигурация ошибок, которая и исправляется. Классические коды Хемминга имеют число синдромов, точно равное их необходимому числу (что позволяет исправить все однократные ошибки в любом информативном и проверочном символах) и включают один нулевой синдром. Такие коды называются плотноупакованными.

Усеченные коды являются неплотноупакованными, так как число синдромов у них превышает необходимое. Так, в коде (9,5) при четырех проверочных символах число синдромов будет равно 2 4 =16, в то время как необходимо всего 10. Лишние 6 синдромов свидетельствуют о неполной упаковке кода (9,5).

Рис. 2 Декодер для (7, 4)-кода Хемминга

Для рассматриваемого кода (7,4) в табл. 2 представлены ненулевые синдромы и соответствующие конфигурации ошибок.

Таким образом, (7,4)-код позволяет исправить все одиночные ошибки. Простая проверка показывает, что каждая из ошибок имеет свой единственный синдром. При этом возможно создание такого цифрового корректора ошибок (дешифратора синдрома), который по соответствующему синдрому исправляет соответствующий символ в принятой кодовой группе. После внесения исправления проверочные символы ri можно на выход декодера (рис. 2) не выводить. Две или более ошибок превышают возможности корректирующего кода Хемминга, и декодер будет ошибаться. Это означает, что он будет вносить неправильные исправления и выдавать искаженные информационные символы.

Идея построения подобного корректирующего кода, естественно, не меняется при перестановке позиций символов в кодовых словах. Все такие варианты также называются (7,4)- кодами Хемминга.

Циклические коды

Своим названием эти коды обязаны такому факту, что для них часть комбинаций, либо все комбинации могут быть получены путем циклическою сдвига одной или нескольких базовых комбинаций кода.

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

Для определения неприводимых многочленов раскладывают на простые множители бином х n -1. Так, для n = 7 это разложение имеет вид:

(x 7 )=(x-1)(x 3 +x 2 )(x 3 +x-1)

Каждый из полученных множителей разложения может применяться для построения корректирующего кода.

Неприводимый полином g(x) называют задающим, образующим или порождающим для корректирующего кода. Длина n (число разрядов) создаваемого кода произвольна. Кодовая последовательность (комбинация) корректирующего кода состоит из к информационных разрядов и n — к контрольных (проверочных) разрядов. Степень порождающего полинома r = n — к равна количеству неинформационных контрольных разрядов.

Если из сделанного выше разложения (при n = 7) взять полипом (х — 1), для которого r=1, то k=n-r=7-1=6. Соответствующий этому полиному код используется для контроля на чет/нечет (обнаружение ошибок). Для него минимальное кодовое расстояние D₀ = 2 (одна единица от D₀ — для исходного двоичного кода, вторая единица — за счет контрольного разряда).

Если же взять полином (x 3 +x 2 +1) из указанного разложения, то степень полинома r=3, а k=n-r=7-3=4.

Контрольным разрядам в комбинации для некоторого кода могут быть четко определено место (номера разрядов). Тогда код называют систематическим или разделимым. В противном случае код является неразделимым.

Способы построения циклических кодов по заданному полиному.

1) На основе порождающей (задающей) матрицы G, которая имеет n столбцов, k строк, то есть параметры которой связаны с параметрами комбинаций кода. Порождающую матрицу строят, взяв в качестве ее строк порождающий полином g(x) и (k — 1) его циклических сдвигов:

Пример; Определить порождающую матрицу, если известно, что n=7, k=4, задающий полином g(x)=x 3 +х+1.

Решение: Кодовая комбинация, соответствующая задающему полиному g(x)=x 3 +х+1, имеет вид 1011. Тогда порождающая матрица G_7,4 для кода при n=7, к=4 с учетом того, что k-1=3, имеет вид:

Порождающая матрица содержит k разрешенных кодовых комбинаций. Остальные комбинации кода, количество которых (2 k — k) можно определить суммированием по модулю 2 всевозможных сочетаний строк матрицы G_n,k. Для матрицы, полученной в приведенном выше примере, суммирование по модулю 2 четырех строк 1-2, 1-3, 1-4, 2-3, 2-4, 3-4 дает следующие кодовые комбинации циклического кода:

Другие комбинации искомого корректирующего кода могут быть получены сложением трех комбинаций, например, из сочетания строк 1-3-4, что дает комбинацию 1111111, а также сложением четырех строк 1-2-3-4, что дает комбинацию 1101001 и т.д.

Ряд комбинаций искомого кода может быть получено путем дальнейшего циклического сдвига комбинаций порождающей матрицы, например, 0110001, 1100010, 1000101. Всего для образования искомого циклического кода требуется 2 k =2 4 =16 комбинаций.

2) Умножение исходных двоичных кодовых комбинаций на задающий полином.

Исходными комбинациями являются все k-разрядные двоичные комбинации. Так, например, для исходной комбинации 1111 (при k = 4) умножение ее на задающий полином g(x)=x 3 +х+1=1011 дает 1101001. Полученные на основе двух рассмотренных способов циклические коды не являются разделимыми.

3) Деление на задающий полином.

Для получения разделимого (систематического) циклического кода необходимо разделить многочлен x n-k *h(x), где h(x) — исходная двоичная комбинация, на задающий полином g(x) и прибавить полученный остаток от деления к многочлену x n-k *h(x).

Заметим, что умножение исходной комбинации h(x) на x n-k эквивалентно сдвигу h(x) на (n-к) разрядов влево.

Пример: Требуется определить комбинации циклического разделимого кода, заданного полиномом g(x)=x 3 +х+1=1011 и имеющего общее число разрядов 7, число информационных разрядов 4, число контрольных разрядов (n-k)=3.

Решение: Пусть исходная комбинация h(x)=1100. Умножение ее на x n-k =x 3 =1000 дает x 3 *(x 3 +x 2 )=1100000, то есть эквивалентно сдвигу исходной комбинации на 3 разряда влево. Деление комбинации 1100000 на комбинацию 1011, эквивалентно задающему полиному, дает:

Полученный остаток от деления, содержащий x n-k =3 разряда, прибавляем к полиному, в результате чего получаем искомую комбинацию разделимого циклического кода: 1100010. В ней 4 старших разряда (слева) соответствуют исходной двоичной комбинации, а три младших разряда являются контрольными.

Следует сделать ряд указаний относительно процедуры деления:

1) При делении задающий полином совмещается старшим разрядом со старшим «единичными разрядом делимого.

2) Вместо вычитания по модулю 2 выполняется эквивалентная ему процедура сложения по модулю 2.

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

Для проверки правильности выполнения процедуры определения комбинации циклического кода необходимо разделить полученную комб1шацию на задающий полином с учетом сделанных выше замечаний. Получение нулевого остатка от такого деления свидетельствует о правильности определения комбинации.

Логический код 4В/5В

Логический код 4В/5В заменяет исходные символы длиной в 4 бита на символы длиной в 5 бит. Так как результирующие символы содержат избыточные биты, то общее количество битовых комбинаций в них больше, чем в исходных. Таким образом, пяти-битовая схема дает 32 (2 5 ) двухразрядных буквенно-цифровых символа, имеющих значение в десятичном коде от 00 до 31. В то время как исходные данные могут содержать только четыре бита или 16 (2 4 ) символов.

Поэтому в результирующем коде можно подобрать 16 таких комбинаций, которые не содержат большого количества нулей, а остальные считать запрещенными кодами (code violation). В этом случае длинные последовательности нулей прерываются, и код становится самосинхронизирующимся для любых передаваемых данных. Исчезает также постоянная составляющая, а значит, еще более сужается спектр сигнала. Но этот метод снижает полезную пропускную способность линии, так как избыточные единицы пользовательской информации не несут, и только «занимают эфирное время». Избыточные коды позволяют приемнику распознавать искаженные биты. Если приемник принимает запрещенный код, значит, на линии произошло искажение сигнала.

Итак, рассмотрим работу логического кода 4В/5В. Преобразованный сигнал имеет 16 значений для передачи информации и 16 избыточных значений. В декодере приемника пять битов расшифровываются как информационные и служебные сигналы.

Для служебных сигналов отведены девять символов, семь символов — исключены.

Исключены комбинации, имеющие более трех нулей (01 — 00001, 02 — 00010, 03 — 00011, 08 — 01000, 16 — 10000). Такие сигналы интерпретируются символом V и командой приемника VIOLATION — сбой. Команда означает наличие ошибки из-за высокого уровня помех или сбоя передатчика. Единственная комбинация из пяти нулей (00 — 00000) относится к служебным сигналам, означает символ Q и имеет статус QUIET — отсутствие сигнала в линии.

Такое кодирование данных решает две задачи — синхронизации и улучшения помехоустойчивости. Синхронизация происходит за счет исключения последовательности более трех нулей, а высокая помехоустойчивость достигается приемником данных на пяти-битовом интервале.

Цена за эти достоинства при таком способе кодирования данных — снижение скорости передачи полезной информации. К примеру, В результате добавления одного избыточного бита на четыре информационных, эффективность использования полосы частот в протоколах с кодом MLT-3 и кодированием данных 4B/5B уменьшается соответственно на 25%.

Схема кодирования 4В/5В представлена в таблице.

Итак, соответственно этой таблице формируется код 4В/5В, затем передается по линии с помощью физического кодирования по одному из методов потенциального кодирования, чувствительному только к длинным последовательностям нулей — например, в помощью цифрового кода NRZI.

Символы кода 4В/5В длиной 5 бит гарантируют, что при любом их сочетании на линии не могут встретиться более трех нулей подряд.

Буква ^ В в названии кода означает, что элементарный сигнал имеет 2 состояния — от английского binary — двоичный. Имеются также коды и с тремя состояниями сигнала, например, в коде 8В/6Т для кодирования 8 бит исходной информации используется код из 6 сигналов, каждый из которых имеет три состояния. Избыточность кода 8В/6Т выше, чем кода 4В/5В, так как на 256 исходных кодов приходится 36=729 результирующих символов.

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

Единственное требование — для обеспечения заданной пропускной способности линии передатчик, использующий избыточный код, должен работать с повышенной тактовой частотой. Так, для передачи кодов 4В/5В со скоростью 100 Мб/с передатчик должен работать с тактовой частотой 125 МГц. При этом спектр сигнала на линии расширяется по сравнению со случаем, когда по линии передается чистый, не избыточный код. Тем не менее, спектр избыточного потенциального кода оказывается уже спектра манчестерского кода, что оправдывает дополнительный этап логического кодирования, а также работу приемника и передатчика на повышенной тактовой частоте.

В основном для локальных сетей проще, надежней, качественней, быстрей — использовать логическое кодирование данных с помощью избыточных кодов, которое устранит длительные последовательности нулей и обеспечит синхронизацию сигнала, потом на физическом уровне использовать для передачи быстрый цифровой код NRZI, нежели без предварительного логического кодирования использовать для передачи данных медленный, но самосинхронизирующийся манчестерский код.

Например, для передачи данных по линии с пропускной способностью 100М бит/с и полосой пропускания 100 МГц, кодом NRZI необходимы частоты 25 — 50 МГц, это без кодирования 4В/5В. А если применить для NRZI еще и кодирование 4В/5В, то теперь полоса частот расширится от 31,25 до 62,5 МГц. Но тем не менее, этот диапазон еще «влазит» в полосу пропускания линии. А для манчестерского кода без применения всякого дополнительного кодирования необходимы частоты от 50 до 100 МГц, и это частоты основного сигнала, но они уже не будут пропускаться линией на 100 МГц.

Скрэмблирование

Другой метод логического кодирования основан на предварительном «перемешивании» исходной информации таким образом, чтобы вероятность появления единиц и нулей на линии становилась близкой.

Устройства, или блоки, выполняющие такую операцию, называются скрэмблерами (scramble — свалка, беспорядочная сборка) .

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

Избыточные биты при этом по линии не передаются.

Суть скремблирования заключается просто в побитном изменении проходящего через систему потока данных. Практически единственной операцией, используемой в скремблерах является XOR — «побитное исключающее ИЛИ», или еще говорят — сложение по модулю 2. При сложении двух единиц исключающим ИЛИ отбрасывается старшая единица и результат записывается — 0.

Метод скрэмблирования очень прост. Сначала придумывают скрэмблер. Другими словами придумывают по какому соотношению перемешивать биты в исходной последовательности с помощью «исключающего ИЛИ». Затем согласно этому соотношению из текущей последовательности бит выбираются значения определенных разрядов и складываются по XOR между собой. При этом все разряды сдвигаются на 1 бит, а только что полученное значение («0» или «1») помещается в освободившийся самый младший разряд. Значение, находившееся в самом старшем разряде до сдвига, добавляется в кодирующую последовательность, становясь очередным ее битом. Затем эта последовательность выдается в линию, где с помощью методов физического кодирования передается к узлу-получателю, на входе которого эта последовательность дескрэмблируется на основе обратного отношения.

Например, скрэмблер может реализовывать следующее соотношение:

где Bi — двоичная цифра результирующего кода, полученная на i-м такте работы скрэмблера, A_i — двоичная цифра исходного кода, поступающая на i-м такте на вход скрэмблера, B_i-3 и B_i-5 — двоичные цифры результирующего кода, полученные на предыдущих тактах работы скрэмблера, соответственно на 3 и на 5 тактов ранее текущего такта, ⊕ — операция исключающего ИЛИ (сложение по модулю 2).

Теперь давайте, определим закодированную последовательность, например, для такой исходной последовательности 110110000001.

Скрэмблер, определенный выше даст следующий результирующий код:

B₁=А₁=1 (первые три цифры результирующего кода будут совпадать с исходным, так как еще нет нужных предыдущих цифр)

Таким образом, на выходе скрэмблера появится последовательность 110001101111. В которой нет последовательности из шести нулей, п рисутствовавшей в исходном коде.

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

Существуют другие различные алгоритмы скрэмблирования, они отличаются количеством слагаемых, дающих цифру результирующего кода, и сдвигом между слагаемыми.

Главная проблема кодирования на основе скремблеров — синхронизация передающего (кодирующего) и принимающего (декодирующего) устройств. При пропуске или ошибочном вставлении хотя бы одного бита вся передаваемая информация необратимо теряется. Поэтому, в системах кодирования на основе скремблеров очень большое внимание уделяется методам синхронизации.

На практике для этих целей обычно применяется комбинация двух методов:

а) добавление в поток информации синхронизирующих битов, заранее известных приемной стороне, что позволяет ей при ненахождении такого бита активно начать поиск синхронизации с отправителем,

б) использование высокоточных генераторов временных импульсов, что позволяет в моменты потери синхронизации производить декодирование принимаемых битов информации «по памяти» без синхронизации.

Существуют и более простые методы борьбы с последовательностями единиц, также относимые к классу скрэмблирования.

Для улучшения кода ^ Bipolar AMI используются два метода, основанные на искусственном искажении последовательности нулей запрещенными символами.

Рис. 3 Коды B8ZS и HDB3

На этом рисунке показано использование метода ^ B8ZS (Bipolar with 8-Zeros Substitution) и метода HDB3 (High-Density Bipolar 3-Zeros) для корректировки кода AMI. Исходный код состоит из двух длинных последовательностей нулей (8- в первом случае и 5 во втором).

Код B8ZS исправляет только последовательности, состоящие из 8 нулей. Для этого он после первых трех нулей вместо оставшихся пяти нулей вставляет пять цифр: V-1*-0-V-1*. V здесь обозначает сигнал единицы, запрещенной для данного такта полярности, то есть сигнал, не изменяющий полярность предыдущей единицы, 1* — сигнал единицы корректной полярности, а знак звездочки отмечает тот факт, что в исходном коде в этом такте была не единица, а ноль. В результате на 8 тактах приемник наблюдает 2 искажения — очень маловероятно, что это случилось из-за шума на линии или других сбоев передачи. Поэтому приемник считает такие нарушения кодировкой 8 последовательных нулей и после приема заменяет их на исходные 8 нулей.

Код B8ZS построен так, что его постоянная составляющая равна нулю при любых последовательностях двоичных цифр.

Код HDB3 исправляет любые 4 подряд идущих нуля в исходной последовательности. Правила формирования кода HDB3 более сложные, чем кода B8ZS. Каждые четыре нуля заменяются четырьмя сигналами, в которых имеется один сигнал V. Для подавления постоянной составляющей полярность сигнала V чередуется при последовательных заменах.

Кроме того, для замены используются два образца четырехтактовых кодов. Если перед заменой исходный код содержал нечетное число единиц, то используется последовательность 000V, а если число единиц было четным — последовательность 1*00V.

Таким образом, применение логическое кодирование совместно с потенциальным кодированием дает следующие преимущества:

Улучшенные потенциальные коды обладают достаточно узкой полосой пропускания для любых последовательностей единиц и нулей, которые встречаются в передаваемых данных. В результате коды, полученные из потенциального путем логического кодирования, обладают более узким спектром, чем манчестерский, даже при повышенной тактовой частоте.

Линейные блочные коды

При передаче информации по каналам связи возможны ошибки вследствие помех и искажений сигналов. Для обнаружения и исправления возникающих ошибок используются помехоустойчивые коды. Упрощенная схема системы передачи информации при помехоустойчивом кодировании показана на рис. 4

Кодер служит для преобразования поступающей от источника сообщений последовательности из k информационных символов в последовательность из n cимволов кодовых комбинаций (или кодовых слов). Совокупность кодовых слов образует код.

Множество символов, из которых составляется кодовое слово, называется алфавитом кода, а число различных символов в алфавите – основанием кода. В дальнейшем вследствие их простоты и наибольшего распространения рассматриваются главным образом двоичные коды, алфавит которых содержит два символа: 0 и 1.

Рис. 4 Система передачи дискретных сообщений

Правило, по которому информационной последовательности сопоставляется кодовое слово, называется правилом кодирования. Если при кодировании каждый раз формируется блок А из k информационных символов, превращаемый затем в n-символьную кодовую комбинацию S, то код называется блочным. При другом способе кодирования информационная последовательность на блоки не разбивается, и код называется непрерывным.

С математической точки зрения кодер осуществляет отображение множества из 2 k элементов (двоичных информационных последовательностей) в множество, состоящее из 2 n элементов (двоичных последовательностей длины n). Для практики интересны такие отображения, в результате которых получаются коды, обладающие способностью исправлять часть ошибок и допускающие простую техническую реализацию кодирующих и декодирующих устройств.

Дискретный канал связи – это совокупность технических средств вместе со средой распространения радиосигналов, включенных между кодером и декодером для передачи сигналов, принимающих конечное число разных видов. Для описания реальных каналов предложено много математических моделей, с разной степенью детализации отражающих реальные процессы. Ограничимся рассмотрением простейшей модели двоичного канала, входные и выходные сигналы которого могут принимать значения 0 и 1.

Наиболее распространено предположение о действии в канале аддитивной помехи. Пусть S=(s₁,s₂. s_n) и Y=(y₁,y₂. y_n) соответственно входная и выходная последовательности двоичных символов. Помехой или вектором ошибки называется последовательность из n символов E=(e₁,e₂. e_n), которую надо поразрядно сложить с переданной последовательностью, чтобы получить принятую:

Таким образом, компонента вектора ошибки e_i=0 указывает на то, что 2-й символ принят правильно (y_i=s_i), а компонента e_i=1 указывает на ошибку при приеме (y_i≠s_i).Поэтому важной характеристикой вектора ошибки является число q ненулевых компонентов, которое называется весом или кратностью ошибки. Кратность ошибки – дискретная случайная величина, принимающая целочисленные значения от 0 до n.

Классификация двоичных каналов ведется по виду распределения случайного вектора E. Основные результаты теории кодирования получены в предположении, что вероятность ошибки в одном символе не зависит ни от его номера в последовательности, ни от его значения. Такой канал называется стационарным и симметричным. В этом канале передаваемые символы искажаются с одинаковой вероятностью P, т.е. P(e_i=1)=P, i=1,2. n.

Для симметричного стационарного канала распределение вероятностей векторов ошибки кратности q является биноминальным:

которая показывает, что при P j является убывающей функцией q, т.е. в симметричном стационарном канале более вероятны ошибки меньшей кратности. Этот важный факт используется при построении помехоустойчивых кодов, т.к. позволяет обосновать тактику обнаружения и исправления в первую очередь ошибок малой кратности. Конечно, для других моделей канала такая тактика может и не быть оптимальной.

Декодирующее устройство (декодер) предназначено оценить по принятой последовательности Y=(y₁,y₂. y_n) значения информационных символов A ‘ =(a ‘ ₁,a ‘ ₂. a ‘ _k,). Из-за действия помех возможны неправильные решения. Процедура декодирования включает решение двух задач: оценивание переданного кодового слова и формирование оценок информационных символов.

Вторая задача решается относительно просто. При наиболее часто используемых систематических кодах, кодовые слова которых содержат информационные символы на известных позициях, все сводится к простому их стробированию. Очевидно также, что расположение информационных символов внутри кодового слова не имеет существенного значения. Удобно считать, что они занимают первые k позиций кодового слова.

Наибольшую трудность представляет первая задача декодирования. При равновероятных информационных последовательностях ее оптимальное решение дает метод максимального правдоподобия. Функция правдоподобия как вероятность получения данного вектора Y при передаче кодовых слов S_i, i=1,2. 2 k на основании Y=S+E определяется вероятностями появления векторов ошибок:

Очевидно, вероятность P(Y/S_i) максимальна при минимальном q_i. На основании принципа максимального правдоподобия оценкой S ‘ является кодовое слово, искажение которого для превращения его в принятое слово Y имеет минимальный вес, т. е. в симметричном канале является наиболее вероятным (НВ):

Если несколько векторов ошибок E_i имеют равные минимальные веса, то наивероятнейшая ошибка E_HB определяется случайным выбором среди них.

В качестве расстояния между двумя кодовыми комбинациями принимают так называемое расстояние Хэмминга, которое численно равно количеству символов, в которых одна комбинация отлична от другой, т.е. весу (числу ненулевых компонентов) разностного вектора. Расстояние Хэмминга между принятой последовательностью Y и всеми возможными кодовыми словами 5, есть функция весов векторов ошибок E_i:

Поэтому декодирование по минимуму расстояния, когда в качестве оценки берется слово, ближайшее к принятой последовательности, является декодированием по максимуму правдоподобия.

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

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

Широко распространены линейные коды, называемые так потому, что их кодовые слова образуют линейное подпространство над конечным полем. Для двоичных кодов естественно использовать поле характеристики p=2. Принадлежность принятой комбинации Y известному подпространству является тем признаком, по которому выносится решение об отсутствии ошибок (E_HB=0).

Так как по данному коду все пространство последовательностей длины n разбивается на смежные классы, то для каждого смежного класса можно заранее определить вектор ошибки минимального веса, называемый лидером смежного класса. Тогда задача декодера состоит в определении номера смежного класса, которому принадлежит Y, и формировании лидера этого класса.

источники:

http://habr.com/ru/post/518120/

http://garick58.narod2.ru/content/KR/io.html

Источник

Всем привет! До этого дня мы использовали чистые массивы. Чистые — это значит простые массивы, не имеющие у себя в багаже различных функций. В этом уроке мы пройдем нечистые массивы — векторы.

Быстрый переход по статье:

Вектор векторов (массив векторов)
Функции векторов

Что такое вектор (vector)

Вектор — это структура данных, которая уже является моделью динамического массива.

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

Как создать вектор (vector) в C++

Сначала для создания вектора нам понадобится подключить библиотеку — <vector>, в ней хранится шаблон вектора.

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

Далее, чтобы объявить вектор, нужно пользоваться конструкцией ниже:

vector < тип данных > <имя вектора>;

Вначале пишем слово vector.
Далее в угольных скобках указываем тип, которым будем заполнять ячейки.
И в самом конце указываем имя вектора.

Вот пример:

В примере выше мы создали вектор строк.

Кстати, заполнить вектор можно еще при инициализации (другие способы мы пройдем позже — в методах вектора). Делается это также просто, как и в массивах. Вот так:

vector <int> ivector = {<элемент [0]>, <[1]>, <[2]>};

После имени вектора ставим знак равенства и скобки, в которых через пробел указываем значение элементов.

Такой способ инициализации можно использовать только в C++!

Так, чтобы заполнить вектор строками, нам нужно использовать кавычки — "строка".

Второй способ обратиться к ячейке

Мы знаем, что в векторе для обращения к ячейке используются индексы. Обычно мы их используем совместно с квадратными скобками [].

Но в C++ есть еще один способ это сделать благодаря функции — at(). В скобках мы должны указать индекс той ячейки, к которой нужно обратиться.

Вот как она работает на практике:

vector <int> ivector = {1, 2, 3};

ivector.at(1) = 5; // изменили значение второго элемента

cout << ivector.at(1); // вывели его на экран

Давайте запустим эту программу:

Process returned 0 (0x0) execution time : 0.010 s

Press any key to continue.

Как указать количество ячеек для вектора

Указывать размер вектора можно по-разному. Можно это сделать еще при его инициализации, а можно хоть в самом конце программы. Вот, например, способ указать длину вектора на старте:

vector <int> vector_first(5);

Так в круглых скобках () после имени вектора указываем первоначальную длину. А вот второй способ:

vector <int> vector_second; // создали вектор

vector_second.reserve(5); // указали число ячеек

Первая строчка нам уже знакома. А вот во второй присутствует незнакомое слово — reserve, это функция, с помощью которой мы говорим компилятору, какое количество ячеек нам нужно использовать.

Вы можете задать логичный вопрос:»А в чем разница?». Давайте создадим два вектора и по-разному укажем их количество ячеек.

#include <iostream>

#include <vector> // подключили библиотеку

using namespace std;

int main() {

setlocale(0, «»);

vector <int> vector_first(3); // объявили

// два

vector <int> vector_second; // вектора

vector_second.reserve(3);

cout << «Значения первого вектора (с помощью скобок): «;

for (int i = 0; i < 3; i++) {

cout << vector_first[i] << » «;

}

cout << «Значения второго вектора (с помощью reserve): « << endl;

for (int i = 0; i < 3; i++) {

cout << vector_second[i] << » «;

}

system(«pause»);

return 0;

}

Запускаем программу:

Значения первого вектора (с помощью скобок): 0 0 0

Значения второго вектора (с помощью reserve): 17 0 0

Process returned 0 (0x0) execution time : 0.010 s

Press any key to continue.

Как видим, в первом случае мы вывели три нуля, а во втором: 17, 0, 0.

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

При объявлении чего-либо (массива, вектора, переменной и т.д) мы выделяем определенное количество ячеек памяти, в которых уже хранится ненужный для ПК мусор. В нашем случае этим мусором являются числа.

Поэтому, когда мы вывели второй вектор, в нем уже находились какие-то рандомные числа — 17, 0, 0. Обычно они намного больше. Можете кстати попробовать создать переменную и вывести ее значение.

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

Как сравнить два вектора

Если в середине программы нам понадобиться сравнить два массива, мы, конечно, используем цикл for и поочередно проверим все элементы.

Вектор снова на шаг впереди! Чтобы нам сравнить два вектора, потребуется применить всего лишь оператор ветвления if.

if (vec_first == vec_second) { // сравнили!

cout << «Они равны!»;

}

else {

cout << «Они не равны»;

}

Конечно, компилятор все равно прогонит эти два вектора по циклу, проверяя ячейки. Но посмотрите на код ниже и скажите насколько программа стала меньше, разве это не хорошо?

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

bool flag = true;

if (vec_first.size() == vec_second.size()) {

for (int i = 0; i < vec_first.size(); i++) {

if (vec_first[i] != vec_second[i]) {

cout << «Они не равны!»;

flag = false;

break; // выходим из цикла

}

else {

flag = false;

cout << «Они не равны!»;

}

if (flag) {

cout << «Они равны!»;

}

Сначала мы создали булеву переменную flag равную true. У нее задача такая:
- Если в условии (строки 5 — 10) она станет равна false — то значит эти векторы не равны и условие (строки 14 — 16) не будет выполняться.
- Если же она после цикла (строки 3 — 12) останется равна true — то в условии (строки 14 — 16) мы сообщим пользователю, что они равны.
В условии (строка 3) проверяем размеры двух векторов на равенство.
И если условие (строки 5 — 10) будет равно true — то мы сообщим пользователю, что эти два вектора не равны.

Как создать вектор векторов

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

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

vector < vector < тип данных > >;

Как можно увидеть, нам пришлось только добавить слова vector и еще его <тип>.

А чтобы указать количества векторов в векторе нам потребуется — метод resize().

vector < vector <int> > vec;

vec.resize(10); // десять векторов

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

vec.push_back(vector <int>());

В аргументах функции push_back() находится — имя контейнера который мы хотим добавить. В нашем случае — vector.
А дальше идет тип контейнера — <тип>.
И все заканчивается отрывающей и закрывающей скобкой ().

Для двумерного вектора тоже можно указать значения еще при инициализации:

vector < vector <int> > ivector = {{1, 4, 7},

{2, 5, 8},

{3, 6, 9}};

{1, 4, 7} — это значения элементов первого массива (первого слоя). Такие блоки значений {1, 4, 7} должны разделяться запятыми.

Методы для векторов:

Сейчас мы разберем некоторые методы, которые часто используются вместе с векторами. Метод — это функция, которая относится к определенному STL контейнеру.

В нашем случае этим STL контейнером является вектор. Если вы дальше собираетесь оперировать векторами — лучше все перечисленные функции запомнить.

1) size() и empty()

Если нам требуется узнать длину вектора, понадобится функция — size(). Эта функция практически всегда используется вместе с циклом for.

for (int i = 0; i < ivector.size(); i++) {

// …

}

Также, если нам требуется узнать пуст ли стек, мы можем использовать функцию — empty().

При отсутствии в ячейках какого-либо значения это функция возвратит — true.
В противном случае результатом будет — false.

Вот пример с ее использованием:

if (ivector.empty()) {

// …

}

2) push_back() и pop_back()

Как мы сказали выше, у векторов имеются методы, которые помогают оптимизировать и улучшить жизнь программистов. Одни из самых используемых функций это — push_back() и pop_back().

С помощью функции push_back() мы можем добавить ячейку в конец вектора.
А функция pop_back() все делает наоборот — удаляет одну ячейку в конце вектора.

Использование функции push_back() без указания значения ячейки — невозможно. Так или иначе, придется это значение указать!

Давайте разберемся, как работают эти функции на практике:

#include <iostream>

#include <vector>

using namespace std;

int main() {

setlocale(0, «»);

vector <string> vec_string;

vec_string.push_back(«апельсин»); // добавляем

vec_string.push_back(«груша»); // четыре

vec_string.push_back(«яблока»); // элемента

vec_string.push_back(«вишня»); // в конец вектора

for (int i = 0; i < vec_string.size(); i++) {

cout << vec_string[i] << » «;

}

cout << endl;

vec_string.pop_back(); // удаляем элемент

for (int i = 0; i < vec_string.size(); i++) {

cout << vec_string[i] << » «;

}

system(«pause»);

return 0;

}

Вот что будет при запуске:

апельсин груша яблоко вишня

апельсин груша яблоко

Process returned 0 (0x0) execution time : 0.010 s

Press any key to continue.

Кстати, можно сделать вот так:

vec_string.push_back(«апельсин»);

vec_string.push_back(«груша»);

string val = vec_string.pop_back(); // присвоили значение удаляемой ячейке

cout << val;

Мы сохранили значение удаляемой ячейки в переменную — val.

Давайте запустим эту программу:

груша

Process returned 0 (0x0) execution time : 0.010 s

Press any key to continue.

3) insert()

Выше мы вам показали функцию push_back(), но то же самое можно сделать, используя функцию — insert(). Только с помощью нее еще можно добавлять элементы в начало вектора.

Эта функция имеет такую конструкцию:

<имя вектора>.insert(<итератор>, <значение>);

<итератор> — про него мы поговорим в другом уроке. Это тема которая требует подробного изучения. Сейчас вам нужно знать только о том, что функция:

begin() — указывает на начала вектора.
end() — указывает на конец вектора.

<значение> — сюда мы должны вписать значение добавляемой ячейки.

Если вы в <итератор> указали именно итератор, а не функции begin() и end(), то элемент будет добавлен именно после той ячейки, на которую указывает итератор.

Давайте посмотрим, как insert() работает на примере:

int main() {

setlocale(0, «»);

vector vec_string(2);

vec_string[0] = 2; // заполнили две

vec_string[1] = 3; // ячейки

for (int i = 0; i < vec_string.size(); i++) {

cout << vec_string[i] << » «;

}

cout << endl;

vec_string.insert(vec_string.begin(), 1); // добавили элемент в начало

for (int i = 0; i < vec_string.size(); i++) {

cout << vec_string[i] << » «;

}

cout << endl;

vec_string.insert(vec_string.end(), 4); // добавили элемент в конец

for (int i = 0; i < vec_string.size(); i++) {

cout << vec_string[i] << » «;

}

system(«pause»);

return 0;

}

При запуске программы, мы увидим это:

2 3

1 2 3

1 2 3 4

Process returned 0 (0x0) execution time : 0.010 s

Press any key to continue.

На иллюстрациях ниже показано, как vec_string изменялся в программе:

Вы должны знать! Если вы хотите, чтобы ваша программа работала как можно быстрее — вам нужно добавлять элементы именно в конец.

Так как при добавлении элемента в начало, с помощью той же функции insert(), в векторе происходит смещение всех ячеек вправо. К тому же, смещение идет по одной ячейке, а это у нас линейный поиск, который работает, мягко сказать, не быстро. При этом, чем больше у нас будет вектор, тем медленнее будет происходить добавление элементов!

4) front() и back()

Для того, чтобы мы могли просматривать первую и последнюю ячейки у нас имеются функции: front() и back().

int front_num = ivector.front();

int back_num = ivector.back();

Упражнение

Чтобы как следует запомнить этот материал, создайте вектор и поочередно примените все выше сказанные функции.

Тест на тему «Векторы». Проверь себя!

Пожалуйста, подождите пока страница загрузится полностью.
Если эта надпись не исчезает долгое время, попробуйте обновить страницу. Этот тест использует javascript. Пожалуйста, влкючите javascript в вашем браузере.

If loading fails, click here to try again

Если ты полностью разобрался в данном материале, то попробуй пройти несложный тест, который сможет выявить твои слабые стороны.

На этом все! Надеемся, вы узнали для себя что-то новое! Если хотите задать вопрос, то пишите в комментарии. Удачи!

Источник

Содержание

1 Специальная алгебра многомерных векторов^[1]
- 1.1 Специальное умножение
- 1.2 Деление ^[3]
- 1.3 Возведение в целую степень
- 1.4 Покомпонентное умножение
- 1.5 Взаимосвязь с традиционными операциями
  - 1.5.1 Скалярное умножение
  - 1.5.2 Векторное умножение
  - 1.5.3 Поворот вектора
  - 1.5.4 Центроафинное преобразование
2 Позиционные коды векторов
- 2.1 Алгебраическое сложение
- 2.2 Умножение
3 Примечания

Специальная алгебра многомерных векторов^[1]

Специальное умножение

В этой алгебре умножение определяется по аналогии с умножением комплексных чисел следующим образом. Таблица умножения комплексных чисел имеет вид

	1	i
1	1	i
i	i	-1

где i — мнимая единица. Таблица умножения трехмерных векторов имеет вид

	i	j	k
i	i	j	k
j	j	k	-i
k	k	-i	-j

где i, j, k — орты. Таблица умножения четырехмерных векторов имеет вид

	i	j	k	m
i	i	j	k	m
j	j	k	m	-i
k	k	m	-i	-j
m	m	-i	-j	-k

где i, j, k, m — орты, и т.д. Этим вполне определяется умножение векторов ^[2]. Однако, это умножение не имеет ничего общего с векторным или скалярным умножением векторов и, в отличие от них, обозначается в дальнейшем символом и называется специальным умножением. Умножение, определенное такими таблицами для ортов, является ассоциативным и коммутативным. Следовательно, специальное умножение любых векторов векторного пространства также будет ассоциативным и коммутативным ^[2]. Таким образом, множество всех n-мерных векторов составляет кольцо относительно операций обычного сложения и специального умножения. Иными словами, указанные таблицы определяют в n-мерном пространстве ассоциативную и коммутативную алгебру без деления ^[2].
Вектор не изменяется при умножении на орт .

Деление ^[3]

Деление в этой алгебре определяется как операция, обратная умножению. Однако, если деление чисел недопустимо только при делителе, равном нулю, то в этой алгебре деление недопустимо при множестве значений делителя. Это множество для, например, трехмерных векторов определяется следующим образом. Если вектор делителя

то множество недопустимых значений этого делителя определяется условием

Возведение в целую степень

Вектор в нулевой степени равен .
Возведение вектора в целую степень n > 0 определяется как многократное умножение. Например, для ортов трехмерных векторов

mathbf j^1 = mathbf j, mathbf j^2 = mathbf k, mathbf j^3 = -mathbf i, mathbf j^4 = -mathbf j, mathbf j^5 = -mathbf k, mathbf j^6 = mathbf i

mathbf k^1 = mathbf k, mathbf k^2 = -mathbf j, mathbf k^3 = mathbf i

Для трехмерных векторов выполняется условие . Следовательно, $frac{mathbf i}{mathbf k} = -mathbf j$ , $frac{mathbf i}{mathbf j} = -mathbf k$ и $mathbf j^{-1}= -mathbf k$ , $mathbf j^{-1}= -mathbf k$ . Таким образом, орт в степени (-1) определяется непосредственно из таблицы умножения.
Возведение орта в целую степень n < 0 определяется как многократное умножение известного вектора — орта в степени (-1).

Покомпонентное умножение

Этот термин используется для наименования операции (здесь и далее рассматриваются трехмерные векторы) специального умножения вектора

mathbf A=x_1 mathbf i + y_1 mathbf j+ z_1 mathbf k

на упорядоченную тройку векторов . Покомпонентное умножение обозначается как

mathbf Z=mathbf A circledast (mathbf B, mathbf C, mathbf D)

и состоит в вычислении по формуле

mathbf Z = x_1 mathbf i circledast mathbf B + y_1 mathbf j circledast mathbf C + z_1 mathbf k circledast mathbf D

Если

mathbf Z=x mathbf i + y mathbf j+ z mathbf k, mathbf B=x_2 mathbf i + y_2 mathbf j+ z_2 mathbf k, mathbf C=x_3 mathbf i + y_3 mathbf j+ z_3 mathbf k, mathbf D=x_4 mathbf i + y_4 mathbf j+ z_4 mathbf k,

то

x=x_1x_2-y_1z_3-z_1y_4, y=x_1y_2-y_1x_3-z_1z_4, z=x_1z_2+y_1y_2+z_1x_4.

Взаимосвязь с традиционными операциями

Применяя последнюю формулу, можно выразить традиционные операции с векторами через покомпонентное умножение.

Скалярное умножение

mathbf Z = mathbf A mathbf B=mathbf A circledast (x_2 mathbf i, -y_2 mathbf k, -z_2 mathbf j)

где вектор имеет орт .

Векторное умножение

mathbf Z = mathbf A times mathbf B=mathbf A circledast ((-z_2 mathbf j+y_2 mathbf j), (-x_2 mathbf j-z_2 mathbf k), (y_2 mathbf j -x_2 mathbf k))

Поворот вектора

Рассмотрим прямую с ортом

mathbf r_o =mathbf i cos alpha + mathbf j cos beta + mathbf k cos gamma

проходящую через начало координат. Пусть вокруг этой прямой по окружности некоторого радиуса вращается точка, причем ее радиус-вектор переходит из положения в положение . Если, кроме того, вращение производитсмя против часовой стрелки (при наблюдении с конца вектора ) и угол поворота , то

mathbf Z = mathbf A cos varphi +(mathbf r_o times mathbf A ) sin varphi -mathbf r_o (mathbf r_o mathbf A)(1- cos varphi )

Эта формула преобразуется к виду , где кординаты векторов выражаются через (α,β,γ,φ)^[1]. .

Центроафинное преобразование

В трехмерном пространстве центроафинное преобразование, при котором точка с вектором переходит в точку с вектором , описывается формулой

mathbf Z=(mathbf B mathbf A) mathbf i + (mathbf C mathbf A) mathbf j +(mathbf D mathbf A) mathbf k

где указанные выше координаты векторов являются параметрами этого преобразования. Рассматривая формулу скалярного умножения, находим, что центроафинное преобразовние эквивалентно покомпонентному умножению

mathbf Z=mathbf A circledast (mathbf B^prime , mathbf C^prime , mathbf D^prime )

где

mathbf B^prime =x_2 mathbf i - y_2 mathbf j- z_2 mathbf k, mathbf C^prime =x_3 mathbf i - y_3 mathbf j- z_3 mathbf k, mathbf D^prime =x_4 mathbf i - y_4 mathbf j-z_4 mathbf k

Позиционные коды векторов

Метод позиционного кодирования основан на представлении кодируемого объекта в виде суммы

$mathbf A=sum_{k} alpha_k rho^{k}$

где k — целое число, alpha_k — число, принимающее значения из определенного множества, rho — основание системы кодирования. В частности, существует система кодирования комплексных чисел по основанию , где j – мнимая единица, и $B_R = { 0, 1, 2,dots, R-1 }$ , а R — целое положительное число (например, R=2) ^[4].
По аналогии с этим в ^[1] предложена позиционная система кодирования векторов по основанию , где – второй орт в таблице специального умножения векторов, n — размерность векторов, . В частности, существует двоичная система кодирования векторов, в которой R=2 и $B_R = { 0, 1}$ . Необходимое для этого возведение орта в целую (положительную или отрицательную) степень рассмотрено выше.

Позиционный код вектора

mathbf A=x mathbf i + y mathbf j+ z mathbf k

представляет собой запись цифр α, имеющую вид

$mathbf A = alpha_{0} alpha_{1} dots alpha_k dots alpha_{n}$

Этот же вектор можно рассматривать как сумму

mathbf A=X mathbf rho^0 +Y mathbf rho^1 + Z mathbf rho^2

где

$X=x sqrt [3] {R^{0}}; Y=y sqrt [3] {R^{-1}}; Z=z sqrt [3] {R^{-2}}$

При этом код вектора можно рассматривать как композицию трех кодов следующего вида

$begin{pmatrix} mathbf A= & alpha_{0} & alpha_{1} & alpha_{2} & alpha_{3} & alpha_{4} & alpha_{5} & alpha_{5} & cdots \ X = & beta_{0} & & & beta_{1} & & & beta_{2} & cdots \ Y= & & gamma_{0} & & & gamma_{1} & & & cdots \ Z = & & & delta_{0} & & & delta_{1} & & cdots \ end{pmatrix}$

где

$beta_{k}=alpha_{3k}; gamma_{k}=alpha_{3k+1}; delta_{k}=alpha_{3k+2}$

Здесь коды чисел X, Y, Z являются двоичными кодами чисел по основанию (-2).

Алгебраическое сложение

Алгебраическое сложение кодов векторов состоит из трех сложений пар компонент X, Y, Z этих векторов. Эти сложения могут выполнятся параллельно.

Умножение

Специальное умножение кодов векторов состоит, как обычно для позиционных кодов, из циклов «сдиг, как умножение множимого на разряд множителя» — «сложение с частичной суммой». Покомпонентное умножение также состоит из таких циклов, но в каждом цикле значение множимого зависит от номера разряда множителя. Точнее, при покомпонентном умножении

вектор с кодом

$mathbf A = alpha_{0} alpha_{1} dots alpha_k dots alpha_{n}$

рассматривается как множитель, а множимое М определяется в зависимости от номера разряда $alpha_{3k+t}$ по следующему правилу:

mathbf M = mathbf B, if t=0; mathbf M = mathbf C, if t=1; mathbf M = mathbf D, if t=2

Примечания

↑ ¹ ² ³ Хмельник С. И. Алгебра многомерных векторов и кодирование пространственных фигур // Автоматика и вычислительная техника, АН ЛССР. — 1971. — Т. 1.
↑ ¹ ² ³ Курош А.Г. Курс высшей алгебры — «Наука». — Mосква, 1965.
↑ Хмельник С. И. Кодирование комплексных чисел и векторов — Mathematics in Computers. — Израиль, 2004. — ISBN 978-0-557-74692-7.
↑ Knuth D. E. (1960). «An Imaginary Number System». Communication of the ACM 3 (4): 245—247. DOI:10.1145/367177.367233.

Источник

Цепной код (англ. chain code) — это такое упорядочивание двоичных векторов одной длины, каждый следующий столбец которого (можно рассматривать как таблицу из элементов) получается из предыдущего циклическим сдвигом вверх.

Цепной код позволяет исправить все одиночные ошибки при условии, что между любыми двумя ошибочно принятыми имеется по крайней мере три правильно принятых сигнала. Часто используется при передаче данных: видео, мобильной связи.

Содержание

1 Алгоритм получения цепного кода для двоичных векторов
2 Псевдокод алгоритма
3 Доказательство корректности
- 3.1 Доказательство первого пункта
- 3.2 Доказательство второго пункта
4 См. также
5 Источники информации

Алгоритм получения цепного кода для двоичных векторов

В качестве первого вектора берём вектор из нулей. Чтобы получить следующий вектор, берём последний добавленный вектор, пусть . Если в коде до этого не встречался вектор , то добавляем его. Иначе проверяем на наличие в коде вектора . Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена.

При таком построении видно, что элементы таблицы равны элементам

Псевдокод алгоритма

— последний добавленный битовый вектор
— список битовых векторов

string[] chain_code(int n):
  current = '0' * n
  result = [current]
  while true
    prefix = current[2..n]
    if prefix + '1' not in result
      current = prefix + '1'
    else prefix + '0' not in result
      current = prefix + '0'
    else
      break
    result.append(current)
  return result

Доказательство корректности

Разобьем доказательство на две части:

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

Доказательство первого пункта

Покажем, что единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — сгенерирован вектор из нулей. Рассмотрим первое такое противоречие: последним добавлен вектор , вектора и уже присутствуют в коде.

Далее есть две возможных ситуации: вектор состоит из нулей или предшествовал другому вектору в коде. В первой ситуации алгоритм завершает работу.

Во второй ситуации каждому из векторов и предшествовали некоторые вектора в коде, пусть и . Так как мы рассматриваем первое противоречие, то .

Но в таком случае вектор совпадает с одним из векторов или . Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, следовательно, реализуется только первый вариант ситуации.

Доказательство второго пункта

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

Пусть . Докажем, что . От противного, пусть вектор был сгенерирован. Тогда ему предшествовал вектор . Так как по предположению , то в коде может быть только один вектор такого вида, а в таком случае алгоритм может сгенерировать только .

Значит, если множество непусто, то оно содержит вектор из нулей. Но это противоречит тому, что вектор из нулей был сгенерирован. Следовательно, это предположение не верно и все вектора с нулём в последней позиции были сгенерированы.

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

См. также

Коды Грея
Коды антигрея
Коды Грея для перестановок

Источники информации

Wikipedia — Chain code

Источник

Контейнер std::vector

Обращение к элементам

Итерация по индексам

Добавление и удаление элементов

Резерв памяти

Многомерные векторы

Сортировка вектора

Строки

Примеры задач с решениями

Код Рида-Соломона

Описание РС-кода и его характеристик

Кодирование сообщений РС-кодом

Декодирование кодов Рида-Соломона

Обнаружение искажений

Проверочная матрица РС – кода

Определение коэффициентов синдромного многочлена

Решение системы линейных уравнений

Формальная производная многочлена в конечном поле

Метод решения ключевого уравнения

Архитектура построения программного комплекса

Заключение

Найти кодовые векторы по информационным блокам

Метричное представление n,k-кодов

Циклические коды

Логический код 4В/5В

Скрэмблирование

Линейные блочные коды

Как создать вектор (vector) в C++

Второй способ обратиться к ячейке

Как указать количество ячеек для вектора

Как создать вектор векторов

<img decoding="async" onError="javascript: wp_broken_images = window.wp_broken_images || function(){}; wp_broken_images(this);" loading="lazy" width="40" height="40" src="https://codelessons.ru/wp-content/uploads/lampa-1.jpg.pagespeed.ce.7gsyMJ9_MD.jpg" alt /> Методы для векторов:

1) size() и empty()

2) push_back() и pop_back()

3) insert()

4) front() и back()

Тест на тему «Векторы». Проверь себя!

Содержание

Специальная алгебра многомерных векторов[1]

Специальное умножение

Деление [3]

Возведение в целую степень

Покомпонентное умножение

Взаимосвязь с традиционными операциями

Скалярное умножение

Векторное умножение

Поворот вектора

Центроафинное преобразование

Позиционные коды векторов

Алгебраическое сложение

Умножение

Примечания

Содержание

Алгоритм получения цепного кода для двоичных векторов

Псевдокод алгоритма

Доказательство корректности

Доказательство первого пункта

Доказательство второго пункта

См. также

Источники информации

Контейнер `std::vector`

Методы для векторов:

Специальная алгебра многомерных векторов^[1]

Деление ^[3]