Синтез эффективных алгоритмов быстрого преобразования Фурье и циклической свертки и их применение в устройствах сопряжения аналоговых и цифровых систем передачи
Диссертация
Цифровая обработка сигналов (ЦОС) находит все более широкое применение в различных областях науки и техники. Постоянное усложнение задач практики, увеличение объема передаваемой и преобразуемой информации, требование реального масштаба времени вызывают необходимость дальнейшего совершенствования методов ЦОС, синтеза новых, все более эффективных вычислительных алгоритмов. Эта задача нашла… Читать ещё >
Содержание
- 1. АНАЛИЗ АЛГОРИТМОВ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ И ЦИКЛИЧЕСКОЙ СВЕРТКИ, ОСНОВАННЫХ НА ПРЯМОУГОЛЬНЫХ ПРЕОБРАЗОВАНИЯХ
- 1. 1. Постановка задачи
- 1. 2. Основные определения
- 1. 3. Синтез алгоритмов быстрого преобразования Фурье и циклической свертки коротких последовательностей
- 1. 3. 1. Модульная арифметика полиномов
- 1. 3. 2. Синтез прямоугольных преобразований
- 1. 3. 3. Синтез алгоритмов быстрого преобразования Фурье на основе прямоугольных преобразований
- 1. 4. «Гнездовой» алгоритм вычисления циклической свертки длинных последовательностей
- 1. 5. Алгоритмы быстрого преобразования Фурье длинных по следоват ельно ст ей
- 1. 5. 1. Алгоритм с множителями поворота
- 1. 5. 2.Алгоритм простых множителей
- 1. 5. 3. «Гнездовой» алгоритм Винограда
- 1. 6. Сопоставление алгоритмов быстрого преобразования Фурье
- 1. 6. 1. Объем вычислений
- 1. 6. 2. Объем памяти
- 1. 6. 3. Эффекты конечной разрядности
- 2. 1. Теоретические основы предлагаемого метода
- 2. 1. 1. Свойство цикличности свертки
- 2. 1. 2. Транспозиция алгоритма
- 2. 1. 3. Метод решения системы линейных уравнений, когда уравнений больше, чем неизвестных
- 2. 2. Синтез прямоугольных преобразований
- 2. 2. 1. Синтез матриц, А и В
- 2. 2. 2. Вычисление матрицы С
- 2. 2. 3. Пример синтеза
- 2. 3. Вопросы реализации предлагаемого метода на ЭВМ
- 2. 4. Оценка мультипликативной сложности новых алгоритмов быстрого преобразования Фурье
- 3. 1. Введение алгебры над алгебраическими расширениями
- 3. 2. Швод базового алгоритма
- 3. 3. Оценка вычислительной сложности
- 3. 4. Синтез прямоугольных преобразований над полем корней
- 3. 5. Синтез прямоугольных преобразований над полем корней 8-ой степени из единицы. Ю
- 3. 6. Оценка вычислительной сложности новых алгоритмов для преобразования многомерных последовательностей. Ю
- 3. 7. Синтез прямоугольных преобразований над полем чисел Эйзенштейна
- 4. 1. Применение дискретного преобразования Фурье в устройствах сопряжения
- 4. 2. Разработка теоретических вопросов
- 4. 2. 1. Модификации алгоритма простых множителей для действительных и эрмитово-симметричных последовательностей
- 4. 2. 2. Анализ вычислительных ошибок алгоритма простых множителей в системе счисления с фиксированной запятой
- 4. 2. 3. Эффективная программная реализация умножений в алгоритмах быстрого преобразования Фурье коротких последовательностей
- 4. 3. Синтез и анализ алгоритмов быстрого преобразования Фурье для N =14, 28, 72 и
- 4. 3. 1. Синтез базовых алгоритмов
- 4. 3. 2. Объем вычислений
- 4. 3. 3. Анализ вычислительных ошибок
- 4. 4. Разработка процессора 144-точечного быстрого преобразования Фурье для цифрового многоканального модема
- 4. 4. 1. Шчислительный алгоритм. I?
- 4. 4. 2. Вычислительные ошибки. Выбор разрядности процессора
- 4. 4. 3. Моделирование процессора быстрого преобразования Фурье на ЭВМ
- 4. 4. 4. Описание работы процессора
- 4. 4. 5. Основные параметры процессора быстрого преобразования Фурье
- 4. 5. Разработка эффективного алгоритма тактовой синхронизации цифрового многоканального модема
Список литературы
- Материалы ХХУ1 съезда КПСС. — М.: Политиздат, 1981. — 223 с.
- Гольденберг Л.М., Матюшкин Б. Д., Поляк М. Н. Цифровые устройства сопряжения (трансмультиплексоры) в системах связи. Электросвязь, 1980, № I, с. 28 — 33.
- Применение цифровой обработки сигналов./Под редакцией Оппен-гейма Э. М.: Шр, 1980. — 552 с. 4.0ппенгейм A.B., Шафер Р. В. Цифровая обработка сигналов. М.: Связь, 1979. — 416 с.
- Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. М.: Мир, 1978. — 848 с.
- HLtosa&i Б. an. Ottfio^onaBEij mattipitocid Qum Sutern lluricj the DLsc/iete ioime* (Puuisfotm.- IEEE Tians. Common., ?981, v.29, № 7, p. 982−989.7.3аездный A.M. и др. Аппаратура передачи дискретной информации MC-5. М.: Связь, 1970.
- Азарова Л.Г. и др. Высокоскоростной многоканальный модем. -Электросвязь, 1978, № 6, с. 61 64.
- Изыскание принципов построения модема для передачи цифровой информации со скоростью 480 кбит/с по вторичным групповым трактам аппаратуры с частотным разделением каналов. Отчет, № гос. per. 78 014 560.: Одесса, 1980.
- Отчет о НИР «Трест». Подготовительная стадия. № гос. per. Я35 485.: Уфа, 1983. 306 с. 1. CooEetj 1 W. and IW. OLn Cityouthm -the machine
- Calculation of Comp^x Joints Teiles. fflath. of Compat., 1965, ч. {9, Opxi?, p. ?97−301.
- Slajtetoa R.C. un. -j-ог Computing the miatd Radix 9dst Jouxiei Ttansj-oxm. IEEE Txans. CLudio and tEecfetoacoast., 1969, vJ7, N2 2, p. 95 405.
- ЬегаСапо! G-.D. Q fast Jouxiet <3Ws-fotm aEj-OtltKm IXsino Base 8 Metatlons.-(Tlath.oj Comput, v. 22, № 402, p. 275 ?79.
- Капорин И.Е. Новый алгоритм быстрого преобразования Фурье. -Журнал вычислительной математики и математической физики, 1980, т. 20, № 4, с. 1054 1058.
- Макклеллан Дж.Х., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983. — 264 с. 16. dolama <Г., mano Т. et at. <2.0-Channel itansmu&l-phxii Dfcsion and ietjtftmanee. -IEEE Ttans. Commnn1980, v. 28, № 9, p. 4Т09-Ш7.
- Cloy.ama <Г., ГПало Т., NaMalaij (isliL К. Ctn txpeximen-ta? fDm-iDm (ПапзтиШр^еойег Using Cmos ASI
- Cltcaits. ReuLtur o-J the? Eechuca? Communication Lafcoxato’ue.s, <980, v. 28, NM-2, p. 4-Z7.
- Borineaot (fiat ГЛ., Sena P., maltu X. 60-Cfian.net fransmufctlpEexex with *>8?5 Нг signafcfcincj. — Commimi-cation uxansrnUsion, 19?0, N4, p. 81−9 2.
- Peltoni D. Plmensioruttaa^ «on digitadam-cFDm Taansmuttlpiexein nach dex mijpKastametHodt. Ph.D. cUssextatLon, ЕТИ? aiich, Swit^ntand, № 628 3, <979.
- Wafeafcajaski K. ri at. TDm- fDm iaaasmultiptereilUina a DiaiM Signal (PxocewtyL .-IEEE Ttaas. Corn-man, 1982, y.30, M*7. p.1552- 1559.
- Ros^itet CT J. /7?. et at a tTiodaHaz fTjcunirruLttiphxii
- Шойерманн X., Геклер X. Систематизированный обзор цифровых методов преобразования вида уплотнения каналов. ТИИЗР, 198I, т. 69, № II, с. 52 — 84.
- Webb. P. T>. Q Jicced Point 3ast 3outU/i (PuLnijozm butov CUtafo^is. — IEEE (Ггапл. OumdLo and E&cttoatou.s'f., 1969, v. 47, г, p. 451- 157.
- Reddty V.U., Suncictaa. mu/L-tfiy т. oj СогоАра&огг fettureen (Piancatuon Etiois ok Tlxed iolrit Tcut iomiti TiaruWm fcxaoi Clnafysi.* .-IEEE foarvb. Circaits arid litems, 4980, v. 11, N* 8, р.74г-Т4С.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. — 536 с.
- Байкова А.Т. О вычислении дискретного преобразования Фурье. -Рукопись представлена Ленинградским электротехническим институтом связи. Деп. в ВИНИЩ 04.07.83, № 3652 83 Деп. — 23 с.
- Байкова А.Т. 0 вычислении круговой свертки коротких последо вательностей. Обработка информации в системах связи: Сборник научных трудов учебных институтов связи. JI.: изд. ЛЗДС, 1984, с. 36 — 43.
- Ван дер Варден В. Л. Алгебра. М.: Наука, 1976. — 648 с.
- Курош А.Г. Курс высшей алгебры. М.: Наука, 1975. — 432 с.
- Каргаполов М.И., Мерзляков Ю. И. Основы теории групп. М.: Наука, 1982. — 288 с.
- Виноградов И.М. Основы теории чисел. М.: Наука, 1981. -176 с.
- C.S. bdex malinas jot Wi^tic (?men<>iona?
- FoimuBatCon of the T> FT anol Cont otation. IEEE ftans. Ctcoust., Speech, Stqn.^ioc., № 17, v. 25 Me Ъ
- Бовбель Е.И., Зайцева E.M., Микулович В. И. Ошибки цифровых систем, основанных на вычислении дискретного преобразования Фурье. Зарубежная радиоэлектроника, 1981, № 5, с. 3 — 25.
- Байкова А.Т. Вычислительные ошибки цифровых устройств, реализующих дискретное преобразование Фурье в системе счисленияс фиксированной запятой. Рукопись депонирована в ВИМИ 27.04. 84, № Д5 885. — 48 с.
- Wiaojmd s. Some В&пеаг Fotms Whose mufctipticatibe Complexity Depends on the Tudd o (Constants. (Tlath. Syst. iTKeoxy, 1977, №{0, p. 469−480.
- Кпаербоут Д.Ф. Теоретические основы обработки геофизической информации. М.: Недра, 1981. 304 с.
- Байкова А.Т. Об одном методе эффективного вычисления циклической свертки и дискретного преобразования Фурье. Техника средств связи, серия ТПС, 1983, вып. 9, с. 108 — 117.
- Rcddy П.S., Redctu i/.U. Complex ReetcinauCat (Гшпф*гщ fat DLaiiat Convocation. IE? E IPianv toast., Sptedi, SCjn. Hoz., 19 80, v. 28, p. 592.-596.58. 9еге№ P.m., Ray пег Pg. w. Cl TXuLtat? fcock рюсмьогог modulation and demodulation. -I EE E
- Tians. Commun1975, j. 25, 2, p. 282−286.59. тага! а Тото^сшгск, а. (Хп Хтро"гео (те (Ьос (^0г ска^аб 5 $В-?Т>т тосЫаиоп <�хгс1 ¿-егтЫЛайоп 1Е ЕЕ Тясми. Согшпап., 4978, v. 26, р. 720−725,
- ЗакаКаЙ (кюЬ V. ^ а£. Эел^ортел* а 11>т/ ТРтагктиШрСеосег. X Е Е Е (Ггапз. Соттст., <978, р.728−7ЪЪ.
- ВйЬапаег/П., 1>айие±- 1 .Ь ?ГТ>177-?3)т 1гаг^гпиЖ-рЕехег: бфщйае °МирКа$е. ап<4? 1ЕЕЕ 5гапл. Соттип., <974, V 22, № 9, р. ^99 4204.
- Байкова А.Т. Эффективные алгоритмы дискретного преобразования Фурье для многоканальных устройств с цифровой обработкой сигналов. Техника средств связи, серия ТПС, 1983, вып. 3, с. 128 -137.
- Dtspain Cl. m. l/ety 7
- Байкова A.T. Об использовании эффективных методов поворота вектора при реализации дискретного преобразования Фурье. Обработка информации в системах связи: Сборник научных трудов учебных институтов связи. Л.: изд. ЛЖ, 1983, с. 72 — 78.
- Байкова А.Т., Ряхин Е. М. Быстродействующий безумножительный процессор дискретного преобразования Фурье г Техника средств связи, серия ТПС, 1984, вып. 3.
- СШ. t. m. a ffiah-^peedIT ?гош>ШIE Е Е fians. Commun., <978, v. ?6, № 5, p. 690−696,73.3аездный A.M., Окунев Ю. Б., Рахович Л. М. Фаз о-разностная модуляция. М.: Связь, 1967. — 304 с.
- Гинзбург В.В., Каяцкас A.A. Теория синхронизации демодуляторов. М.: Связь, 1974. — 216 с.