Парктер - McClellan сүзгісін жобалау алгоритмі - Parks–McClellan filter design algorithm

Parks – McClellan алгоритмімен жасалған сүзгінің өту және тоқтау жолақтары
Y осі - жиіліктік жауап H(ω) және х осі әр түрлі радиан жиіліктері, ωмен. Х осінде белгіленген екі жиіліктің, ωб және ωс. ωб өткізу жолағының кесу жиілігін және ωс тоқтау жолағының кесу жиілігін көрсетеді. Жоғарғы сол жақтағы сызық тәрізді толқын - бұл өту жолағының толқыны, ал төменгі оң жақтағы толқын - тоқтау жолағының толқыны. Графиктің жоғарғы сол жағындағы екі үзік сызық δ белгісін көрсетедіб және төменгі оң жақта екі үзік сызық δ көрсетедіс. Тізімдегі барлық басқа жиіліктер жиілікке жауап беру сызбасының экстремалды жиілігін көрсетеді. Нәтижесінде алты экстремалды жиілік бар, содан кейін біз жалпы жиілікте сегіз экстремалды жиілік беру үшін өту диапазонын және тоқтау жиілігін қосамыз.

The Парктер - МакКлеллан алгоритмі, жариялаған Джеймс МакКлеллан және Томас Паркс 1972 жылы оңтайлы Чебышевті табудың қайталанатын алгоритмі болып табылады соңғы импульстік жауап (FIR) сүзгі. Parks - McClellan алгоритмі тиімді және оңтайлы FIR сүзгілерін жобалау және енгізу үшін қолданылады. Мұнда оңтайлы сүзгі коэффициенттерін табудың жанама әдісі қолданылады.

Алгоритмнің мақсаты - Чебышевтің жуықтауы арқылы өту және тоқтау жолақтарындағы қателіктерді азайту. Parks – McClellan алгоритмі –ның вариациясы Ремез алмасу алгоритмі, FIR сүзгілері үшін арнайы жасалған өзгерісімен. Бұл FIR сүзгісін жобалаудың стандартты әдісі болды.

FIR сүзгісін оңтайлы жобалау тарихы

1960 жылдары аналогты сүзгіні жобалау саласындағы зерттеушілер Чебышевтің жуықтауы сүзгіні жобалауға арналған. Осы уақыт ішінде ең жақсы сүзгілерде эквиваленттік сипаттама болатындығы белгілі болды эллиптикалық сүзгі (немесе Cauer сүзгісі) Чебышевтің жуықтауына қатысты оңтайлы болды. 1960 жылдары цифрлық сүзгі төңкерісі басталған кезде зерттеушілер а екі сызықты түрлендіру шығару шексіз импульстік жауап (IIR) сандық эллиптикалық сүзгілер. Олар сондай-ақ FIR сүзгілерін жобалаудың бірдей сүзгі тапсырмасын орындау мүмкіндігін мойындады және көп ұзамай Чебышев жуықтауын қолданып FIR оңтайлы сүзгісін іздеу басталды.[1]

Математикада да, техникада да оңтайлы жауап эквиваленттік мінез-құлықты көрсететіні және толқындардың санын Чебышевтің жуықтауы арқылы санауға болатындығы белгілі болды. 1962-1971 жылдар аралығында Чебышев FIR оңтайлы сүзгісін жобалау бағдарламасын жасау бойынша бірнеше әрекет жасалды.[1] Көптеген талпыныстарға қарамастан, көбісі алгоритмдік іске асырудағы проблемалардан немесе проблемаларды құрастырудан туындағандықтан сәтсіз аяқталды. Мысалы, Отто Херрманн эквивалентті фильтрлерді жобалау әдісін ұсынды, оның шеттері шектеулі.[1] Бұл әдіс сызықтық емес теңдеулер жиынтығын шешу арқылы толқындардың максималды санымен эквиваленттік жиіліктік реакцияны алды. Сол кезде енгізілген тағы бір әдіс Чебышевтің оңтайлы жуықтауын жүзеге асырды, бірақ алгоритм салыстырмалы түрде төмен ретті сүзгілерді жобалаумен шектелді.[1]

Германның әдісіне ұқсас, Эд Хофстеттер FIR сүзгілерін мүмкіндігінше толқындармен жобалайтын алгоритм ұсынды. Бұл Ripple максималды алгоритмі ретінде белгілі болды. Максималды Ripple алгоритмі интерполяция арқылы ауыспалы қателік шартын қойды, содан кейін айнымалы шешім қанағаттандыруы керек теңдеулер жиынтығын шешті.[1] Максималды Ripple алгоритмінің бір маңызды шектеулері жолақтың жиектері жобалау процедурасына кірулер ретінде көрсетілмегендігінде болды. Керісінше, бастапқы жиілік {ωмен} және қажетті функция Д.(ωмен) өту және тоқтау жолағын анық емес түрде анықтады. Оңтайлы сүзгіні жобалаудың алдыңғы әрекеттерінен айырмашылығы, Maximal Ripple алгоритмі жиілік жиынын табуға тырысқан алмасу әдісін қолданды {ωмен} мұнда ең жақсы сүзгінің толқындары болды.[1] Осылайша, Ripple максималды алгоритмі оңтайлы сүзгі дизайны болған жоқ, бірақ Parks-McClellan алгоритмінің тұжырымдалуына айтарлықтай әсер етті.

Тарих

1970 жылдың тамызында Джеймс МакКлеллан Райс университетінің аспирантурасына аналогтық сүзгі дизайнының математикалық модельдеріне шоғырланып түсіп, фильтр дизайнына қызығушылығының арқасында «Сандық сүзгілер» атты жаңа курста оқыды.[1] Курсты Томас Паркс және Сид Буррус. Ол кезде DSP дамып келе жатқан сала болды, нәтижесінде дәрістерге жақында жарияланған ғылыми жұмыстар жиі қатысады. Келесі семестрде, 1971 жылдың көктемінде Томас Паркс «Сигнал теориясы» курсын ұсынды, оны Макклеллан да оқыды.[1] Семестрдің көктемгі демалысында Паркс конференцияға қатысу үшін Хьюстоннан Принстонға қарай жүрді, онда Эд Хофстеттердің FIR сүзгісін жобалаудың жаңа алгоритмі (Максималды толқындық алгоритмі) туралы презентациясын тыңдады. Ол Хофстеттердің, Оппенгеймнің және Сигелдің қағаздарын Хьюстонға алып келді, FIR сүзгілерін жобалау үшін Чебышевтің жуықтау теориясын қолдану мүмкіндігі туралы ойлады.[1] Ол Хофстеттердің алгоритмінде жүзеге асырылған әдіс Ремез алмасу алгоритміне ұқсас екенін естіп, Ремез алмасу алгоритмін қолдану жолымен жүруге шешім қабылдады. «Сигналдар теориясы» курсының студенттеріне жоба жасау керек болды, өйткені Чебышевтің жуықтауы курстың басты тақырыбы болғандықтан, бұл жаңа алгоритмді енгізу Джеймс МакКлелланның курстық жобасы болды. Бұл, сайып келгенде, оңтайлы Чебышев жуықтау теориясын және тиімді іске асыруды қамтитын Parks-McClellan алгоритміне алып келді. Көктемгі семестрдің соңында МакКлеллан мен Паркс FIR сүзгілері үшін Remez алмасу алгоритмінің вариациясын жазуға тырысты. Әзірлеуге шамамен алты апта уақыт қажет болды және кейбір оңтайлы сүзгілер мамыр айының соңында сәтті жасалған болатын.

Джеймс МакКлеллан және Томас Паркс

Джеймс МакКлеллан 1947 жылы 5 қазанда дүниеге келген Гуам. Ол өзінің ғылым бакалавры Электротехника (1969) бастап Луизиана мемлекеттік университеті.[2] Ғылым магистрі (1972) және докторантурасын (1973) алғаннан кейін Райс университеті, Доктор Макклеллан MIT Линкольн зертханасында 1973 жылдан 1975 жылға дейін жұмыс істеді.[2] 1975 жылы MIT электротехника және информатика кафедрасының профессоры болды.[2] Университетте жеті жыл жұмыс жасағаннан кейін доктор МакКлеллан қосылды Шлумбергер 1982 жылы, онда бес жыл жұмыс істеді.[2] 1987 жылдан бастап доктор Макклеллан электр энергетикасының профессоры Джорджия технологиялық институты.[2] Доктор Макклеллан цифрлық жұмысы үшін көптеген марапаттарға ие болды сигналдарды өңдеу және оны сенсорлық массивті өңдеуге қолдану: IEEE Signal Processing Technical Achievement Award (1987), IEEE Signal Processing Society Award (1996) және IEEE Jack S. Kilby Signal Processal Medal (2004).[1] Доктор Макклеллан алған марапаттарынан басқа бірқатар маңызды әдебиеттерді жариялады: MATLAB 5 (1994), DSP First (1997), Signal Processing First (2003) және DSP-дегі сан теориясы (1979).[1]

Томас Паркс 1939 жылы 16 наурызда Нью-Йорктегі Буффало қаласында дүниеге келген. Ол бакалавр (1961), ғылым магистрі (1964) және электротехника ғылымдарының докторы (1967) дәрежелерін алды Корнелл университеті.[3] Докторлық паркті докторантурамен бітіргеннен кейін Райс университетінің факультетіне қосылды. Ол 1967-1986 жылдары Корнелл университетінің факультетіне кірген кезде оқытушы болды.[3] Доктор Паркс - сандық сигналдарды өңдеуге бағытталған зерттеулерінің негізінде бірнеше марапаттардың иегері сигнал теориясы, көп деңгейлі жүйелер, интерполяция және фильтр дизайны: IEEE ASSP қоғамының техникалық жетістігі сыйлығы (1981), IEEE ASSP қоғамы сыйлығы (1988), Райс университетінің президентінің сыйлығы (1999), IEEE үшінші мыңжылдық медалі (2000) және IEEE Джек С. Килби сигналды өңдеу медалы (2004) ).[1] Доктор Паркс алған марапаттарынан басқа, электротехника саласындағы көптеген еңбектерін жариялады: DFT / FFT конволюциясының алгоритмдері (1985), цифрлық сүзгілерді жобалау (1987), TMS 32010 пайдалану цифрлық сигналдарды өңдеу зертханасы (1988) , TMS 320C25 (1990), сигналдарды өңдеуге арналған компьютерлік жаттығулар (1994) және MATLAB 5 (1994) арқылы сигналдарды өңдеуге арналған компьютерлік жаттығулар қолданылған цифрлық сигналдарды өңдеу зертханасы.[1]

Алгоритм

Парктер - Макклеллан алгоритмі келесі қадамдарды қолдану арқылы жүзеге асырылады:[1]

  1. Инициализация: экстремалды жиіліктер жиынын таңдаңыз {ωмен(0)}.
  2. Соңғы жиынтыққа жуықтау: қазіргі экстремалды жиынтықтағы ең жақсы Чебышев жуықтамасын есептеп шығарыңыз, δ(м) қазіргі экстремалды жиынтықтағы мин-макс қатесі үшін.
  3. Интерполяция: Қате функциясын есептеңіз E (ω) (2) көмегімен жиіліктердің барлық жиынтығы бойынша.
  4. Жергілікті максимумдарды іздеңізE(м)(ω)| жиынтықта Ω.
  5. Егер максимум(ωεΩ)|E(м)(ω)| > δ(м), содан кейін экстремалды жиынтығын {-ге дейін жаңартыңызωмен(m + 1)} жаңа жиіліктерді таңдау арқылы, мұндағы |E(м)(ω)| оның жергілікті максимумдары бар. Қатенің реттелген жиіліктер жиынтығында (4) және (5) суретте көрсетілгендей кезектесіп тұрғанына көз жеткізіңіз. 2-қадамға оралып, қайталаңыз.
  6. Егер максимум(ωεΩ)|E(м)(ω)| ≤ δ(м), содан кейін алгоритм аяқталды. {Ω жиынтығын пайдаланыңызмен(0)} және фильтр коэффициенттерін алу үшін кері дискретті Фурье түрлендіруін есептеуге арналған интерполяция формуласы.

Парктер - Макклеллан алгоритмі келесі қадамдармен өзгертілуі мүмкін:[4]

  1. L + 2 экстремалды жиіліктері туралы алғашқы болжам жасаңыз.
  2. Берілген теңдеуді пайдаланып δ есептеңіз.
  3. Lagrange Интерполяциясын қолдана отырып, біз өткізу жолағы мен аялдама жолағының үстінен A (ω) сынамаларының тығыз жиынтығын есептейміз.
  4. L + 2 ең үлкен экстремасын анықтаңыз.
  5. Егер ауысым теоремасы қанағаттандырылмаса, онда (2) -ге оралып, ауыспалы теорема орындалғанға дейін қайталаймыз.
  6. Егер кезектестіру теоремасы қанағаттандырылса, онда h (n) -ді есептейміз және аяқтаймыз.

Жоғарыда айтылған Парктер - Макклеллан алгоритмі туралы негізгі түсінік алу үшін жоғарыдағы алгоритмді қарапайым түрде келесідей түрде жаза аламыз:

  1. Экстреманың позициялары өту және тоқтау жолағында біркелкі орналасады.
  2. Полиномдық интерполяцияны орындаңыз және жергілікті экстреманың позицияларын қайта бағалаңыз.
  3. Экстреманы жаңа позицияларға жылжытыңыз және экстреманың ауысуын тоқтатқанға дейін қайталаңыз.

Түсіндіру

Оң жақтағы суретте көрсетілген сюжет үшін әртүрлі экстремалды жиіліктер көрсетілген. Экстремалды жиіліктер - бұл тоқтау және өту жолақтарындағы максималды және минималды нүктелер. Тоқтату жолағының толқыны - бұл учаскенің төменгі оң жағындағы толқындардың төменгі бөлігі және өту жолағының толқыны - бұл учаскенің жоғарғы сол жағындағы толқындардың жоғарғы бөлігі. Сызба бойынша өтетін үзік сызықтар δ немесе максималды қатені көрсетеді. Экстремалды жиіліктердің орналасуын ескере отырып, оңтайлы δ немесе оңтайлы қатенің формуласы бар. Біз бірінші әрекеттегі оңтайлы δ немесе экстреманың нақты орындарын білмегендіктен, қайталаймыз. Тиімді түрде біз бастапқыда экстреманың позициясын қабылдаймыз және δ есептейміз. Содан кейін біз экстреманы қайта бағалап, жылжытып, δ немесе қатені қайта есептейміз. Біз бұл процесті δ өзгеруін тоқтатқанға дейін қайталаймыз. Алгоритм δ қатесінің жинақталуына әкеледі, әдетте он-он екі қайталау.[5]

Қосымша ескертпелер

Чебышевтің жуықтамасын қолданбас бұрын бірнеше қадамдар қажет болды:

  1. Жақындау үшін базалық функция жиынын анықтаңыз, және
  2. Өткізгіш сүзгілердің өту және тоқтату жолақтары әрқашан өтпелі аймақтармен бөлінетіндігін пайдаланыңыз.[1]

FIR сүзгілерін косинустың қосындысына дейін азайтуға болатындықтан, барлық негізгі сызықтық фазалық FIR сүзгілерін орындау үшін бірдей негізгі бағдарламаны қолдануға болады. Максималды Ripple тәсілінен айырмашылығы, енді жолақтың шеттерін алдын-ала анықтауға болады.

Parks-McClellan алгоритмін қолдана отырып, оңтайлы сүзгі дизайнын тиімді жүзеге асыру үшін екі қиындықты жеңу керек:

  1. Икемді айырбас стратегиясын анықтау және
  2. Қатты интерполяция әдісін енгізу.[1]

Белгілі бір мағынада бағдарламалау FIR сүзгісін жобалауда қолдану үшін белгілі алгоритмді іске асыруға және бейімдеуге қатысты болды. Бағдарламаны тиімді ету үшін алмасу стратегиясының екі түрі алынды:

  1. Өту және тоқтау жолақтары арасындағы экстремалды жиіліктерді бөлу, және
  2. Бағдарлама қайталанған кезде жолақтар арасындағы экстремалды қозғалысты қамтамасыз ету.[1]

Инициализация кезінде өту және тоқтау жолағындағы экстремалдар санын жолақтар өлшемдерінің қатынасын қолдану арқылы тағайындауға болады. Сонымен қатар, өткізу және тоқтату жиектері әрдайым экстремалды жиынтықта орналасатын еді, ал бағдарламаның логикасы осы жиіліктерді экстремалды жиында ұстап тұрды. Жолақтар арасындағы қозғалыс барлық үміткерлердің экстремалды жиіліктеріндегі қателіктердің мөлшерін салыстыру және ең үлкенін қабылдау арқылы басқарылды. Алгоритмнің екінші элементі қателік функциясын бағалау үшін қажет интерполяция сатысы болды. Олар Лагранж интерполяциясының барицентрлік формасы деп аталатын әдісті қолданды, ол өте берік болды.

Parks - McClellan алгоритмінің барлық шарттары Чебышевтің ауыспалы теоремасына негізделген. Ауыстыру теоремасы максималды қатені минимумға жеткізетін L дәрежесінің көпмүшесі кем дегенде L + 2 экстремасына ие болатынын айтады. Оңтайлы жиілік реакциясы максималды шектерге әрең жетеді.[5] Экстрема жолдың өту және тоқтау шеттерінде және ω = 0 немесе ω = π немесе екеуінде де болуы керек. L дәрежесіндегі полиномның туындысы L-1 дәрежелі көпмүше, L-1 орындарында көп дегенде нөлге тең болуы мүмкін.[5] Сонымен, жергілікті экстремалардың максималды саны - L-1 жергілікті экстремасы және 4 жолақты жиектер, жалпы L + 3 экстремасы.

Әдебиеттер тізімі

  1. ^ а б c г. e f ж сағ мен j к л м n o б q МакКлеллан, Дж. Х .; Парктер, Т.В. (2005). «Парктердің жеке тарихы-Mc Клеллан алгоритм ». IEEE сигналдарды өңдеу журналы. 22 (2): 82–86. Бибкод:2005ISPM ... 22 ... 82M. дои:10.1109 / MSP.2005.1406492.
  2. ^ а б c г. e МакКлеллан, Джеймс (1997), Джеймс МакКлеллан профилі, алынды 2009-03-28
  3. ^ а б Парктер, Томас (2006), Корнелл университетінің электротехникалық және компьютерлік инженерия мектебі, алынды 2009-03-28
  4. ^ Джонс, Дуглас (2007), Парктер - McClellan FIR сүзгісі дизайны, алынды 2009-03-29
  5. ^ а б c Ловелл, Брайан (2003), Саябақтар - Макклеллан әдісі (PDF), алынды 2009-03-30

Қосымша сілтемелер

Келесі қосымша сілтемелер парктер - Макклеллан алгоритмі туралы, сондай-ақ Джеймс МакКлеллан мен Томас Паркс жазған басқа зерттеулер мен мақалалар туралы ақпарат береді:

  1. Сызықтық фазалы рекурсивті емес цифрлық сүзгілерге арналған Чебышевтің жақындауы
  2. Саябақтар туралы қысқаша анықтама - MATLAB көмегімен FIR төмен өту сүзгілерін жобалау - МакКлеллан
  3. DSP-ге кіріспе
  4. MathWorks MATLAB құжаттамасы
  5. ELEC4600 Дәріс туралы ескертпелер
  6. C кодын енгізу (LGPL лицензиясы) - Джейк Яновец
  7. Айова-Хиллз бағдарламалық жасақтамасы. «C кодының мысалы». Алынған 3 мамыр 2014.
  8. Алгоритм қайта қаралған және кеңейтілген McClellan, Parks, & Rabiner, 1975; Fortran коды.