РАЗДЕЛ 2
Системы счисления с постоянным числом единиц
Развитие средств вычислительной техники сопровождается ростом производительности вычислительных машин, усложнением их конструкции и расширением области применения. Это обуславливает постоянный интерес к проблеме повышения надежности работы. Решение данной задачи практически всегда предполагает введение избыточности. Среди многообразия форм введения избыточности все больший вес приобретают методы помехоустойчивого кодирования, позволяющие обнаруживать ошибки при передаче, хранении и обработке информации [77].
Традиционно "неудобными" для помехоустойчивого кодирования оставались узлы управления ЭВМ, обладающие нерегулярной структурой [77]. Для обнаружения и исправления ошибок в исполнительных устройствах были созданы специальные коды, которые принято называть арифметическими, потому что они предназначены для обнаружения ошибок при выполнении арифметических операций. Однако эти коды создавались в большей степени интуитивно. Поэтому большой интерес вызывает анализ методов синтеза кодов, корректирующих ошибки, и разработка методов синтеза арифметических кодов [78].
2.1. Оценка методов синтеза структурных кодов и систем счисления
В процессе создания или совершенствования устройств передачи, хранения или переработки информации формируются требования к кодам, которые контролируют или корректируют ошибки. На основе этих требований необходимо построить реальный код, то есть представить в явном виде список кодовых слов. В основе построения реальных кодов могут лежать различные методы их синтеза. Однако на практике при синтезе кодов для каналов цифровой связи, наибольшее распространение получили три основных метода [6].
1. Метод перебора.
Выписываются слова безизбыточного кода и из них выбираются слова, удовлетворяющие заданным требованиям. Сам перебор осуществляется как вручную, так и программно, в любом случае необходимо составить алгоритм перебора. Данный метод можно использовать для получения кодов сравнительно небольшой мощности.
2. Метод аналитического перебора.
По каким-либо соображениям выбирается модель кода, ограничивающая его мощность по сравнению с полным кодом. Затем с ограниченного списка слов путем перебора получаются слова с требуемыми свойствами. Данный метод применим при наличии модели, ограниченно описывающей множество кодовых слов.
3. Регулярный метод.
Суть метода заключается в построении кода на основе математической модели, однозначно задающей алгоритм построения. Этот метод применяется при наличии хорошо разработанной математической модели.
Перечисленные методы синтеза кодов предназначены для получения кодов, применяемых в цифровых каналах передачи информации и, следовательно, они недостаточно хорошо стыкуются с алгоритмами выполнения арифметических операций.
Для синтеза арифметических кодов в большей степени подходят методы синтеза структурных кодов [15]. Это структурно-матричный метод синтеза кодов, прямой и обратный алгоритмический методы синтеза.
Алгоритм прямого алгоритмического метода синтеза:
1. Выбор и обоснование исходной структурной формы.
2. Расчет мощности кодовой формы с помощью рекуррентной последовательности.
3. Определение мощности посредством базисной функции.
4. Построение базисной функции.
5. Построение кода в явном виде.
Алгоритм обратного алгоритмического метода синтеза:
1. Определение базисной функции.
2. Расчет параметров кода.
3. Построение кода в явном виде.
Алгоритм структурно-матричного метода синтеза:
1. Строится Z начальных матриц размера M(Sj) * Sj.
2. Матрица размера М(n) * n образуется из Z матриц размера М(n-Sj) * (n-Sj) следующим образом:
а) слева от каждой строки матрицы размером М(n-Sj)*(n-Sj) добавляются Sj символов, образующих j-ю строку группы;
б) в расширенной матрице вычеркиваются возможные строки, содержащие запрещенные структурные группы в местах стыка дополнительных Sj символов;
в) столбцы полученных матриц приписываются один под другим.
Однако и эти методы синтеза не получили широкого распространения на практике. Более широко для синтеза арифметических кодов можно использовать метод перебора для синтеза структурных кодов [79]. Структурный код строится последовательным выбором из безизбыточного двоичного кода комбинаций символов, удовлетворяющих требованиям структурной группы.
Алгоритм синтеза структурных кодов методом перебора:
1. Выбор и обоснование исходной структурной формы.
2. Определение структурной группы синтезированного кода по выбранной структуре
3. Синтез кода в явном виде на основе последовательной выборки из безизбыточного кода комбинаций символов, удовлетворяющих требованиям структурной группы.
4. Определение количественных и качественных характеристик кода.
Результаты исследования арифметических структурных кодов, приведенные в работах [80-84] позволяют определить алгоритм совмещенного метода практического синтеза, вобравший в себя особенности методов перебора и структурно-матричного метода синтеза кодов.
1. Выбор и обоснование исходной структурной формы.
2. По выбранной структуре определить структурную группу синтезируемого кода.
3. Синтез кода в явном виде на основе последовательной выборки из безизбыточного кода комбинаций символов, удовлетворяющих требованиям структурной группы до n=2h, где n-разрядность начальных значений кода, h-максимальная длина слова структурной группы.
4. Определение по структурной группе функции кода (функция кода определяет алгоритм структурно-матричного метода синтеза).
5. Полный синтез кода на основе функции кода структурно матричным методом синтеза.
Совмещенный метод практического синтеза обладает следующими преимуществами:
1. Упрощает алгоритм синтеза за счет исключения операций вычеркивания возможных строк, содержащих запрещенные структурные группы в местах стыка дополнительных слов.
2. Одноз