Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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





Регистры сдвига (сдвигающие регистры) являются одними из основных узлов аппаратуры передачи дискретных сообщений. Любой сдвигающий регистр, состоящий из n триггеров, есть запоминающее устройство, способное принимать 2 n различных состояний.

Если в регистр сдвига ввести обратные связи, каждая из которых формируется логической схемой, называемой схемой сложения по модулю два (или «ИСКЛЮЧАЮЩЕЕ ИЛИ»), то с помощью такого устройства можно построить генератор псевдослучайной последовательности или устройство деления одного многочлена на другой (кодирующие и декодирующие устройства).

Рассмотрим построение генератора псевдослучайной последовательности.

Случайной последовательностью называется последовательность из 1 и 0, в которой каждый элемент появляется в последовательности независимо от предыдущих символов. Случайные последовательности должны удовлетворять тестам на случайность:

уравновешенности, когда число 1 и 0 в последовательности равно;

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

вероятность появления каждого набора из m элементов для m<n (где n – длина последовательности) равна 2- m.

Случайная последовательность не имеет ни начала, ни конца. Получить ее можно, подбрасывая монетку и рассматривая, какая сторона монетки выпадет. Если выпал “орел”, то записывается единица, если “решка”, то записывается ноль. На практике такие последовательности получить нельзя. Поэтому используют ограниченные (конечные) последовательности, которые обладали бы некоторыми свойствами случайных последовательностей. Такие последовательности называются псевдослучайными последовательностями (ПСП).

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

 

 

Рис. 43. Генератор псевдослучайной последовательности

 

Таким образом, под воздействием каждого тактового импульса разряды регистра сдвига принимают определенные состояния, причем последовательность этих состояний зависит от способа включения обратной связи. Общее число таких различных состояний равно 2 n -1, следовательно, период ПСП равен 2 n -1. ПСП можно снимать с выхода любого разряда регистра, в частности с последнего. Любая выходная последовательность, имеющая такой период, называется линейной последовательностью максимальной длины.

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

F (x)= xn+ An- 1 xn- 1 +…+ A 2 x 2 + A 1 x+ 1.

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

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

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

Сопряженные многочлены вычисляют следующим образом:

в характеристическом многочлене производят замену переменных x=y- 1:

1/ yn + An -1/ yn -1+…+ A 2/ y 2+ A 1/ y +1;

вновь полученный многочлен умножают на yn:

(yn / yn) yn + An -1(yn / yn -1) +…+ A 2(yn / y 2) + A 1(yn / y) + yn =
=1+ An -1 y +…+ A 2 yn -2+ A 1 y + yn.

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

Для некоторых n неприводимые многочлены вычислены и сведены в таблицы. Некоторые из этих многочленов приведены в табл. 10.

 

 

Т а б л и ц а 10

Число разрядов n Многочлен Максимальная длина ПСП Номера разрядов, выходы которых подаются на сумматор по модулю 2
  x 2+ x +1   1, 2
  x 3+ x +1 x 3+ x 2+1   2, 3 1, 3
  x 4+ x +1 x 4+ x 3+1   3, 4 1, 4
  x 5+ x 2+1 x 5+ x 3+1   3, 5 2, 5
  x 6+ x +1 x 6+ x 5+1   5, 6 1, 6
  x 7+ x +1 x 7+ x 6+1   6, 7 1, 7
  x 8+ x 4+ x 3+ x 2+1 x 8+ x 6+ x 5+ x 4+1   4, 5, 6, 8 2, 3, 4, 8

 

Рассмотрим построение генератора ПСП при n =4. В таблице найдем характеристический многочлен степени 4 – g (x)= x 4+ x +1.

Заменим переменную и найдем сопряженный многочлен:

1/ y 4+1/ y +1, y 4(1/ y 4+1/ y +1)=1+ y 3+ y 4.

Следовательно, регистр сдвига имеет четыре разряда. Число сумматоров по модулю два, включаемых в обратную связь, равно 3-2=1. Номера разрядов, выходы которых подаются на входы сумматора по модулю два, равны 3 и 4. Схема генератора ПСП приведена на рис. 44.

 

Рис. 44. Генератор ПСП для n =4

 

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

Т а б л и ц а 11

Номер такта Q 1 Q 2 Q 3 Q 4
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         

 

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

В данном случае эта последовательность получена с выхода четвертого разряда регистра сдвига (пятый столбец табл. 11).







Дата добавления: 2015-08-27; просмотров: 550. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...


Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

Кишечный шов (Ламбера, Альберта, Шмидена, Матешука) Кишечный шов– это способ соединения кишечной стенки. В основе кишечного шва лежит принцип футлярного строения кишечной стенки...

Принципы резекции желудка по типу Бильрот 1, Бильрот 2; операция Гофмейстера-Финстерера. Гастрэктомия Резекция желудка – удаление части желудка: а) дистальная – удаляют 2/3 желудка б) проксимальная – удаляют 95% желудка. Показания...

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

Неисправности автосцепки, с которыми запрещается постановка вагонов в поезд. Причины саморасцепов ЗАПРЕЩАЕТСЯ: постановка в поезда и следование в них вагонов, у которых автосцепное устройство имеет хотя бы одну из следующих неисправностей: - трещину в корпусе автосцепки, излом деталей механизма...

Понятие метода в психологии. Классификация методов психологии и их характеристика Метод – это путь, способ познания, посредством которого познается предмет науки (С...

ЛЕКАРСТВЕННЫЕ ФОРМЫ ДЛЯ ИНЪЕКЦИЙ К лекарственным формам для инъекций относятся водные, спиртовые и масляные растворы, суспензии, эмульсии, ново­галеновые препараты, жидкие органопрепараты и жидкие экс­тракты, а также порошки и таблетки для имплантации...

Studopedia.info - Студопедия - 2014-2025 год . (0.013 сек.) русская версия | украинская версия