Спосіб спрямованого пошуку векторів при ущільненні мовних сигналів

Спосіб спрямованого пошуку векторів для ущільнення мовних сигналів, який включає формування таблиць суміжності на основі діаграми Вороного, обчислення відстані від вхідного вектора до поточного, її порівняння з відстанями між вхідним вектором і списком сусідів поточного, у 3 48138 Поставлена задача досягається тим, що заздалегідь підготовлена таблиця суміжності для кожного класу (якому відповідає певний рівень мажоризації) надалі впорядковується за рівнями мажоризації. Спрямований пошук відбувається таким чином: спочатку визначають рівень мажоризації, до якого належить вхідний вектор та, починаючи з цього рівня, виконують пошук найближчого до нього вектора. Перехід відбувається, якщо відстань від вхідного вектора до цього вектора менше, ніж до поточного. Якщо такий вектор не знаходиться на даному рівні, пошук продовжують на сусідніх рівнях. У випадку, якщо для кожного вектора з таблиці суміжності відстань не менше, ніж від поточного, пошук завершують і поточний вектор вважається найближчим до вхідного вектора. Спосіб здійснюється наступним чином: наприклад, кодова книга містить кінцеву множину 1 векторів Q Y , Y2,...YN , Yi yi1, yi2,...yiM . Таким чином, з кожним вектором Yj у кодовій книзі пов'язаний індекс, або кодове слово j , що може бути записано як N - розрядне ціле число. На вхід квантизатора поступає вектор X x1, x2,...xM . В результаті кодування необхідно вибрати таке коd X, Yj дове слово j, що мінімізує спотворення (правило вибору найближчого сусіднього вектора). У даній роботі для вимірювання спотворення використовувалася Евклідова відстань: M 2 d X, Yi xk 2 y ik . k 1 (1) Множина вхідних векторів X , що кодуються одним і тим самим індексом j , утворюють регіон Вороного: X : d X, Yj d X, Yi ; i I j , (2) I 1 2,...,N - множина індексів. Альтерна, де тивним варіантом завдання регіону Вороного є X : d X, Yj d X, Yi ; i A j j , (3) Aj i : i  j де - множина кодових слів, у яких регіони Вороного є суміжними (adjacent) з даним регіоном. Aj На основі таблиць суміжності , підготовлених заздалегідь для кожного регіону відбувається перехід від кодового слова j до кодового слова l за умови d X, Yl d X, Yj ; l A j . (4) Для прискорення пошуку найближчого вектора було здійснено впорядкування кодових книг на основі використання теорії мажоризації. НаприкY y1, y2,...yn лад, задано вектори та Y' y'1, y'2 ,...y'n Y, Y' Q , , компоненти яких впо 4 рядковано за незростанням. Говорять, що Y мажорується Y' або Y' мажорує Y (позначають Y  Y' ), якщо виконується: k k yi i j y'i , k 1 2,...,M 1 , , i 1 n n yi i 1 y'i. i 1 (5) Якщо виконується нерівність k k yi i 1 y'i, k 1 2,...,M, , i 1 , (6) говорять, що Y слабо мажорується Y' або Y' Y w Y' ) слабо мажорує Y (позначають Для впорядкування сусідів кожного кодового слова j було використано формулу (7). При цьому Aj таблицю суміжності було розбито на окремі класи, що формуються відповідно до рівнів мажоризації. Рівні мажоризації формуються за Li таким правилом: рівень мажоризації L мажорується рівнем мажоризації k , якщо для L L кожного вектора Y , що належить i , на рівні k знайдеться вектор Y' , що слабо мажорує Y , або формально Y, Y Li, Y', Y' Lk , Y  w Y' Li  Lk ; i,k Aj (7) Спрямований пошук у рамках запропонованого способу буде відбуватися таким чином. 1. Спочатку визначають, на який рівень мажоризації потрапляє вхідний вектор X . L 2. Після цього, починаючи з цього рівня k , Y відбувається пошук вектора l для переходу до кодового слова l згідно формули (4). 3. Якщо такий вектор не знаходиться на рівні Lk , пошук продовжують на сусідніх рівнях Lk 1,Lk 1,Lk 2,Lk 2,.... 4. Якщо для жодного вектора Yi , i A j (4) не Y виконується, пошук завершують і вектор j вважають найближчим до вхідного вектора X . Інакше відбувається перехід, і пункти 1-4 повторюються для кодового слова l . Зазначимо, що пошук рівня мажоризації для вхідного вектора X не потребує значних витрат часу і зводиться до простої процедури перевірки виконання формули (6). 5 Комп’ютерна верстка Д. Шеверун 48138 6 Підписне Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601