ПОШУК ВЕКТОРІВ У КОДОВИХ КНИГАХ ПРИ УЩІЛЬНЕННІ МОВЛЕННЯ НА ОСНОВІ БІНАРНОГО ДЕРЕВА

Анотація

Передача мовленнєвих сигналів у неущільненому вигляді потребує швидкісних каналів зв’язку через велику надлишковість даних. Саме тому в сучасних системах цифрового зв’язку широко застосовуються алгоритми кодування мовлення, що реалізують високу ступінь ущільнення при збереженні достатнього рівня якості звучання, зокрема з використанням кодових книг. При цьому широко застосовується векторне квантування. Проте практичне застосування векторного квантування у реальному масштабі часу обмежено через різке зростання витрат пам’яті та часу на пошук кодованого вектора у кодових книгах. Для скорочення часу пошуку найближчого вектора у кодових книгах запропоновано метод структуризації кодових книг на основі бінарного дерева. Показано, що використання бінарного дерева дозволяє суттєво зменшити кількість вимірювань відстані, необхідних для пошуку найближчого сусіднього вектора. Проаналізовано основні фактори, що впливають на ефективність пошуку. Розглянуто кілька варіантів розбиття області параметрів при створенні дерева, а саме: midpt, коли комірка ділиться січною площиною посередині перпендикулярно найдовшій стороні; sl_midpt, що відрізняється від попереднього можливістю зсуву січної площини з метою зменшення кількості тривіальних листів; sl_fair, що поєднує методи розбиття по медіані та sl_midpt з врахуванням обмеження на відношення сторін створюваних комірок. Наведено результати порівняльного аналізу вказаних варіантів. Розглянуто властивості LSF як об’єкта квантування, які необхідно враховувати при побудові бінарного дерева Експериментально досліджено продуктивність методів. Оскільки всі вектори в кодових книгах займають лише верхню частину прямокутної області, було запропоновано повернути осі координат на 45 градусів проти годинникової стрілки, перерахувавши координати векторів. Це дало можливість дещо скоротити час пошуку за рахунок штучного досягнення більшої симетричності розбиття дерева. Оцінювання результатів проводилося за кількістю обчислень відстаней у кодових книгах, необхідною для пошуку найближчого вектора, відносно розміру тестової вибірки. Застосування методу при квантуванні мовлення дозволило зменшити час пошуку найближчого вектора до 5% від часу повного пошуку. Скорочення часу пошуку (? в 17 разів) в процесі передавання мовленнєвих сигналів досягається за рахунок додаткових обчислювальних витрат на підготовчому етапі, необхідних для побудови бінарного дерева, а також збільшення обсягів пам’яті, потрібної для його зберігання.