СЖИМАТЕЛЬ ВЫДЕЛЯЕМЫХ СИМВОЛОВ В ДВОИЧНОЙ КОМБИНАЦИИ Российский патент 1998 года по МПК G06F7/00 H03M7/30 

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

Известен уплотнитель единиц в двоичной комбинации по (авт. св. СССР N 798830, кл. 5 G 06 F 7/50, 1978 г., фиг. 2, 5), осуществляющий уплотнение (сжатие) единиц в N-разрялной двоичной комбинации их поступенчатым сдвигом элементами И, ИЛИ к младшим разрядам, при этом на первой ступени уплотняются единицы в каждых 2-разрядных частях входной двоичной комбинации, на второй ступени преобразуются пары 2-разрядных уплотненных кодов от первой ступени в 4-х разрядные уплотненные коды и т.д., на последней ступени преобразуются N/2-разрядных уплотненных кодов от предыдущей ступени в N-разрядный выходной уплотненный код.

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

Этот недостаток определяется в двоичной системе комбинации символов одного вида (единиц).

Наиболее близким по технической сущности к предлагаемому изобретению является сжиматель выделяемых символов в двоичной комбинации в виде двумерной итеративной сети (квадратной матрицы) из N² ячеек, расположенных в N строках и N столбцах матрицы и образующих первый и второй каналы в каждой строке матрицы, третий и четвертый каналы в каждом столбце последовательным соединением аналогичных одноименных ячеек, при этом в каждой ячейке второй канал образован проходной шиной, остальные каналы образованы коммутаторами на элементах И, ИЛИ, НЕ (Фет Я.И. Параллельные процессы для управляющих систем. М. : Энергоиздат, 1981 г., с. 123, 135-137, рис. 56, 57а).

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

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

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

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

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

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

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

На фиг.1 изображена схема сжимателя выделяемых символов в двоичной комбинации; на фиг.2 - схема ячейки; на фиг.3 - диаграмма, поясняющая преобразование структуры 8-разрядной двоичной комбинации сжатием выделяемых символов.

Сжиматель символов в двоичной комбинации (фиг.1) содержит элемент И 1, элементы И-НЕ 2.1, 2.2,..., 2, N-1, ячейки 3.1, 3.2,..., 3.L, элементы НЕТ 4.1, 4.2, ..., 4.N-1, вход 5 и выход 6 первого канала ячейки 3.1, вход 7 и выход 8 второго канала ячейки 3.1, вход 9 и выход 10 третьего канала ячейки 3.1, вход 11 и выход 12 четвертого канала ячейки 3.1, управляющие входы 13.1, 13.2, ..., 13.N, информационные входы 14.1, 14.2, ..., 14.N, управляющие выходы 15.1, 15.2, ..., 15.N и информационные выходы 16.1, 16.2, ..., 16.N, где N - количество разрядов в двоичной комбинации, L = N (N-1)/2.

Ячейки 3.1, 3.2, ..., 3.L выполнены одинаково и образуют треугольную матрицу из N-1 строк и N-1 столбцов, в i-й строке и j-м столбце которой расположена ячейка 3.М (i=1,2, ..., N-1, j=1,2, ..., i, M=i+(2N-j-2)(j-1)/2), в каждой строке и в каждом столбце последовательно соединены каналы ячеек, образуя первый и второй каналы строки, третий и четвертый каналы столбца. В каждой строке и в каждом столбце матрицы входы каналов первых ячеек строки, столбца и выходы каналов последних ячеек строки, столбца являются также входами и выходами одноименных каналов сроки, столбцы матрицы. Например, вход 9 третьего канала ячейки 3.1 в первой строке и в первом столбце матрицы и выход третьего канала ячейки 3.N-1 в (N-1)-й строке и в первом столбце матрицы является входом и выходом третьего канала первого столбца матрицы.

Первый управляющий вход 13.1 сжимателя выделяемых символов в двоичной комбинации подключен к входу 9 третьего канала первого столбца матрицы и к первому входу элемента И 1, выход которого соединен с входом 11 четвертого канала первого столбца матрицы (вход четвертого канала ячейки 3.1). (i+1)-й управляющий вход 13.(i+1) сжимателя выделяемых символов в двоичной комбинации подключен к входу первого канала i-й строки матрицы (вход первого канала ячейки 3.i) и к первому входу элементов И-НЕ 2.i, выход которого соединен с выходом второго канала i-й строки матрицы (вход второго канала ячейки 3.i).

Первый информационный вход 14.1 и (i+1)-й информационный вход 14.(i+1) сжимателя выделяемых символов в двоичной комбинации подключены соответственно к второму входу элементов И 1 и к второму входу элементов И-НЕ 2.i.

Выход первого канала первой строки матрицы (выход 6 первого канала ячейки 3.1) подключен к входу третьего второго столбца матрицы (вход третьего канала ячейки 3. N) и к прямому входу элемента НЕТ 4.1, инверсный вход и выход которого соединены соответственно с выходом второго канала первой строки матрицы (выход 8 второго канала ячейки 3.1) и с выходом четвертого канала второго столбца матрицы (вход четвертого канала ячейки 3.N). Аналогичным образом соединены выход первого канала и выход второго канала i-й строки матрицы с выходами элемента НЕТ 4.i, выход первого канала i-й строки матрицы и выход элемента 4.i соответственно с входом третьего канала и с выходом четвертого канала (i+1)-го столбца матрицы.

Выход третьего канала и выход четвертого канала j-го столбца матрицы подключен соответственно к управляющему выходу 15.j и к информационному выходу 16. j сжимателя выделяемых символов в двоичной комбинации, управляющий выход 15. N и информационный выход 16.N которого подключен соответственно к выходу первого канала (N-1)-й строки матрицы (выход первого канала ячейки 3. L) и к выходу элемента НЕТ 4.N-1.

В каждой ячейке (фиг.2) второй канал выполнен проходной шиной, соединяющей его вход 7 и выход 8, первый канал, третий канал и четвертый канал ячейки выполнены соответственно на элементе И 17, на элементе ИЛИ 18 и на элементах ИЛИ 19, ИЛИ-НЕ 20, вход 5 и выход 6 первого канала ячейки подключены соответственно к первому входу и к выходу элемента И 17, вход 9 третьего канала ячейки подключен к второму входу элемента И 17, к первому входу элемента ИЛИ-НЕ 20 и к первому входу элемента ИЛИ 18, второй вход и выход которого соединены соответственно с входом 5 первого канала и с выходом 10 третьего канала ячейки, вход 11 и выход 12 четвертого канала ячейки подключены соответственно к первому входу и к выходу элемента ИЛИ 19, второй вход которого соединен с выходом элемента ИЛИ-НЕ 20, а выход 7 второго канала ячейки подключен к второму входу элемента ИЛИ-НЕ 20.

Работа предлагаемого устройства заключается в следующем.

Сжиматель выделяемых символов в двоичной комбинации (фиг. 1) выделяет из выходной двоичной комбинации (фиг. 3, б) символы, указанные сигналами 1 маски (фиг. 3, а) и сдвигает их к младшим разрядам выходной двоичной комбинации (фиг. 3, в), в которой общее количество разрядов равно количеству разрядов во входной двоичной комбинации, количество разрядов с выделенными и сжатыми символами равно количеству сигналов 1 маски, остальные разряды содержат сигнал 0.

На управляющие входы 13.1, 13.2, ..., 13.N и на информационные входы 14.1, 14.2, . .., 14.N сжимателя выделяемых символов в двоичной комбинации параллельными кодами поступают соответственно N-разрядные маска и двоичная комбинация. Сигнал первого разряда маски с первого управляющего входа 13.1 поступает на первый вход элементов И 1 и на вход третьего канала первого столбца матрицы (вход 9 третьего канала ячейки 3.1). Сигнал (i+1)-го разряда маски с (i+1)-го управляющего входа 13.i+1 поступает на первый элемент И-НЕ 2. i и на вход первого канала i-й строки матрицы (вход первого канала ячейки 3.i) (i=1,2, ..., N-1). Сигнал первого разряда двоичной комбинации с первого информационного входа 14.1 и сигнал (i+1)-го разряда двоичной комбинации с (i+1)-го информационного входа 14. i+1 поступает соответственно на второй вход элемента И 1 и на второй вход элемента И-НЕ 2.i.

Элемент И 1 и элементы И-НЕ 2.1, 2.2, ..., 2.N-1 маскируют двоичную комбинацию. С выхода элемента И 1 на выход четвертого канала первого столбца матрицы (вход 11 четвертого канал ячейки 3.1) поступают прямой сигнал первого разряда двоичной комбинации при наличии сигнала логической единицы (сигнала 1) в первом разряде маски и сигнал логического нуля (сигнал 0) в противном случае. С выхода элемента И-НЕ 2.i на вход второго канала i-й строки матрицы (вход 7 второго канала ячейки 3.i) поступают инверсный сигнал (i+1)-го разряда двоичной комбинации при наличии сигнала 1 в (i+1)-м разряде маски и сигнал 0 в противном случае.

Так как второй канал ячеек выполнен проходной шиной, выходные сигналы элементов И-НЕ 2.1, ..., 2.N-1 проходят по второму каналу каждой сроки матрицы без преобразования (насквозь).

Сигнал 0 первого разряда маски проходит через вход 9, элемент ИЛИ 18, выход 10 третьего канала ячеек первого столбца матрицы (фиг.2) и сохраняет значение 0, пока разряды маски содержат 0. В этих ячейках сигнал 0 с выхода 9 третьего канала ячейки на второй вход элемента И 17 и на первый вход элемента ИЛИ-НЕ 20, закрывает элемент И 17 первого канала ячейки и открывает элемент ИЛИ-НЕ 20 четвертого канала ячейки.

В некоторой ячейке 3.i первого столбца матрицы, где впервые на входе 5 первого канала ячейки встречается сигнал 1 маски, этот сигнал через элемент ИЛИ 18 поступает на выход 10 третьего канала ячейки 3.i, далее проходит и сохраняет значение 1 в третьем канале ячеек 3.i+1, 3.i+2, ... 3.N-1 первого столбца матрицы.

Так как на вход 9 третьего канала ячейки 3.i еще поступает сигнал - и элемент ИЛИ-НЕ 20 открыт, инверсный маскированный сигнал (i+1)-го разряда двоичной комбинации проходит, инвертируясь, через элемент ИЛИ-НЕ 20, элемент ИЛИ 19 на выход 12 четвертого канала ячейки 3.i.

Сигнал 1 в третьем канале ячеек 3.i+1, 3.i+2, ..., 3.N-1 первого столбца матрицы открывает в каждой из них элемент И 17, разрешая прохождение сигнала соответствующего разряда маски через вход 5, элемент И 17, выход 6 первого канала ячейки, и устанавливает сигнал - на выходе элемента ИЛИ-НЕ 20, разрешая прохождение выделенного сигнала двоичной комбинации через вход 11, элемент ИЛИ 19, выход 12 четвертого канала ячейки.

В результате с выхода 6 первого канала ячейки 3.1 первого столбца матрицы на прямой вход элемента НЕТ 4.1 и с выходов первого канала ячеек 3.2, 3.3, ..., 3.N-1 первого столбца матрицы на выходы первого канала ячеек 3.N, 3.N+1, ..., 3.2N-3 второго столбца матрицы поступает копия маски за исключением ее первого сигнала 1, а с выхода третьего канала и с выходы четвертого канала первого столбца матрицы соответственно на первый управляющий выход 15.1 и на первый информационный выход 16.1 сжимателя выделяемых символов в двоичной комбинации поступают соответственно первый сигнал 1 маски и указанный им сигнал разряда двоичной комбинации.

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

Аналогичные преобразования происходят во втором, третьем столбцах матрицы и т. д. , на выходах и третьих каналов выделяются соответственно второй сигнал 1, третий сигнал 1 маски и т.д., на выходах их четвертых каналов выделяются сигналы (символы) двоичной комбинации, указанные соответственно вторым сигналом 1, третьим сигналом 1 маски и т.д. При этом элемент НЕТ 4, на инверсный вход которого по второму каналу i-й строки матрицы поступает инверсный маскированный сигнал (i+1)-го разряда двоичной комбинации, выделяет сигнал (i+1)-го разряда двоичной комбинации при наличии сигнала 1 на выходе первого канала i-й строки матрицы, что равносильно наличию сигнала 1 в i+1 младших разрядах маски.

Таким образом сжиматель выделяемых сигналов в двоичной комбинации выделяет из двоичной комбинации только те символы, которым соответствуют сигналы 1 маски, и выводит на управляющие выходы 15.1, 15.2, ..., 15.N преобразованную маску, в которой сигналы 1 сжаты к первому управляющему выходу 15.1, выводит на информационные выходы 16.1, 16.2, ..., 16.N преобразованную двоичную комбинацию, в которой выделенные символы сжаты к первому информационному выходу 16.1.

В известном устройстве, выбранном за прототип, количество логических элементов равно 6N², в предлагаемом устройстве - 2N²-2, т.е. не менее чем в три раза меньше по сравнению с известным устройством.

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

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

Сжиматель выделяемых выделяемых символов в двоичной комбинации, содержащий по N информационных и N управляющих входов, по N управляющих и N информационных выходов и N(N - 1) / 2 ячеек, образующих матрицу из N - 1 строк, N - 1 столбцов (N - количество разрядов двоичной комбинации) и первый и второй каналы в каждой строке матрицы, третий и четвертый каналы в каждом столбце матрицы последовательным соединением аналогичных одноименных каналов ячеек, при этом в каждой строке матрицы вход первого канала, вход второго канала, выход первого канала и выход второго канала строки являются соответственно входом первого канала, входом второго канала первой ячейки в строке, выходом первого канала и выходом второго канала последней ячейки в строке, в каждом столбце матрицы вход третьего канала, вход четвертого канала, выход третьего канала и выход четвертого канала столбца являются соответственно входом третьего канала, входом четвертого канала первой ячейки в столбце, выходом третьего канала и выходом четвертого канала последней ячейки в столбце, выход третьего канала и выход четвертого канала i-го столбца матрицы (i = 1,2, ..., N - 1) подключен соответственно к i-му управляющему выходу и i-му информационному выходу сжимателя выделяемых символов в двоичной комбинации, в каждой ячейке второй канал выполнен проходной шиной, соединяющей его вход и выход, первый канал и четвертый канал ячейки выполнены соответственно на первом элементе И и первом элементе ИЛИ, вход и выход первого канала ячейки подключены соответственно к первому входу и выходу первого элемента И, вход и выход четвертого канала ячейки подключены соответственно к первому входу и выходу первого элемента ИЛИ, отличающийся тем, что в сжиматель выделяемых символов в двоичной комбинации введены второй элемент И, N - 1 элементов И - НЕ, N - 1 элементов НЕТ, в каждой ячейке введены второй элемент ИЛИ в третий канал ячейки и элемент ИЛИ - НЕ в четвертый канал ячейки, ячейки расположены в i-й строке и j-м столбце матрицы (j = 1,2 ... i), при этом первый управляющий вход сжимателя выделяемых символов в двоичной комбинации подключен к входу третьего канала первого столбца матрицы и первому входу второго элемента И, выход которого подключен к входу четвертого канала первого столбца матрицы, (i + 1)-й управляющий вход сжимателя выделяемых символов в двоичной комбинации подключен к входу первого канала i-й строки матрицы и первому входу i-го элемента И - НЕ, выход которого соединен с входом второго канала i-й строки матрицы, первый информационный вход и (i + 1)-й информационный вход сжимателя выделяемых символов в двоичной комбинации подключены соответственно к второму входу второго элемента И и второму входу i-го элемента И - НЕ, выход первого канала i-й строки матрицы, кроме (N - 1)-й строки матрицы, подключен к входу третьего канала (i + 1)-го столбца матрицы и прямому входу i-го элемента НЕТ, инверсный вход и выход которого соединены соответственно с выходом второго канала i-й строки матрицы и входом четвертого канала (i + 1)-го столбца матрицы, выход первого канала и выход второго канала (N - 1)-й строки матрицы подключен соответственно к прямому и инверсному входам (N - 1)-го элемента НЕТ, прямой вход и выход которого соединены соответственно с N-м управляющим выходом и N-м информационным выходом сжимателя выделяемых символов в двоичной комбинации, причем в каждой ячейке матрицы вход третьего канала ячейки подключен к второму входу первого элемента И, первому входу элемента ИЛИ - НЕ и первому входу второго элемента ИЛИ, второй вход и выход которого соединены соответственно с входом первого канала и выходом третьего канала ячейки, вход второго канала ячейки подключен к второму входу элемента ИЛИ - НЕ, выход которого соединен с вторым входом первого элемента ИЛИ.