Розглядається алгоритм сліпого пошуку спільної оцінки повідомлення і імпульсної характеристики каналу по решітці зі зменшеним числом станів. Даний алгоритм може використовуватися, якщо імпульсна характеристика каналу зв'язку з помірними межсимвольной інтерференцією і ставленням сигнал / шум має значну довжину. Приведено докладний опис алгоритму, представлені експериментальні результати досліджень його якісних показників.

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Наталине А.Б., Сергієнко А.Б.


Reduced Trellis Search Algorithm of Joint Data and Channel Estimation for Quadrature Amplitude Modulation and Trellis Coded Modulation

Blind trellis search algorithm for joint channel and data estimation with reduced computational complexity is presented. This method is useful for channels with long impulse responses, moderate intersymbol interference and signal-to-noise ratio. Algorithm description and experimental results are presented and discussed.


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2004
    Журнал
    Известия вищих навчальних закладів Росії. Радіоелектроніка
    Наукова стаття на тему 'АЛГОРИТМ ПОШУКУ СПІЛЬНОЇ ОЦІНКИ ПОВІДОМЛЕННЯ І імпульсної характеристики КАНАЛУ ПО РЕШІТЦІ зі зменшенням числа станів ДЛЯ СИГНАЛОВ З квадратурного амплітудної модуляції і сигнальних-КОДОВИХ КОНСТРУКЦІЙ'

    Текст наукової роботи на тему «Алгоритм ПОШУКУ СПІЛЬНОЇ ОЦІНКИ ПОВІДОМЛЕННЯ І імпульсної характеристики КАНАЛУ ПО РЕШІТЦІ зі зменшенням числа станів ДЛЯ СИГНАЛОВ З квадратурного амплітудної модуляції і сигнальних-КОДОВИХ КОНСТРУКЦІЙ»

    ?бібліографічний список

    1. Radar Cross Section Handbook / G. T. Ruck, D. E. Barrick, W. D. Stuart, D. E. Krichbaum. N. Y. - London: Plenium Press, 1970. 949 p.

    2. Потєхін О. І. Деякі задачі дифракції електромагнітних хвиль. М .: Сов. радіо, 1948. 134 с.

    3. Моделювання та випробування радіообладнання / Под ред. В. І. Винокурова. Л .: Суднобудування, 1981. 304 с.

    V. A. Vinogradov, V. V. Leontiev

    Saint Petersburg state electrotechnical university "LETI"

    Radar Cross Section of Truncated Parabolic Cylinder

    The formula for radar cross section of the metallic cylinder with parabolic cross section by means of the physical optics technique is obtained.

    Radar cross section, physical optics method, truncated parabolic cylinder

    Стаття надійшла до редакції 5 березня 2004 р.

    УДК 621.396.2

    А. Б. Наталине, А. Б. Сергиенко

    Санкт-Петербурзький державний електротехнічний

    університет "ЛЕТІ"

    Алгоритм пошуку спільної оцінки повідомлення і імпульсної характеристики каналу по решітці зі зменшеним числом станів для сигналів з квадратурної амплітудної модуляцією і сигнально-кодових конструкцій

    Розглядається алгоритм сліпого пошуку спільної оцінки повідомлення і імпульсної характеристики каналу по решітці зі зменшеним числом станів. Даний алгоритм може використовуватися, якщо імпульсна характеристика каналу зв'язку з помірними межсимвольной інтерференцією і ставленням сигнал / шум має значну довжину. Приведено докладний опис алгоритму, представлені експериментальні результати досліджень його якісних показників.

    Сліпа оцінка каналу, сліпе вирівнювання, вирівнювання каналу, метод найменших квадратів, декодер Вітербо

    Передача сигналів в цифрових системах зв'язку на практиці проводиться по аналоговим каналам зв'язку, що вносить спотворені дані. Це призводить до виникнення межсимвольной інтерференції (МСІ) на приймальній стороні і може служити-

    34

    © А. Б. Наталине, А. Б. Сергиенко, 2004

    ====================================== Известия вузів Росії. Радіоелектроніка. 2004. Вип. 2

    жити причиною появи помилок на виході приймача. Щоб компенсувати виникаючі спотворення, необхідно проводити вирівнювання каналу або оцінку його імпульсної характеристики, що дозволить згодом найбільш достовірно відновити прийняті символи. Один з часто застосовуваних на практиці методів полягає в тому, що вирівнювання і оцінка імпульсної характеристики каналу (ІХК) грунтуються на відомій приймача навчальної послідовності, яка передається передавачем на початку кожного сеансу зв'язку. Однак в деяких додатках, таких, наприклад, як багато користувачів мережу, передача навчальної послідовності для кожного знову підключився користувача привела б до різкого падіння середньої швидкості передачі. В цьому випадку використовуються методи сліпого вирівнювання і оцінки ІХК.

    Методи сліпого вирівнювання в порівнянні з субоптимальність сліпими алгоритмами оцінок ІХК вимагають набагато меншого обсягу обчислень при практичній реалізації, але мають на 1-2 порядки більший час збіжності. Крім того, багато методи сліпого вирівнювання принципово не можуть працювати, якщо коефіцієнт передачі каналу має нулі в частотної області [1].

    Однією з найбільш популярних оцінок параметрів є оцінка по максимуму правдоподібності (МП). До переваг МП-оцінок можна віднести швидку збіжність і мінімальну потенційно досяжну дисперсію оцінюваного параметра, а основним їх недоліком є ​​великі обчислювальні витрати. Існує два основні підходи для формування МП-оцінок ІХК: стохастичний та детермінований [2]. У першому випадку мається на увазі, що передані дані представляють собою випадковий вектор з відомим розподілом і оцінкою підлягає тільки ІХК, у другому випадку оцінюються і дані, і ІХК.

    Метод спільної оцінки каналу і даних був вперше запропонований Сешадрі [3]. Представлені в [3] алгоритми призначені для обробки сигналів з амплітудною маніпуляцією, проте їх можна легко узагальнити на випадок сигналів з квадратурної амплітудної модуляцією (КАМ). В [3] запропоновано формувати оцінку даних на основі узагальненого алгоритму Вітербо (ОАВ), а оцінку ІХК - за допомогою методу найменших квадратів (МНК) для кожного продолжаемого шляху в ОАВ. Для зменшення обчислювальної навантаження в [3] запропонований алгоритм, в якому число шляхів в решітці ОАВ інваріантної до розміру сигнального сузір'я і так само М | 4Ь, де М - число рішень для кожного стану ОАВ, а Ь - довжина ІХК. Однак легко бачити, що з ростом довжини ІХК Ь цей алгоритм швидко стає нереалізованим на практиці.

    У цій статті розглядається алгоритм спільної оцінки ІХК і даних зі зменшеним числом станів решітки ОАВ, при цьому обчислювальна навантаження инвариантна до довжини ІХК. Загальна кількість шляхів в решітці одно МИ, де N - розмір сузір'я для КАМ-сигналів або число станів для сигнально-кодових конструкцій (СКК).

    Модель каналу зв'язку (рис. 1). Прийнятий сигнал г \ може бути записаний у такий спосіб:

    Ь-1

    гк = Е ак -гІг + пк

    г = 0

    (1)

    Джерело {аг}

    даних

    Канальні спотворення {Іг},

    шум {пг}

    {Г}

    формування оцінок

    {І}

    {Аг}

    Мал. 1

    На малюнку {а /} - випадкова послідовність статистично незалежних комплексних чисел, равновероятно обираних з сигнального сузір'я; {І /} - невідомі коефіцієнти ІХК; {П /} - послідовність відліків нормального дискретного "білого" шуму.

    Передбачається, що частота дискретизації приймача дорівнює символьної швидкості і тимчасова синхронізація вже досягнута. Слід зазначити, що описаний в статті алгоритм може бути легко узагальнено на випадок, коли частота дискретизації приймача в ціле число разів перевищує символьну швидкість.

    Рівність (1) може бути переписано у вигляді Гк = а | І + Пк,

    де Гк = {гк, Гк-1, ..., Гк-ь + 1 ^ - вектор-стовпець відліків прийнятого сигналу;

    ак = {ак, ак-1, •••, ак-ь + 1 ^ - вектор-стовпець інформаційної послідовності;

    І = {Іо, І \, ..., іь-1 ^ - вектор-стовпець коефіцієнтів ІХК;

    Пк = {пк, пк-1, •••, пк-Ь + 1 ^ - вектор-стовпець шумових відліків; "Т"

    - символ транспонування.

    Завдання алгоритму оцінки каналу полягає в тому, щоб знайти оцінку вектора ІХК І. Потім, використовуючи знайдену оцінку І, можна знайти оцінку послідовності даних {а /}.

    Опис алгоритму. Число станів в решітці алгоритму N збігається з числом станів в СКК. На кожній ітерації ОАВ для кожного стану існує М провідних в нього шляхів; таким чином, всього є МИ шляхів.

    Сузір'я для СКК може бути записано у вигляді матриці Q з розміром N хК, де V - число символів в кожній групі. Надалі сигнали КАМ будуть розглядатися як окремий випадок СКК, де N дорівнює числу точок в сузір'ї, V = 1 і всі переходи між станами дозволені.

    Обозначіму'-й шлях ( '= 1 .. .М), провідний на к-й ітерації в пана е стан (г = 1 ... N),

    як '. Кожному шляху ?? ' зіставляються вектор ак 'з розміром (Ь -1), що містить оцінки (Ь -1) останніх елементів даних, матриця коефіцієнтів wk' з розміром

    (Ь х Ь)

    і метрика шляху тк

    г, у

    У матрицях w ^ J d-й рядок являє собою оцінку ІХК, що формується за допомогою

    МНК, для якого на k-й ітерації ОАВ еталоном є символ ^ (d), а вектор a ^ J описує загальну лінію затримки для всіх рядків. Необхідність формування оцінок імпульсної характеристики з різними часовими зсувами зразка буде пояснена далі.

    Алгоритм має два параметри: крок МНК ц і постійну?, Яка задає початкові умови для матриць w ^ J. Результати дослідження впливу обох параметрів на

    характеристики алгоритму наведені далі.

    Алгоритм може бути описаний таким чином:

    • Початкові умови: w0J =? Il для всіх i, j; якщо j < min {M, V}, то m0J = 0 і

    a0j (l) = Q (i, j); якщо j > min {M, V}, то m0j = так і a0j (k) = 0 (Il - одинична матриця з розміром L х L).

    • Обчислення метрик і оновлення оцінок каналу на k-й ітерації.

    З усіх шляхів вибираються ті, які можуть бути продовжені за таблицею переходів в перший стан. Для кожного обраного шляху S ^ J обчислюється вектор d ^ J з розміром V, p-й елемент якого є метрикою даного шляху, продовженого в перший стан з символом Q (m, p) (передбачається, що m-й рядок матриці Q містить групу символів, відповідну переходу з i-го стану в перше). Вектор di, j обчислюється таким чином:

    J (Р) = mk-i + (rk -wkJ-ibp) (rk - w jp),

    де bp =

    Q (m, p) (ak J) T

    т

    символ ермітовим сполучення.

    Крім того, складається вектор uг'1 з розміром V, р-й елемент якого дорівнює Q (т, р). Потім вектори dг, 1 і Uг, 1 замінюються на числа yo1 * 1 і и1 наступним чином:

    и1 = Q (т, V); е '^ = yo'1 (V), де V = аг§тт {yo'1 (р)}, р = 1..У .

    Мінімальне значення набору змінних yo'1 розглядається як метрика т ^ 1,

    відповідні індекси / иа також символ і, запам'ятовуються.

    Далі на шляху оцінки ІХК оновлюються для різних часових зрушень

    зразка (створюється матриця wk'1) і для вектора ak'1, що містить оцінки останніх

    (Ь -1) елементів даних. Послідовність дій може бути описана наступним чином.

    1. Формування оцінки останніх Ь елементів даних, необхідних для оновить

    лення оцінок ІХК: Ь =

    т

    »Г, 'I а'

    2. Оцінка останніх (Ь -1) елементів даних, необхідна для (до +1) -й ітерації алгоритму: ак'1 = Ь (1, Ь -1).

    3. Визначення вектора помилок е = Гк - .

    4. Оновлення оцінок ІХК за допомогою МНК:

    w

    КД = + Це * Ьт, (2)

    де - символ комплексного сполучення.

    | Льноезначеніеі дляпуті ^ до

    Таким чином, шлях ^ Р повністю сформований. Далі з решти величин 'знову вибирається мінімальне значення і для шляху 51,2 аналогічним чином про-

    провадиться оновлення оцінок.

    Повторивши цю процедуру в цілому М раз, можна відібрати М найбільш правдоподібних шляхів, що ведуть після к-й ітерації в перший стан.

    Подібним чином обчислюються метрики і формуються оцінки для всіх необхідних М шляхів в кожне стан, після чого алгоритм готовий до (до +1) -й ітерації.

    Практичний досвід показав, що найкраща оцінка ІХК виходить, якщо в якості еталону для МНК використовується символ Гк (е), де е дорівнює номеру позиції максимуму модуля ІХК І. В іншому випадку оцінка зазвичай сходиться до локального екстремуму. Оскільки номер позиції максимуму модуля ІХК апріорно невідомий, виникла необхідність формувати оцінки з усіма тимчасовими зрушеннями зразка

    (Е = 0 ... Ь -1), що призвело до появи матриць wk 'для кожного шляху.

    Можна запропонувати наступний практичний критерій збіжності алгоритму: будемо вважати ітераційний процес Зійшлий, якщо протягом заданого кількості ітерацій ОАВ для шляху з мінімальною метрикою мінімум модуля елементів вектора помилок е в (2) залишається нижче деякого порога і номер його позиції е не змінюється. Найкращою оцінкою ІХК слід вважати е-ю рядок матриці w для шляху з найменшою метрикою.

    Кількість ітерацій і величина порога залежать від числа станів СКК, відносини сигнал / шум, параметра МНК ц і кількості шляхів в стан М. Для вироблення конкретних рекомендацій щодо їх вибору необхідно провести додаткові дослідження.

    Експериментальні результати. Нехай Ітах є максимумом модуля ІХК,

    а у - номером його позиції: Ітах = Іу = тах {| І /}, г = 0, ..., Ь-1. Величину МСІ Б мож-

    Ь-1

    але визначити як Б = Іт1 | х ^ \ кг \.

    г = о, г ф у

    Характеристики описаного алгоритму досліджені за допомогою моделювання на ЕОМ. При цьому для емуляції каналу зв'язку використовувалося два типи ІХК. Перша з них, лінійна ІХК (ЛІХК) із заданою величиною МСІ Д формувалася таким чином:

    0.05 + '{\ _4Б - 0.2 (Ь -1)] / (Ь -1) (Ь - 3)} при 0 <' < (Ь -1) / 2;

    Ітах = 1 при '= (Ь-1) / 2; 'Ьпрі (Ь -1) / 2 <' <Ь.

    На рис. 2 представлений приклад ЛІХК, а на рис. 3 - амплітудно-фазовий портрет сигналу КАМ-16, який пройшов через канал з такою ІХК при відсутності шуму *.

    І

    0.75 0.50 0.25 0

    ЛІХК

    Б = 1.2,

    Ь = 9

    1 4

    2 0

    - 2 - 4

    І

    0.75 0.50 0.25 0

    РІХК 'Б = 1.4,

    Ь = 9

    -п І

    I | про е>

    13 5 7

    Мал. 2

    Ь - 6 - 4 - 2 0 2 4 Q Рис. 3

    1 4

    2 0

    - 2 - 4

    1 3 5 7 Ь - 6 4 - 2 0 2 4 Q Рис. 4 Рис. 5

    Другий тип, рівномірна ІХК (РІХК) із заданою величиною МСІ Б, будувалася в такий спосіб: Ітах = 1, у = (Ь -1) / 2; для всіх 'ф у коефіцієнтам І' равновероятно і незалежно присвоювалися значення ± Б / (Ь -1). Приклад РІХК представлений на рис. 4. На рис. 5 показаний амплітудно-фазовий портрет сигналу КАМ-16, який пройшов через канал з даної ІХК при відсутності шуму.

    З рис. 3 і 5 видно, що для коректного прийому даних необхідно компенсувати спотворення, викликані МСІ.

    При моделюванні використовувалися чотири типи сигналів: з фазової маніпуляцією - ФМ-4 і ФМ-8, з квадратурної маніпуляцією - КАМ-16 [4], а також СКК з 8 станами і 64 точками в сузір'ї [4].

    Нормована помилка оцінки ІХК на к-й ітерації алгоритму обчислювалася як

    е (к) = р -11 (к) || / || і ||, де h - справжня ІХК; 11 (к) - її найкраща оцінка на к-й ітерації (рядок матриці w шляху з мінімальною метрикою, номер якої відповідає позиції мінімуму модуля вектора помилок e з (2)). На рис. 6 показаний типовий приклад поведінки нормованої помилки в часі при збіжності алгоритму.

    При моделюванні алгоритм вважався що зійшли в тому випадку, якщо на інтервалі в 200 ітерацій ОАВ помилка е (к) залишалася менше - 36 дБ.

    Результати дослідження максимально допустимої величини МСІ Б (при якій алгоритм ще сходиться) для всіх типів сигналів і ІХК з фіксованими параметрами

    * Чорними точками показані передані, а сірими - прийняті дані.

    0

    400

    800

    до

    - 10 - 20

    - 30

    - 40 е, дБ

    ФМ-4, М = 8 ЛІХК, Ь = 9, В = 1.5, С / Ш = 20 дБ

    алгоритму і відносинами сигнал / шум (с / ш) і з різними довжинами Ь представлені в таблиці. Для всіх сигналів параметр в = 1.0, число шляхів на стан М = 8.

    Результати, представлені в таблиці, дозволяють припустити, що максимально допустима ступінь МСІ не залежить від довжини ІХК, оскільки при проведенні даного експерименту час збіжності алгоритму лежало в діапазоні від 300 до 1000 символів для всіх представлених сигналів.

    Мал. 6

    Вид Число Ц с / ш, В

    сигналів станів дБ ЛІХК, Ь РІХК, Ь

    9 11 13 9 11 13

    ФМ-4 4 0.02 15 2.7 2.6 2.7 4.6 4Т 4.6

    ФМ-8 8 0.02 20 1.6 1.6 1.6 2.0 2.1 2.1

    КАМ-16 16 0.0002 30 1.2 1.1 1.2 1.4 1.4 1.4

    СКК-64 8 0.0002 40 0.8 0.8 0.9 0.8 0.8 0.8

    Результати дослідження впливу кількості шляхів в кожне стан М на максимально допустиму величину МСІ представлені на рис. 7 і 8 для ЛІХК і РІХК відповідно. З цих малюнків видно, що для всіх промоделювати сигналів існує деяке граничне значення М, збільшення числа шляхів понад якого вже не призводить до зростання максимально допустимої величини МСІ.

    0-1-1-Г, 0-1-1--

    2 4 8 М2 4 8 м

    Мал. 7 Рис. 8

    Результати дослідження впливу параметра в, задає початкові умови для

    матриць wг, у, на час збіжності алгоритму * представлені на рис. 9 і 10 для ФМ-4 і КАМ-16 відповідно. З них випливає, що для швидкої збіжності параметр в повинен лежати в інтервалі [0.1Лтах; Ітах]. На практиці максимум модуля ІХК Ітах може бути

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

    Крок МНК ц визначається сигнальним сузір'ям і довжиною ІХК; аналіз його впливу на швидкість збіжності алгоритму можна знайти в [5].

    * Час збіжності вимірюється необхідною кількістю ітерацій алгоритму кс 40

    До

    до

    ФМ-8

    КАМ-16

    400

    200

    300

    2000

    3000

    1000

    0-1-1-1-1-

    10-4 10-3 10-2 10-1 10 °? / H Рис. 10

    10-4 10-3 10-2 10-1 100? / H Рис. 9

    'max

    'max

    Представлені в статті експериментальні результати дозволяють зробити наступні висновки.

    1. Обчислювальна складність запропонованого алгоритму инвариантна до довжини ІХК і для великих довжин дає відчутний виграш в порівнянні з описаним в [3] алгоритмом пошуку по решітці зі зменшеним сузір'ям.

    2. Максимально допустима величина МСІ не залежить від довжини ІХК.

    3. При правильному виборі параметра в час збіжності алгоритму лежить в діапазоні від 300 до 1000 символів.

    4. Починаючи з деякого числа рішень М, що відслідковуються ОАВ для кожного стану, подальше збільшення цього параметра не приводить до зростання максимально допустимої величини МСІ.

    1. Batch Processing Algorithms for Blind Equalization Using Higher-Order Statistics / C.-Y. Chi, C.-Y. Chen, C.-H. Chen, C.-C. Feng // IEEE Signal Processing Magazine. 2003. Vol. 20, № 1. P. 25-50.

    2. Jitendra K. T., Tong L., Ding Z. Single-User Channel Estimation and Equalization // IEEE Signal Processing Magazine. 2000.Vol. 17, № 3. P. 16-29.

    3. Seshadri N. Joint Data and Channel Estimation Using Blind Trellis Search Techniques // IEEE Trans. on Communications. 1994. Vol. COM-42, № 3. P. 1000-1011.

    4. A Duplex Modem Operating at Data Signalling Rates of up to 14400 bit / s for Use on the General Switched Telephone Network and on Leased Point-to-Point 2-Wire Telephone-Type Circuits // ITU-T Recommendation. Vol. 32 bis. Geneva: ITU-T, 1991. 22 p.

    5. Haykin S. Adaptive filter theory. New York: Prentice-Hall, 1986. 620 p.

    A. B. Natalyin, A. B. Sergienko

    Saint Petersburg state electrotechnical university "LETI"

    Reduced Trellis Search Algorithm of Joint Data and Channel Estimation for Quadrature Amplitude Modulation and Trellis Coded Modulation

    Blind channel estimation, blind equalization, channel equalization, Viterbi decoding, least-mean-square method

    Стаття надійшла до редакції 12 січня 2004 р.

    бібліографічний список

    Blind trellis search algorithm for joint channel and data estimation with reduced computational complexity is presented. This method is useful for channels with long impulse responses, moderate intersymbol interference and signal-to-noise ratio. Algorithm description and experimental results are presented and discussed.


    Ключові слова: СЛІПА ОЦІНКА КАНАЛУ / BLIND CHANNEL ESTIMATION / СЛІПЕ ВИРІВНЮВАННЯ / BLIND EQUALIZATION / ВИРІВНЮВАННЯ КАНАЛУ / CHANNEL EQUALIZATION / МЕТОД НАЙМЕНШИХ КВАДРАТІВ / LEAST-MEAN-SQUARE METHOD / декодер Вітербо / VITERBI DECODING

    Завантажити оригінал статті:

    Завантажити