Изобретение относится к обработке цифрового сигнала.
Более конкретно, настоящее изобретение относится к способу, устройству и схеме для осуществления преобразования Адамара.
Процедуры кодирования формы сигнала преобразуют совокупность форм сигнала в улучшенную совокупность форм сигнала. Улучшенная совокупность форм сигнала затем может быть использована для получения улучшенной вероятности ошибок в двоичном разряде PB по сравнению с тем, что имеется для исходной совокупности после приема. В улучшенной совокупности форм сигнала сигналы настолько различны, насколько это возможно. Другой путь осуществления этой оценки заключается в уменьшении, насколько это возможно, перекрестной корреляции (которая обозначается как Zij) между двумя формами i и j сигналов.
Перекрестная корреляция (Zij) определяется как
где Si(t) и Sj(t) - две функции формы сигнала. Для совокупности форм сигнала, состоящей из биполярных импульсов (+1, -1), определение перекрестной корреляции (Zij) может быть упрощено:
Наименьшая возможная величина перекрестной корреляции имеется для антикорреляционных сигналов (Zij) = -1); однако этого можно достигнуть, только когда количество форм сигналов в совокупности равно двум и формы сигналов антиподны. Вообще, для наилучшей достижимой совокупности форм сигнала все величины перекрестной корреляции равны нулю. Такая совокупность называется ортогональной. Наиболее популярными для целей связи являются ортогональные коды форм сигнала.
Одним из способов преобразования совокупности данных в совокупность ортогональных данных - это преобразование Адамара. Преобразование Адамара характеризуется матрицей Адамара, в которой каждая строка матрицы Адамара ортогональна каждой другой строке этой матрицы, то есть в соответствии с уравнением 2 количество совпадений равно количеству несовпадений для каждой пары строк. С каждой строкой матрицы Адамара можно обращаться как с последовательностью Уолша (Walsh).
Матрица Адамара порядка n рекурсивно может быть определена следующим образом:
где H1 определяется следующим образом:
H1 = [1] (4)
и H'i = -Hi.
Таким образом,
Аналогично, путем применения уравнения 3 для H4 получаем следующее выражение:
а для H8 получаем
Были разработаны быстрые алгоритмы для увеличения эффективности характеристик преобразований Адамара. Эти разработки используют тот факт, что матрицы Адамара - действительные, симметричные и ортогональные построчно матрицы. Так как матрицы Адамара содержат только величины ±1, то не требуется перемножения во время вычислений в процессе преобразования. Более того, требуемое количество суммирований и вычитаний может быть уменьшено от n2 до n•log2h благодаря тому факту, что матрица Адамара порядка n (Hn) может быть представлена в виде произведения n разреженных матриц, то есть ≈log2(n):
Hn = Hn, (8)
где
Заметим, что верхние n/2 строки и нижние n/2 строки содержат только два ненулевых члена в каждой строке. Преобразование
может быть выполнено путем воздействия на u 
log2n раз. Из-за конкретной структуры 
необходимы только n суммирований и вычитаний каждый раз, когда 
действует на вектор, что позволяет получить общее количество n•(log2(n)) суммирований и вычитаний.
Проблема, связанная с осуществлением описанного выше преобразования Адамара, заключается в существенном расходе ресурсов памяти. Кроме этого, описанный выше способ не позволяет осуществлять последовательные преобразования. Соответственно, имеется необходимость в усовершенствованном способе и устройстве для осуществления преобразования Адамара, что позволит уменьшить нагрузку на ресурсы памяти и позволит осуществить последовательное преобразование. Такой способ также является объектом настоящего изобретения.
Первым объектом изобретения является устройство для осуществления преобразования Адамара, содержащее
совокупность последовательно соединенных процессоров быстрого преобразования Адамара (FHT-процессоров) для приема входного сигнала и задержанного обработанного сигнала, для вычитания упомянутого входного сигнала из упомянутого задержанного обработанного сигнала для получения сигнала разности, для выбора задержанного обработанного сигнала на основании сигнала разности входного сигнала в соответствии с заранее определенным форматом выбора, для суммирования упомянутого задержанного обработанного сигнала с выходным сигналом предыдущего FHT-процессора для получения сигнала суммы, а также для выбора и передачи входного сигнала на последующее устройство FHT-процессора на основании упомянутого задержанного обработанного сигнала и упомянутого сигнала суммы посредством последнего процессора быстрого преобразования Адамара, передающего выходной сигнал, при этом заявленное устройство для осуществления преобразования Адамара содержит совокупность элементов памяти, связанных с соответствующим одним из совокупности процессоров быстрого преобразования Адамара для приема упомянутого обработанного сигнала и задержки упомянутого обработанного сигнала на заранее определенный формат задержки для получения упомянутого задержанного обработанного сигнала.
В заявленном устройстве для осуществления преобразования Адамара каждый из совокупности FHT-процессоров содержит
устройство вычитания для приема упомянутого входного сигнала и упомянутого задержанного обработанного сигнала, а также для вычитания упомянутого входного сигнала из упомянутого задержанного обработанного сигнала для получения упомянутого сигнала разности,
первый мультиплексор для приема упомянутого сигнала разности и упомянутого входного сигнала, а также для передачи одного из упомянутых сигналов разности и упомянутого входного сигнала в качестве упомянутого обработанного сигнала в соответствии с первым заранее определенным форматом выбора,
сумматор для приема и суммирования упомянутого входного сигнала и упомянутого задержанного обработанного сигнала для получения сигнала суммы, а также мультиплексор для приема упомянутого сигнала суммы и упомянутого задержанного обработанного сигнала, а также для получения одного из сигналов суммы и упомянутого задержанного обработанного сигнала в соответствии с вторым заранее определенным форматом выбора.
В заявленном устройстве для осуществления преобразования Адамара каждый элемент памяти из упомянутой совокупности элементов памяти осуществляет задержку упомянутого обработанного сигнала на длительность задержки, равную удвоенной длительности задержки элемента памяти, связанного с предыдущим процессором быстрого преобразования Адамара.
Устройству для осуществления преобразования Адамара присуще также то, что каждый элемент памяти из совокупности элементов памяти осуществляет задержку упомянутого обработанного сигнала на длительность задержки, равную половине длительности задержки элемента памяти, связанного с предыдущим процессором быстрого преобразования Адамара.
В заявленном устройстве для осуществления преобразования Адамара упомянутый входной сигнал передается последовательно, а каждый из совокупности процессоров быстрого преобразования Адамара содержит
устройство вычитания для приема задержанного сигнала заема упомянутого обработанного сигнала, а также упомянутого входного сигнала и для вычитания упомянутого задержанного сигнала заема и упомянутого входного сигнала из разряда упомянутого задержанного обработанного сигнала для получения упомянутого сигнала разности и сигнала заема,
первый элемент памяти для приема и задержки упомянутого сигнала заема в соответствии с заранее определенной длительностью для получения упомянутого задержанного сигнала заема;
первый мультиплексор для приема упомянутого входного сигнала и упомянутого сигнала разности, а также для передачи одного из упомянутых входного сигнала и упомянутого сигнала разности в качестве обработанного сигнала в соответствии с заранее определенным форматом выбора,
сумматор для приема и суммирования упомянутого входного сигнала, упомянутого задержанного обработанного сигнала и задержанного сигнала переноса для получения упомянутого сигнала суммы и сигнала переноса,
второй элемент памяти для приема упомянутого сигнала переноса и для задержки его на заранее определенный промежуток времени для получения упомянутого задержанного сигнала переноса,
второй мультиплексор для приема упомянутого задержанного обработанного сигнала и упомянутого сигнала суммы, а также для передачи одного из сигналов суммы и упомянутого задержанного обработанного сигнала в качестве упомянутого входного сигнала на последующий этап.
Вторым объектом изобретения является способ осуществления Адамара, согласно которому принимают входной сигнал,
вычитают упомянутый входной сигнал из задержанного обработанного сигнала для получения сигнала разности,
выбирают обработанный сигнал из упомянутого сигнала разности и упомянутого входного сигнала в соответствии с заранее определенным форматом выбора, при этом заявленный способ осуществления преобразования Адамара предполагает задержку упомянутого обработанного сигнала на заранее определенный промежуток времени для получения упомянутого задержанного обработанного сигнала,
суммирование упомянутого обработанного сигнала с упомянутым входным сигналом для получения суммарного сигнала,
выбор входного сигнала из сигнала суммы и упомянутого задержанного обработанного сигнала в соответствии с вторым заранее определенным форматом выбора.
Согласно заявленному способу осуществления преобразования Адамара при задержке упомянутого обработанного сигнала
сдвигают совокупность запомненных обработанных сигналов в массивы с различными индексами,
сохраняют упомянутый обработанный сигнал в массиве с исходным индексом, причем
сохраненный обработанный сигнал, запомненный в массиве с конечным индексом, передают в качестве упомянутого задержанного обработанного сигнала.
Заявленный способ также предполагает, что при приеме упомянутого входного сигнала последовательно принимают биты упомянутого входного сигнала, причем при вычитании упомянутого входного сигнала из задержанного обработанного сигнала дополнительно вычитают сигнал заема из упомянутого обработанного задержанного сигнала и получают упомянутый сигнал заема в соответствии с упомянутым вычитанием, причем при суммировании упомянутого обработанного сигнала с упомянутым входным сигналом дополнительно суммируют сигнал переноса с упомянутым обработанным сигналом и упомянутым входным сигналом для дальнейшего получения сигнала переноса.
Еще одним объектом изобретения является вариант устройства для осуществления преобразования Адамара, содержащий
совокупность процессоров быстрого преобразования Адамара (FHT) с первым процессором FHT, имеющим два входа с первым входом для приема входного сигнала и имеющим два выхода, первый выход - для передачи обработанного сигнала, а также совокупность последовательно соединенных дополнительных FHT-процессоров, имеющих два входа с первым входом, связанным с вторым выходом предыдущего FHT-процессора, отличающийся тем, что устройство содержит совокупность элементов памяти с первым элементом памяти, имеющим вход, связанный с вторым выходом устройства вычитания, являющегося частью упомянутого первого FHT-процессора, и имеющим выход, связанный с вторым входом указанного того же устройства вычитания, и совокупность дополнительных элементов памяти, имеющих вход, связанный с вторым выходом сумматора, являющегося частью соответствующего дополнительного FHT-процессора, и имеющих выход, связанный с вторым входом упомянутого того же сумматора.
Согласно заявленному варианту устройства для осуществления преобразования Адамара каждый из совокупности FHT-процессоров включает в себя
устройство вычитания, имеющее два входа с первым входом для приема упомянутого входного сигнала и имеющее выход,
первый мультиплексор, имеющий два входа и выход, первый вход которого предназначен для приема упомянутого входного сигнала и второй вход, связанный с выходом упомянутого устройства вычитания,
сумматор, имеющий два входа с первым входом для приема упомянутого входного сигнала и имеющий выход,
второй мультиплексор, имеющий первый вход, связанный с выходом упомянутого сумматора, и второй вход для приема упомянутого входного сигнала.
При этом в заявленном варианте устройства для осуществления преобразования Адамара упомянутое устройство вычитания дополнительно содержит третий вход и второй выход, причем упомянутый сумматор дополнительно содержит третий вход и второй выход, устройство для осуществления преобразования Адамара дополнительно содержит
третий элемент памяти, имеющий вход, связанный с вторым выходом упомянутого устройства вычитания, и имеющий выход, связанный с третьим входом упомянутого устройства вычитания,
четвертый элемент памяти, имеющий вход, связанный с вторым выходом упомянутого сумматора, а также имеющий выход, связанный с третьим входом упомянутого сумматора.
Еще одним объектом изобретения является схема для осуществления преобразования Адамара, содержащая
совокупность последовательно соединенных FHT-процессоров для приема соответствующего входного сигнала и соответствующего задержанного обработанного сигнала, при этом вычитают упомянутый входной сигнал из упомянутого задержанного обработанного сигнала для получения сигнала разности, выбирают обработанный сигнал из сигнала разности и упомянутого входного сигнала в соответствии с заранее определенным форматом выбора, суммируют упомянутый обработанный задержанный сигнал с выходным сигналом упомянутого предыдущего FHT-процессора для получения сигнала суммы, а также выбирают входной сигнал из упомянутого задержанного обработанного сигнала и упомянутого сигнала суммы и передают его на последующий FHT-процессор, причем последний FHT-процессор передает выходной сигнал, отличающаяся тем, что содержит совокупность элементов памяти, связанных с соответствующим одним из совокупности FHT-процессоров для приема упомянутого обработанного сигнала и для задержки упомянутого обработанного сигнала в соответствии с заранее определенным форматом задержки для получения упомянутого задержанного обработанного сигнала.
В заявленной схеме для осуществления преобразования Адамара каждый из совокупности FHT-процессоров содержит
устройство вычитания для приема упомянутого входного сигнала и упомянутого обработанного задержанного сигнала, а также для вычитания упомянутого входного сигнала из упомянутого задержанного обработанного сигнала для получения упомянутого сигнала разности,
первый мультиплексор для приема упомянутого сигнала разности и упомянутого входного сигнала и для передачи одного из сигналов разности, а также входного сигнала в качестве обработанного сигнала в соответствии с первым заранее определенным форматом выбора,
сумматор для приема и суммирования упомянутого входного сигнала и упомянутого задержанного обработанного сигнала для получения упомянутого сигнала суммы; а также второй мультиплексор для приема упомянутого сигнала суммы и упомянутого задержанного обработанного сигнала, а также для передачи одного из сигналов суммы и упомянутого задержанного обработанного сигнала в соответствии со вторым заранее определенным форматом выбора.
Согласно заявленной схеме для осуществления преобразования Адамара каждый элемент памяти из упомянутой совокупности элементов памяти выполняет задержку упомянутого обработанного сигнала на длительность, равную удвоенной длительности задержки элемента памяти, связанного с предыдущим FHT-процессором.
При этом схеме для осуществления преобразования Адамара присуще то, что элемент памяти из упомянутой совокупности элементов памяти выполняет задержку упомянутого обработанного сигнала на длительность, равную половине длительности элемента памяти, связанного с предыдущим FHT-процессором.
В заявленной схеме для осуществления преобразования Адамара упомянутый входной сигнал передается последовательно и каждый из упомянутой совокупности FHT-процессоров содержит
устройство вычитания для приема задержанного сигнала заема упомянутого задержанного обработанного сигнала, а также входного сигнала и для вычитания упомянутого задержанного сигнала заема и упомянутого входного сигнала из разряда упомянутого задержанного обработанного сигнала для получения упомянутого сигнала разности и сигнала заема;
первый элемент памяти для приема упомянутого сигнала заема и для задержки его в соответствии с заранее определенной длительностью для получения упомянутого задержанного сигнала заема,
первый мультиплексор для получения упомянутого входного сигнала и упомянутого сигнала разности, а также для передачи одного из упомянутых входного сигнала и сигнала разности в качестве упомянутого обработанного сигнала в соответствии с заранее определенным форматом выбора,
сумматор для приема и суммирования упомянутого входного сигнала, упомянутого задержанного обработанного сигнала и задержанного сигнала переноса для получения упомянутого суммарного сигнала и сигнала переноса,
второй элемент памяти для приема упомянутого сигнала переноса и для задержки его на заранее определенную длительность для получения упомянутого задержанного сигнала, а также
второй мультиплексор для приема упомянутого задержанного обработанного сигнала и упомянутого сигнала суммы, а также для передачи упомянутого сигнала суммы или упомянутого задержанного обработанного сигнала в качестве упомянутого входного сигнала на последующий шаг.
Преобразование Адамара порядка 2 может быть выполнено элементом, который принимает две входные величины a и b и в ответ на это выдает две величины (a+b) и (a-b). Этот элемент может быть реализован в аппаратном обеспечении одним сумматором и одним устройством вычитания, двумя мультиплексорами и элементом памяти.
Описанный выше элемент может быть получен путем последовательного подключения входов к вычитающему входу устройства вычитания, к суммирующему входу сумматора и к входу B первого мультиплексора. Выход устройства вычитания подключается к входу A первого мультиплексора, а выход сумматора подключается к входу A второго мультиплексора. Выход первого мультиплексора подключается к входу элемента памяти. Выход элемента памяти затем подключается к суммирующему входу устройства вычитания, ко второму суммирующему входу сумматора и к входу B второго мультиплексора. Выходная информация затем последовательно передается на выход второго мультиплексора. Теперь обратимся к устройству осуществления преобразования Адамара порядка 4. Описанный выше фундаментальный элемент подключается последовательно к другому такому же, слегка преобразованному элементу. Этот второй элемент последовательного включения усовершенствован путем установки второго элемента памяти последовательно с первым элементом памяти, так чтобы выходная информация от первого мультиплексора вначале передавалась первому элементу памяти, а затем, на втором цикле такта, данные, запоминаемые в первом элементе памяти, должны быть передвинуты во второй элемент памяти до их передачи на суммирующие входы устройства вычитания и сумматора, а также на вход В второго мультиплексора на следующем цикле такта.
Путем некоторого дополнения можно осуществить преобразование Адамара порядка 8 путем добавления третьего усовершенствованного элемента одновременно с четвертым элементом памяти, установленными последовательно и так далее. Количество элементов памяти для последнего элемента Адамара будет равно половине порядка преобразования Адамара. Важно иметь в виду, что требуемая для этих элементов память не одна и та же. Это происходит из-за того, что сумма двух чисел m является двоичным числом m+l. Так что для элементов памяти на каждом последующем шаге выбора элемента требуется точность на один бит больше, чем для элементов памяти предыдущего элемента.
Для экономии ресурсов памяти, необходимых для выполнения этой обработки, в качестве дальнейшего усовершенствования предложенных выше средств порядок элементов может быть изменен на обратный. Например, в случае преобразования Адамара порядка 8 первый элемент может иметь четыре элемента памяти с объемом памяти для элемента памяти, равной (m+1) битам, где m - это количество битов на входе. Следующий элемент будет иметь элементы памяти объемом, равным удвоенному значению (m+2), а последний элемент в последовательности будет иметь один элемент памяти объемом (m+3).
Поэтому целью настоящего изобретения является предоставление устройства выполнения преобразований Адамара, использующего упрощенное аппаратное обеспечение. Преобразование Адамара может выполняться путем использования однобитных сумматоров с ресурсами перемещения и одновременного преобразования входной информации из параллельной формы в последовательную для передачи одного бита в каждый момент времени.
Другой целью настоящего изобретения является предоставление способа и устройства для дальнейшей экономии памяти, что достигается путем эффективного усечения величин, хранимых в описанных выше элементах памяти.
Свойства, цели и преимущества настоящего изобретения станут более очевидными после приведенного ниже детального рассмотрения с учетом чертежей, на которых использована сквозная нумерация и где
фиг. 1 является блок-схемой устройства для выполнения преобразования Адамара порядка 4;
фиг. 2 является блок-схемой устройства для выполнения преобразования Адамара порядка 64;
фиг. 3 является блок-схемой усовершенствованного исполнения устройства выполнения преобразования Адамара порядка 64; а
фиг. 4 является блок-схемой шага последовательного ввода FHT (быстрого преобразования Адамара).
Настоящее изобретение является способом и устройством для выполнения быстрого преобразования Адамара (FHT). На фигуре 1 проиллюстрирован пример исполнения настоящего изобретения для осуществления преобразования Адамара порядка 4. Например, если блок из четырех цифровых выборок (a1, a2, a3, a4) составляет входной символ, то устройство, показанное на фигуре 3, выполняет FHT входного символа для получения FHT закодированного символа в соответствии с приведенным ниже уравнением 11:
(11)
Необходимо отметить, что размерность четыре, использованная в примере исполнения, приведена всего лишь для примера и что способ и устройство настоящего изобретения в равной степени применимы для быстрого преобразования Адамара (FHT) всех определенных порядков.
В примере исполнения каждая из цифровых выборок (a1, a2, a3 и a4) имеет 8-битное представление, хотя в равной степени возможно использование и других размеров в битах в настоящем изобретении. Первая входная выборка a1 передается по входной сигнальной линии. Входная выборка a1 передается на вычитающий вход устройства вычитания 2 (сумматор, выполненный как устройство вычитания), на первый вход сумматора 6 и вход B мультиплексора 4. Мультиплексор 4 передает на свой выход либо сигнал по входной сигнальной линии, либо выходной сигнал от устройства вычитания 2. На первом цикле ввода сигнал от выхода мультиплексора 4 передается на входную сигнальную линию. На втором цикле ввода выход мультиплексора 4 принимает сигнал с выхода устройства вычитания 2, и таким образом процесс периодически повторяется на каждом цикле ввода. Например, для первого цикла ввода мультиплексор 4 передает выборку a1 на свой выход, которая принимается и сохраняется в элементе памяти 10.
На втором цикле ввода вторая выборка a2 передается на вычитающий выход устройства вычитания 2, на первый вход сумматора 6 и на вход B мультиплексора 4. Хранимая в элементе памяти 10 величина a1 передается на суммирующий вход устройства вычитания 2, на второй вход сумматора 6 и на вход B мультиплексора 8. В ответ на это устройство вычитания передает величину (a1-a2) на свой выход, кроме этого, эта величина передается на выход мультиплексора 4 и сохраняется в элементе памяти 10. Сумматор 6 передает величину (a1+a2) на свой выход. Мультиплексор 8 передает на свой выход либо выходную информацию от сумматора 6, либо выходную информацию от элемента памяти 10. На втором цикле ввода мультиплексор 8 передает на свой выход выходную информацию от сумматора 6, на третьем цикле ввода он передает на свой выход информацию от элемента памяти 10 и попеременно передает эти сигналы на свои выходы на каждом цикле ввода. Таким образом, для второго цикла ввода мультиплексор 8 передает на свой выход величину (a1+a2), переданную от сумматора 6.
Выходная информация (a1+a2) от мультиплексора 8 передается на вычитающий вход устройства вычитания 12, на первый вход сумматора 16 и на вход B мультиплексора 14. Мультиплексор 14 передает на свой выход сигнал от выхода мультиплексора 8 на втором и третьем циклах ввода, затем он передает выходную информацию от сумматора 12 на четвертом и пятом циклах ввода, и процесс периодически повторяется каждые два цикла. Таким образом, на втором цикле ввода мультиплексор 14 передает выходной сигнал (a1+a2) от мультиплексора 8 на элемент памяти 20, где он сохраняется.
В течение третьего цикла ввода выборка a3 передается на вычитающий ввод устройства вычитания 2, на первый вход сумматора 6 и вход B мультиплексора 4. Элемент памяти 10 передает хранимую в нем величину (a1-a2) на суммирующий вход устройства вычитания 2, на второй вход сумматора 6 и на вход B мультиплексора 8. Мультиплексор 4 передает величину a3 по входной сигнальной линии на элемент памяти 10, где он сохраняется. Мультиплексор 8 передает сигнал (a1-a2) от своего входа B на свой выход.
Величина (a1-a2), передаваемая на выход мультиплексора 8, передается на вычитающий вход устройства вычитания 12, на первый вход сумматора 16 и на вход B мультиплексора 14. Элемент памяти 20 передает свое содержимое (a1+a2) элементу памяти 22. Мультиплексор 14 передает выходной сигнал (a1-a2) от мультиплексора 8 на элемент памяти 20.
На четвертом цикле следующая входная выборка a4 передается на вычитающий вход устройства вычитания 2, на первый вход сумматора 6 и на вход B мультиплексора 4. Элемент памяти 10 передает хранимую в нем величину a3 на суммирующий вход устройства вычитания 2, на второй вход сумматора 6 и на вход B мультиплексора 8. Сумматор 2 передает (a3-a4) на вход A мультиплексора 4. Мультиплексор 4 передает выходную информацию (a3-a4) от устройства вычитания 4 на элемент памяти 10, где она сохраняется. Сумматор 6 передает сумму (a3+a4) на вход A мультиплексора 8. Мультиплексор 8 передает на свой выход сигнал (a3+a4) от сумматора 6.
Величина (a3+a4), передаваемая от мультиплексора 8, затем передается на вычитающий выход устройства вычитания 12, на первый вход сумматора 16 и на вход B мультиплексора 14. Элемент памяти 22 затем передает свое содержимое - (a1+a2) - на суммирующий вход устройства вычитания 12, на второй вход сумматора 16 и на вход B мультиплексора 18. Элемент памяти 20 передает свое содержимое - (a1+a2) - на элемент памяти 22. Сумматор 12 в ответ на это передает сумму принятых величин - (a1+a2)-(a3+a4) на вход A мультиплексора 14. Мультиплексор 14 передает величину, переданную с выхода устройства вычитания 12 - (a1+a2)-(a3+a4), на элемент памяти 20, где она сохраняется. Сумматор 16 затем передает сумму принятых двух величин - (a1+a2)+(a3+a4) на вход A мультиплексора 18. Мультиплексор 18 передает сигнал, полученный от сумматора 16 на циклах ввода 4 и 5, затем передает выходную информацию от элемента памяти 22 в качестве выходной информации циклов ввода 6 и 7, и процесс периодически повторяется каждые два цикла. Мультиплексор 18 передает необходимую сумму (a1+a2+a3+a4) в качестве первой выходной информации на втором этапе устройства FHT.
На пятом цикле ввода вторая входная выборка a5 передается на вычитающий вход устройства вычитания 2, на первый вход сумматора 6 и на вход B мультиплексора 4. Элемент памяти 10 передает хранимую в нем величину (a3-a4) на суммирующий вход сумматора 2, на второй вход сумматора 6 и на вход B мультиплексора 8. Мультиплексор 4 передает величину a5 по входной сигнальной линии на элемент памяти 10, где он сохраняется. Мультиплексор 8 передает сигнал (a3-a4), переданный от элемента памяти 10, на свой выход.
Величина (a3-a4) с выхода мультиплексора 8 передается на вычитающий вход сумматора 12, на первый вход сумматора 16 и на вход B мультиплексора 14. Элемент памяти 22 передает свое содержимое - (a1-a2) - на суммирующий вход устройства вычитания 12, на второй вход сумматора 16 и на вход B мультиплексора 18. Элемент памяти 20 передает свое содержимое - (a1+a2)-(a3+a4) на элемент памяти 22. Устройство вычитания 12 передает (a1-a2)-(a3-a4) на первый вход мультиплексора 14, который передает эту величину на элемент памяти 20. Аналогично, сумматор 16 передает (a1-a2)+(a3-a4) или (a1-a2+a3-a4) на первый вход мультиплексора 18, который передает эту величину на свой выход.
На шестом цикле ввода следующая входная выборка a6 передается на вычитающий вход устройства вычитания 2, на первый вход сумматора 6 и на вход B мультиплексора 4. Элемент памяти 10 передает хранимую в нем величину a5 на суммирующий вход устройства вычитания 2, на второй вход сумматора 6 и на вход B мультиплексора 8. Устройство вычитания передает (a5-a6) на вход A мультиплексора 4. Мультиплексор 4 передает величину (a5-a6) со своего входа A на элемент памяти 10, где она сохраняется. Сумматор 6 передает (a5+a6) на вход A мультиплексора 8. Мультиплексор 8 передает сигнал (a5+a6) от своего входа A на свой выход.
Выходной сигнал (a5+a6) от мультиплексора 8 передается на вычитающий вход устройства вычитания 12, на первый вход сумматора 16 и на вход B мультиплексора 14. Элемент памяти 22 затем передает свое содержимое - (a1+a2)-(a3+a4) на суммирующий вход устройства вычитания 12, на второй вход сумматора 16 и на вход B мультиплексора 18. Элемент памяти 20 передает свое содержимое (a1-a2)-(a3-a4) на элемент памяти 22. Мультиплексор 14 передает сигнал (a5+a6) со своего входа B на элемент памяти 20, где он сохраняется. Мультиплексор 18 передает величину сигнала (a1+a2)+(a3+a4)=(a1+a2-a3-a4) с входа B на свой выход.
На седьмом цикле ввода следующая входная выборка a7 передается на вычитающий выход устройства вычитания 2, на первый вход сумматора 6 и на вход B мультиплексора 4. Элемент памяти 10 передает хранимую в нем величину - (a5-a6) на суммирующий вход сумматора 2, на второй вход сумматора 6 и на вход B мультиплексора 8. Мультиплексор 4 передает величину a7 со своего входа B на элемент памяти 10, где она сохраняется. Мультиплексор 8 передает сигнал (a5-a6) от своего входа B на свой выход.
Выходной сигнал (a5-a6) мультиплексора 8 передается на вычитающий вход устройства вычитания 12, на первый вход сумматора 16 и на вход B мультиплексора 14. Элемент памяти 22 затем передает свое содержимое - (a1-a2)-(a3-a4) на суммирующий вход устройства вычитания 12, на второй вход сумматора 16 и на вход B мультиплексора 18. Элемент памяти 20 передает свое содержимое - (a5+a6) на элемент памяти 22. Мультиплексор 14 передает сигнал (a5-a6) от своего входа B на элемент памяти 20, где он сохраняется. Мультиплексор 18 передает величину сигнала (a1-a2)-(a3-a4)=(a1-a2-a3+a4) от своего входа B на свой выход.
Необходимо отметить, что FHT входной последовательности (a1, a2, a3, a4), (a1+a2+a3+a4, a1-a2+a3-a4, a1+a2-a3-a4, a1+a2-a3-a4) успешно было передано устройством. После ввода следующего элемента a8 этой последовательности в устройство на выходе устройства появляется первый элемент FHT преобразования входной последовательности (a5, a6, a7, a8), который имеет вид a5+a6+a7+a8. Этот процесс может быть продолжен бесконечно.
Фундаментальный элемент устройства FHT ограничен пунктирной линией блока 24. Блок 24 составлен из одного устройства вычитания 12, одного сумматора 16 и двух мультиплексоров (мультиплексоры 14 и 18), эта подсистема будет называться процессором FHT. Следует отметить, что устройство вычитания является сумматором с инвертирующим входом. Совместно с устройствами памяти или элементами памяти они образуют полный этап FHT. Дополнительные этапы могут добавляться путем передачи выходной информации предыдущего этапа на добавляемый этап. Единственное отличие между этапом и предыдущим этапом заключается в том, что количество элементов памяти удваивается (кроме этого, количество битов для данного элемента памяти должно увеличиваться на один) и частота тактирования элементов памяти понижается в два раза по сравнению с предыдущим этапом.
На фигуре 2 показана блок-схема FHT-устройства для выполнения FHT порядка 64. Процессоры FHT 30, 34, 38, 42, 46 и 50 все идентичны процессору FHT, показанному детально в блоке 24 фигуры 1, а устройства памяти 32, 36, 40, 44, 48 и 52 являются совокупностью взаимосвязанных элементов памяти или защелок данных, таких, которые образуются при помощи регистра сдвига, что также описано на фигуре 1. В примере исполнения входные для процессора FHT 30 данные состоят из восьмибитных чисел, хотя настоящее изобретение в равной степени можно использовать для данных с любой битовой длиной.
Так как в этом примере исполнения поток входных данных состоит из данных типа 8 бит/выборка, то элемент памяти в устройстве памяти 32 должен иметь возможность удержания девяти битов для согласования возможных выходов FHT-процессора 30 без усечения, так как сумма двух n-битных чисел является (n+1)-битным числом. Аналогично, элементы памяти устройства памяти 36 должны иметь возможность сохранять 10 битов. Элементы памяти устройства памяти 40 должны иметь возможность сохранять 11 битов; элементы памяти устройства памяти 44 должны иметь возможность хранить 12 битов; элементы памяти устройства памяти 48 должны иметь возможность сохранять 13 битов, а элементы памяти устройства памяти 52 должны иметь возможность хранить 14 битов.
На фигуре 3 проиллюстрировано усовершенствованное исполнение настоящего изобретения. Устройство, показанное на фигуре 3, осуществляет быстрое преобразование Адамара порядка 64. FHT-процессоры 90, 94, 98, 102, 106 и 110 идентичны по конструкции FHT-процессору 24, который детально показан на фигуре 1. Единственное отличие работы FHT-процессора, показанного на фигуре 3, по сравнению с работой процессора, показанного на фигуре 2, заключается в коммутации мультиплексоров (не показаны) FHT-процессоров 90, 94, 98, 102, 106 и 110. На первом этапе мультиплексоры FHT-процессора 90 коммутируются только во время каждых 32 циклов ввода. На втором этапе FHT мультиплексоры FHT-процессора 94 коммутируются во время каждых 16 циклов ввода. На последнем этапе мультиплексоры FHT-процессора 110 коммутируются на каждом цикле ввода.
Существенным различием между усовершенствованным исполнением, показанным на фигуре 3, и исполнением, показанным на фигуре 2, является экономия полного объема используемой памяти. Повторно обращаясь к примеру исполнения для обработки данных длиной в восемь битов, отметим, что первое устройство памяти должно иметь возможность хранения девятибитного числа, в то время как устройство памяти следующего этапа должно иметь возможность хранить десятибитное число. Поэтому в этом предпочтительном исполнении этапы, во время которых устройствам памяти необходимо хранить наименьшее количество битов, используются для хранения наибольшего количества величин. Устройство памяти 92 хранит тридцать два 9-битных числа, устройство памяти 96 - шестнадцать 10-битных чисел, устройство 100 - восемь 11-битных чисел, устройства 104 - четыре 12-битных числа, устройство 108 - два 13-битных числа, а устройство 112 - одно 14-битное число. Количество битов, хранимых в памяти во время использования этого усовершенствованного исполнения, можно рассчитать по формуле, приведенной ниже:
где n - это порядок выполняемого FHT, а m - это количество битов на вход.
На фигуре 4 представлено альтернативное исполнение настоящего изобретения для приема выборок как потока последовательных битов. В этом альтернативном исполнении биты, которые содержат входные выборки, передаются на устройство FHT последовательно. Для каждой входной выборки на FHT-процессор передаются биты выборки от самого младшего быта (LSB) до самого старшего бита (MSB). Входной бит передается на первый вычитающий выход устройства вычитания 120, на вход B мультиплексора 124, а также на первый суммирующий вход сумматора 128. Кроме этого, выходные данные от элемента памяти 126 передаются на суммирующий вход устройства вычитания 120. Последней входной информацией для устройства вычитания 120 для второго вычитающего входа является бит заема предыдущей операции, который передается от устройства задержки 122. Элементы задержки 122 и 130 обеспечивают задержку, равную по длительности периоду одного разряда. Устройство вычитания 120 затем вычитает задержанный бит заема и текущий входной вычитаемый бит из суммируемого бита. В результате этой операции получаются два бита выходных данных, включая бит заема, который передается на задержку 122, а также разностный бит, который передается на вход A мультиплексора 124.
Мультиплексор 124 выбирает данные для одного из своих двух входов для передачи на свой выход. Циклы коммутации мультиплексоров 124 и 132 такие же, как ранее описываемый, с учетом того, что входной цикл определяется как период времени, необходимый для передачи всех битов, включая входную выборку. Как упоминалось ранее, входной бит передается на первый суммирующий вход сумматора 128. Выходная информация от элемента памяти 126 также передается на второй суммирующий вход сумматора 128. Кроме этого, задержанный бит переноса от предыдущей операции суммирования сумматора 128 передается от элемента задержки 130 на третий суммирующий вход сумматора 128. Эти три входные суммы (задержанного носителя, входного бита и выходного бита от элемента памяти) суммируются для получения двух битов данных. Первый бит, бит переноса, передается на элемент задержки 130, а суммарный бит передается на вход A мультиплексора 132. Мультиплексор 132, кроме этого, принимает на свой вход B выходной бит элемента памяти 126. Мультиплексор 132 затем выбирает данные одного из своих двух входов для передачи на свой выход в качестве бита одного из FHT коэффициентов в соответствии с операцией коммутации, описанной выше.
Последний способ, который может быть использован отдельно или в комбинации с упомянутыми выше усовершенствованиями, это способ, использующий усечение. Когда данные передаются параллельным образом на FHT-устройство, то усечение может достигаться путем простой передачи заранее определенного количества самых старших битов данных на элементы памяти. В случае, когда данные передаются на FHT-устройство в последовательном потоке, биты, передающие самые младшие биты вначале на элемент памяти, сдвигаются в, а иногда и за первый элемент памяти, который действует как последовательно загруженный регистр сдвига параллельного выхода. Когда в элементе памяти остаются только самые старшие биты, то достигается усечение, и эти биты могут затем параллельно сдвигаться к следующему элементу памяти.
Приведенное выше описание предпочтительных исполнений дает возможность специалисту в данной области техники выполнить или использовать настоящее изобретение. Специалисты данной области техники могут осуществить различные модификации этих исполнений, а приведенные здесь основные принципы могут использоваться для других исполнений без привлечения изобретательских способностей. Таким образом, настоящее изобретение не ограничивается приведенными здесь исполнениями, но предназначено для использования в самых различных областях в соответствии с приведенными здесь принципами и новыми свойствами и с прилагаемой формулой изобретения.
Перевод надписей к рисункам
Фиг. 1
1. Выход
2. Вход
Фиг. 2, 3
1. Вход
2. Процессор быстрого преобразования Адамара
3. Выход
Фиг. 4
1. Элемент памяти
2. Задержка
3. Резерв
4. Устройство вычитания
5. Вход
6. Разность
7. Сумматор
8. Носитель
9. Сумма
10. Выходх
Изобретение относится к способам обработки цифрового сигнала. Базовым строительным блоком устройства быстрого преобразования Адамара является FHT-процессор. В состав FHT-процессора входят устройство вычитания, предназначенное для вычитания входного символа из задержанного обработанного символа, первый мультиплексор, элемент памяти для хранения выходной информации первого мультиплексора в качестве задержанного обработанного символа, сумматор для суммирования входного символа с задержанным обработанным символом, а также второй мультиплексор для получения либо суммы входного символа и задержанного обработанного символа, либо задержанного обработанного символа в качестве выходной информации. Этот базовый процессор предназначен для работы совместно с различными конфигурациями памяти. Эти процессоры могут затем быть связаны последовательно для выполнения преобразования Адамара любых определенных порядков. Кроме этого, изобретение описывает два способа оптимизации использования ресурсов памяти. Один из них использует оптимальную конфигурацию элементов памяти, а второй использует усечение. Технический результат изобретения заключается в уменьшении расходов ресурсов памяти и возможности осуществления последовательного преобразования. 4 с. и 12 з.п. ф-лы, 4 ил.
| US 3792355 A, 12.02.74 | |||
| Устройство быстрого преобразования сигналов по Уолшу с упорядочением по Адамару | 1984 |
|
SU1265795A1 |
| Устройство для преобразования Адамара цифровой последовательности | 1987 |
|
SU1462355A1 |
| US 4446530 A, 01.05.84 | |||
| Устройство ортогонального преобразования цифровых сигналов по Уолшу-Адамару | 1980 |
|
SU951320A1 |
| Устройство для ортогонального преобразования цифровых сигналов по Уолшу-Адамару | 1982 |
|
SU1098005A1 |
| Устройство для быстрого преобразования Уолша-Адамара | 1988 |
|
SU1536398A1 |
