Метод направленного поиска векторов в кодовых книгах
Проанализированы существующие методы ускорения поиска ближайшего вектора в кодовых книгах при передаче речевой информации. Предложена математическая модель и метод направленного поиска с мажоризацией. Проведено моделирование поиска ближайшего вектора, которое подтвердило эффективность предложенного...
Gespeichert in:
| Datum: | 2010 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2010
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/12812 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод направленного поиска векторов в кодовых книгах / А.Н. Ткаченко, О.Ф. Грийо Тукало // Электронное моделирование. — 2010. — Т. 32, № 2. — С. 77-85. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859905155912171520 |
|---|---|
| author | Ткаченко, А.Н. Грийо Тукало, О.Ф. |
| author_facet | Ткаченко, А.Н. Грийо Тукало, О.Ф. |
| citation_txt | Метод направленного поиска векторов в кодовых книгах / А.Н. Ткаченко, О.Ф. Грийо Тукало // Электронное моделирование. — 2010. — Т. 32, № 2. — С. 77-85. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| description | Проанализированы существующие методы ускорения поиска ближайшего вектора в кодовых книгах при передаче речевой информации. Предложена математическая модель и метод направленного поиска с мажоризацией. Проведено моделирование поиска ближайшего вектора, которое подтвердило эффективность предложенного метода.
Проаналізовано іcнуючі методи прискорення пошуку найближчого вектора у кодовій книзі при передаванні мовної інформації. Запропоновано математичну модель і метод спрямованого пошуку із мажоризацією. Проведено моделювання пошуку найближчого вектора, яке підтвердило ефективність запропонованого методу.
Existent approaches of accelerating the nearest vector search in codebooks are analysed at speech transmission. A mathematical model and method of the directed search with majorization is offered. The design of the nearest vector search has been conducted, that confirmed efficiency of the offered method.
|
| first_indexed | 2025-12-07T15:59:27Z |
| format | Article |
| fulltext |
ÓÄÊ 621.39
À. Í. Òêà÷åíêî, êàíä. òåõí. íàóê, Î. Ô. Ãðèéî Òóêàëî
Èí-ò èíôîðìàöèîííûõ òåõíîëîãèé è êîìïüþòåðíîé èíæåíåðèè
Âèííèöêîãî íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà
(Óêðàèíà, 21021, Âèííèöà, Õìåëüíèöêîå øîññå, 95, êàô. BÒ,
òåë. (0432) 598413, (093) 4665570,
Å-mail: alextk1960@gmail.com, xxmargoxx@gmail.com)
Ìåòîä íàïðàâëåííîãî ïîèñêà
âåêòîðîâ â êîäîâûõ êíèãàõ
(Ñòàòüþ ïðåäñòàâèë ä-ð òåõí. íàóê Â. Â. Ìîõîð)
Ïðîàíàëèçèðîâàíû ñóùåñòâóþùèå ìåòîäû óñêîðåíèÿ ïîèñêà áëèæàéøåãî âåêòîðà â êîäîâûõ
êíèãàõ ïðè ïåðåäà÷å ðå÷åâîé èíôîðìàöèè. Ïðåäëîæåíà ìàòåìàòè÷åñêàÿ ìîäåëü è ìåòîä
íàïðàâëåííîãî ïîèñêà ñ ìàæîðèçàöèåé. Ïðîâåäåíî ìîäåëèðîâàíèå ïîèñêà áëèæàéøåãî âåê-
òîðà, êîòîðîå ïîäòâåðäèëî ýôôåêòèâíîñòü ïðåäëîæåííîãî ìåòîäà.
Ïðîàíàë³çîâàíî ³cíóþ÷³ ìåòîäè ïðèñêîðåííÿ ïîøóêó íàéáëèæ÷îãî âåêòîðà ó êîäîâ³é
êíèç³ ïðè ïåðåäàâàíí³ ìîâíî¿ ³íôîðìàö³¿. Çàïðîïîíîâàíî ìàòåìàòè÷íó ìîäåëü ³ ìåòîä
ñïðÿìîâàíîãî ïîøóêó ³ç ìàæîðèçàö³ºþ. Ïðîâåäåíî ìîäåëþâàííÿ ïîøóêó íàéáëèæ÷îãî
âåêòîðà, ÿêå ï³äòâåðäèëî åôåêòèâí³ñòü çàïðîïîíîâàíîãî ìåòîäó.
Ê ë þ ÷ å â û å ñ ë î â à: ñæàòèå ðå÷åâûõ ñèãíàëîâ, ëèíåéíûå ñïåêòðàëüíûå ÷àñòîòû,
êîäîâûå êíèãè, äèàãðàììû Âîðîíîãî, ñîñåäíèé ñïóñê, ìàæîðèçàöèÿ âåêòîðîâ.
Ñæàòèå ðå÷åâûõ ñèãíàëîâ, ïðèìåíÿåìîå â ñîâðåìåííûõ ñèñòåìàõ öèôðîâîé
ñâÿçè, ïîçâîëÿåò ïîâûñèòü ýôôåêòèâíîñòü èñïîëüçîâàíèÿ ïîëîñû ïðîïóñ-
êàíèÿ êàíàëîâ è òåì ñàìûì ñïîñîáñòâóåò óìåíüøåíèþ öåí íà óñëóãè ìî-
áèëüíîé è èíòåðíåò-ñâÿçè. Â íàñòîÿùåå âðåìÿ øèðîêîå ðàñïðîñòðàíåíèå
ïîëó÷èëè ìåòîäû ñæàòèÿ íà îñíîâå êâàíòîâàíèÿ ñèãíàëîâ ñ èñïîëüçîâàíèåì
êîäîâûõ êíèã. Ðåàëèçàöèÿ ñêàëÿðíîãî êâàíòîâàíèÿ (ÑÊ) ëèíåéíûõ ñïåêò-
ðàëüíûõ ïàð (line spectrum frequency (LSF)) íå òðåáóåò çíà÷èòåëüíûõ âû÷èñ-
ëèòåëüíûõ ðåñóðñîâ è áîëüøèõ îáúåìîâ ïàìÿòè. Îäíàêî â ïîñëåäíåå âðåìÿ â
ñòàíäàðòàõ ñæàòèÿ ðå÷è ÷àùå èñïîëüçóþò âåêòîðíîå êâàíòîâàíèå (ÂÊ), ïîç-
âîëÿþùåå ïîëó÷èòü ìåíüøåå ñïåêòðàëüíîå èñêàæåíèå ïðè êîäèðîâàíèè
ñèãíàëà îäèíàêîâûì êîëè÷åñòâîì áèò. Ýòî îáóñëîâëåíî òåì, ÷òî â ÂÊ áîëåå
ýôôåêòèâíî èñïîëüçóåòñÿ êîððåëÿöèÿ ìåæäó îòäåëüíûìè ñîñòàâëÿþùèìè
âåêòîðà ïàðàìåòðîâ. Ïðåèìóùåñòâî âîçðàñòàåò ñ óâåëè÷åíèåì ÷èñëà ñîâ-
ìåñòíî êâàíòóåìûõ êîìïîíåíòîâ, ò.å. ïðè óâåëè÷åíèè ðàçìåðíîñòè âåêòî-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 2 77
ðà. Âìåñòå ñ òåì, ïðè ýòîì âîçðàñòàþò çàòðàòû ïàìÿòè, à òàêæå âðåìÿ íà
ïîèñê êîäèðîâàííîãî âåêòîðà â êîäîâîé êíèãå, ÷òî ïðåäîïðåäåëÿåò
ñóùåñòâåííûå îãðàíè÷åíèÿ íà ïðàêòè÷åñêîå ïðèìåíåíèå ÂÊ â ðåàëüíîì
ìàñøòàáå âðåìåíè. Ïîýòîìó â äåéñòâóþùèõ ñòàíäàðòàõ ïðèìåíÿþò ñóá-
îïòèìàëüíîå êîäèðîâàíèå, êîãäà 10-òèìåðíûé âåêòîð ïàðàìåòðîâ ðàçáè-
âàþò íà äâà èëè áîëüøå ïîäâåêòîðîâ ìåíüøåé ðàçìåðíîñòè [1].
Äëÿ ñîêðàùåíèÿ âðåìåíè ïîèñêà â [2] ïðåäëîæåíî íåñêîëüêî ñïîñîáîâ
óïîðÿäî÷åíèÿ âåêòîðîâ â êîäîâîé êíèãå, íàçâàííûõ ìåòîäàìè áûñòðîãî
âåêòîðíîãî êâàíòîâàíèÿ (fast vector quantization methods). Ïîêàçàíî, ÷òî
ñëîæíîñòü âû÷èñëåíèé ïðè èñïîëüçîâàíèè ýòèõ ìåòîäîâ ñîñòàâëÿåò 25 %
ñëîæíîñòè âû÷èñëåíèé ïðè ïîëíîì ïîèñêå áåç ñóùåñòâåííîé ïîòåðè ïðî-
èçâîäèòåëüíîñòè, êîòîðàÿ îöåíèâàëàñü ïî ñïåêòðàëüíîìó èñêàæåíèþ.
 [3] ïðåäëîæåí ìåòîä ñòðóêòóðèçàöèè êîäîâûõ êíèã íà îñíîâå îòíî-
øåíèÿ ìàæîðèðîâàíèÿ, èñïîëüçîâàíèå êîòîðîãî ïîçâîëèëî óìåíüøèòü
ñëîæíîñòü âû÷èñëåíèé â 5—6 ðàç ïî ñðàâíåíèþ ñ ñîîòâåòñòâóþùåé ñëîæ-
íîñòüþ ïðè ïîëíîì ïîèñêå.
Ìåòîä «ñîñåäíåãî ñïóñêà», ïðåäëîæåííûé â ðàáîòå [4], ïîçâîëÿåò
óìåíüøèòü âðåìÿ ïîèñêà ñîñåäíåãî âåêòîðà â 50 ðàç îòíîñèòåëüíî âðåìåíè
ïîëíîãî ïîèñêà â ïðèâåäåííîì ïðèìåðå. Îäíàêî ýòîò âûñîêèé ïîêàçàòåëü
äîñòèãíóò ïðè çíà÷èòåëüíîì óâåëè÷åíèè ñðåäíåãî ñïåêòðàëüíîãî èñêàæå-
íèÿ (íà 0,22 äÁ), ÷òî ìîæåò îêàçàòüñÿ íåïðèåìëåìûì äëÿ ïðàêòè÷åñêîãî
ïðèìåíåíèÿ.
Ïðåäëàãàåìûé ìåòîä îáúåäèíÿåò ïðåèìóùåñòâà ìåòîäîâ, îïèñàííûõ â
ðàáîòàõ [3] è [4]. Çàðàíåå ïîäãîòîâëåííûé ñïèñîê ñîñåäåé äëÿ êàæäîãî
êëàñòåðà â äàëüíåéøåì óïîðÿäî÷èâàåòñÿ ñîãëàñíî îòíîøåíèþ ìàæîðèðî-
âàíèÿ. Ýòî ïîçâîëÿåò óìåíüøèòü âðåìÿ ïîèñêà áëèæàéøåãî âåêòîðà â
êîäîâîé êíèãå â 40 ðàç îòíîñèòåëüíî âðåìåíè ïîëíîãî ïîèñêà áåç ñóùåñò-
âåííîãî óâåëè÷åíèÿ ñïåêòðàëüíîãî èñêàæåíèÿ.
Óìåíüøåíèÿ ñëîæíîñòè âû÷èñëåíèé ïðè êîäèðîâàíèè ðå÷åâûõ ñèãíà-
ëîâ ìîæíî äîñòè÷ü â ðåçóëüòàòå íàïðàâëåííîãî ïîèñêà áëèæàéøåãî âåêòî-
ðà â êîäîâîé êíèãå. Äëÿ ýòîãî íåîáõîäèìî ðåøèòü òàêèå çàäà÷è:
ðàçðàáîòàòü ìîäåëü è ñòðóêòóðó äàííûõ, õðàíÿùèõñÿ â êîäîâûõ
êíèãàõ;
ðàçðàáîòàòü ìåòîä ïîèñêà áëèæàéøåãî âåêòîðà â ñîçäàííîé êîäîâîé
êíèãå;
îöåíèòü ýôôåêòèâíîñòü ðàçðàáîòàííîãî ìåòîäà.
Ìàòåìàòè÷åñêàÿ ìîäåëü è ìåòîä íàïðàâëåííîãî ïîèñêà. Ïóñòü
êîäîâàÿ êíèãà ñîäåðæèò êîíå÷íîå ìíîæåñòâî âåêòîðîâ Q Y Y YN�{ , ,..., }1 2 ,
Y y y yi i i iM�{ , ,..., }1 2 . Òàêèì îáðàçîì, ñ êàæäûì âåêòîðîì Y j â êîäîâîé
êíèãå ñâÿçàí èíäåêñ, èëè êîäîâîå ñëîâî j, êîòîðîå ìîæåò áûòü çàïèñàíî
À. Í. Òêà÷åíêî, Î. Ô. Ãðèéî Òóêàëî
78 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 2
êàê N-ðàçðÿäíîå öåëîå ÷èñëî. Íà âõîä êâàíòèçàòîðà ïîñòóïàåò âåêòîð
X x x x M�{ , ,..., }1 2 .
 ðåçóëüòàòå êîäèðîâàíèÿ íåîáõîäèìî âûáðàòü òàêîå êîäîâîå ñëîâî j,
êîòîðîå ìèíèìèçèðóåò èñêàæåíèå d X Y j( , ) (ïðàâèëî âûáîðà áëèæàéøåãî
ñîñåäíåãî âåêòîðà). Äëÿ âû÷èñëåíèÿ èñêàæåíèÿ áóäåì èñïîëüçîâàòü Ýâê-
ëèäîâî ðàññòîÿíèå:
d X Y x yi k ik
k
M
2 2
1
( , ) ( )� �
�
� . (1)
Ìíîæåñòâî âõîäíûõ âåêòîðîâ X, êîòîðûå êîäèðóþòñÿ îäíèì è òåì æå
èíäåêñîì j, îáðàçóþò äèàãðàììó Âîðîíîãî:
V X d X Y d X Y i Ij j i� � � �{ : ( , ) ( , ); } ,
ãäå I N�{ , ,..., }1 2 — ìíîæåñòâî èíäåêñîâ. Àëüòåðíàòèâíûì âàðèàíòîì çà-
äàíèÿ ðåãèîíà Âîðîíîãî ÿâëÿåòñÿ ñëåäóþùàÿ ôîðìóëà:
V X d X Y d X Y i Aj j i j� � � �{ : ( , ) ( , ); } ,
ãäå A i V Vj i j� � { : }� — ìíîæåñòâî êîäîâûõ ñëîâ, ó êîòîðûõ äèàãðàììû
Âîðîíîãî ÿâëÿþòñÿ ñìåæíûìè ñ äàííûì ðåãèîíîì.
Ïðîñòåéøèì ìåòîäîì ïîèñêà â êîäîâîé êíèãå âåêòîðà, áëèæàéøåãî ê
X, åñòü ïîëíûé ïîèñê. Ïðè ýòîì äëÿ êîäîâîé êíèãè ðàçìåðîì N íåîáõî-
äèìî N ðàç âû÷èñëèòü ðàññòîÿíèå ñîãëàñíî (1), ÷òî âî ìíîãèõ ñëó÷àÿõ
íåïðèåìëåìî äëÿ ïðàêòè÷åñêîé ðåàëèçàöèè. Ñ äðóãîé ñòîðîíû, ïðè òàêîì
ïîäõîäå òðåáóåòñÿ âûïîëíåíèå áîëüøîãî îáúåìà ëèøíåé ðàáîòû, ïî-
ñêîëüêó íå èñïîëüçóþòñÿ ðåçóëüòàòû ïðåäûäóùèõ âû÷èñëåíèé. Ìåòîä
ñîñåäíåãî ñïóñêà [4] îñíîâàí íà èñïîëüçîâàíèè òàáëèö ñìåæíîñòè A j ,
ïîäãîòîâëåííûõ çàðàíåå äëÿ êàæäîãî ðåãèîíà V j . Îñíîâíàÿ èäåÿ ýòîãî
ìåòîäà ñîñòîèò â òîì, ÷òî ðåçóëüòàòû âû÷èñëåíèÿ ðàññòîÿíèÿ èñïîëü-
çóþòñÿ äëÿ ïåðåõîäîâ ê ñìåæíûì ðåãèîíàì â íàïðàâëåíèè îïòèìóìà.
Ïåðåõîä îò êîäîâîãî ñëîâà j ê êîäîâîìó ñëîâó l ïðîèñõîäèò ïðè âûïîë-
íåíèè óñëîâèÿ
d X Y d X Y l Al j j( , ) ( , ),� � . (2)
Áûëè ðàññìîòðåíû äâå îñíîâíûå ìîäèôèêàöèè ìåòîäà ñîñåäíåãî
ñïóñêà.  ïåðâîé èç íèõ (full neighbor descent (FND)) ñíà÷àëà âû÷èñëÿëîñü
ðàññòîÿíèå îò âõîäíîãî âåêòîðà êî âñåì ñìåæíûì êîäîâûì ñëîâàì äëÿ
äàííîé äèàãðàììû Âîðîíîãî, ïîñëå ÷åãî ïðèíèìàëîñü ðåøåíèå î ïåðå-
õîäå ê êîäîâîìó ñëîâó ñ ìèíèìàëüíûì ðàññòîÿíèåì èëè î çàâåðøåíèè
ïîèñêà (ïîëíûé îáõîä ñîñåäåé):
d X Y d X Y i A l Al i j j( , ) ( , ), ,� � � � .
Ìåòîä íàïðàâëåííîãî ïîèñêà âåêòîðîâ â êîäîâûõ êíèãàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 2 79
Âî âòîðîé ìîäèôèêàöèè (random neighbor descent (RND)) ñîñåäíèå
êîäîâûå ñëîâà ïðîâåðÿëèñü â ñëó÷àéíîì ïîðÿäêå è ïåðåõîä ê ñîñåäíåìó
êîäîâîìó ñëîâó ïðîèñõîäèë ñðàçó ïîñëå âûïîëíåíèÿ óñëîâèÿ (2) (ñëó÷àé-
íûé îáõîä ñîñåäåé).
Ñðàâíåíèå ýòèõ ïîäõîäîâ ïðîâåäåíî äëÿ êîäîâûõ êíèã, ñîäåðæàùèõ
N � 4096 âåêòîðîâ ðàçìåðíîñòüþ M �5. Ëó÷øèå ðåçóëüòàòû ïîëó÷åíû ïðè
ñëó÷àéíîì îáõîäå ñîñåäåé [4].  îáîèõ ñëó÷àÿõ â êà÷åñòâå íà÷àëüíîé
ãèïîòåçû âûáèðàëîñü èñõîäíîå êîäîâîå ñëîâî, íàéäåííîå äëÿ ïðåäûäó-
ùåãî ôðåéìà, êîòîðîå ïîçâîëÿëî èñïîëüçîâàòü êîððåëÿöèþ ìåæäó ñîñåä-
íèìè ôðàãìåíòàìè ðå÷åâîãî ñèãíàëà.
Ïðèâåäåííûå â [4] ðåçóëüòàòû ïîçâîëÿþò ñäåëàòü ïðåäïîëîæåíèå, ÷òî
ýôôåêòèâíîñòü ïîèñêà òåì âûøå, ÷åì ìåíüøå âðåìåíè òðàòèòñÿ íà ïîèñê
ñîñåäà ïðè ïåðåõîäå ñîãëàñíî (2) äëÿ êàæäîãî êîäîâîãî ñëîâà j. Ôàêòè-
÷åñêè íà ýòîì ýòàïå âûïîëíÿåòñÿ çàòðàòíûé ëèíåéíûé ïîèñê, è åãî íåãà-
òèâíîå âëèÿíèå íà îáùèå ðåçóëüòàòû óâåëè÷èâàåòñÿ ñ âîçðàñòàíèåì ÷èñëà
ñîñåäåé. Òàê, äëÿ óïîìÿíóòîé âûøå êîäîâîé êíèãè ÷èñëî ñîñåäåé êîëåá-
ëåòñÿ â ïðåäåëàõ 40 ... 160 è ñîñòàâëÿåò â ñðåäíåì 70 äëÿ êàæäîãî ðåãèîíà.
Ïðè òàêèõ óñëîâèÿõ ëèíåéíûé ïîèñê ìîæíî ñ÷èòàòü íåýôôåêòèâíûì.
Ñëó÷àéíûé îáõîä ñîñåäåé óìåíüøàåò âðåìÿ ëèíåéíîãî ïîèñêà è òåì ñà-
ìûì ïîâûøàåò îáùóþ ïðîèçâîäèòåëüíîñòü.
Ýôôåêòèâíîñòü òàêîãî ïîäõîäà ñóùåñòâåííî çàâèñèò îò òîãî, â êàêîì
ïîðÿäêå îñóùåñòâëÿåòñÿ îáõîä ñîñåäíèõ êîäîâûõ ñëîâ. Ïðè ýòîì ëîãè÷íî
ñäåëàòü ïðåäïîëîæåíèå î òîì, ÷òî, óïîðÿäî÷èâ îáõîä âåêòîðîâ äëÿ êàæäî-
ãî ðåãèîíà, ìîæíî óìåíüøèòü âðåìÿ ëèíåéíîãî ïîèñêà è òåì ñàìûì äîñ-
òè÷ü äàëüíåéøåãî ñîêðàùåíèÿ âû÷èñëèòåëüíûõ çàòðàò.
Îäèí èç âîçìîæíûõ ïîäõîäîâ ê óïîðÿäî÷èâàíèþ êîäîâûõ êíèã îñíîâàí
íà èñïîëüçîâàíèè òåîðèè ìàæîðèçàöèè [5], ïðèìåíåíèå êîòîðîé äëÿ óñêî-
ðåíèÿ ïîèñêà áëèæàéøåãî âåêòîðà îïèñàíî â [3]. Ïóñòü çàäàíû âåêòîðû
Y y y yn�{ , ,..., }1 2 è
�
Y y y yn{ , ,..., }1 2 , Y Y Q,
� , êîìïîíåíòû êîòîðûõ óïî-
ðÿäî÷åíû ïî íåâîçðàñòàíèþ. Ïîëàãàåì, ÷òî Y ìàæîðèðóåòñÿ
Y , èëè
Y ìàæî-
ðèðóåò Y (îáîçíà÷àåòñÿ Y Y�
), åñëè âûïîëíÿåòñÿ ñëåäóþùåå óñëîâèå [5]:
y yi
i
k
i
i
k
�
� �
� �
1 1
, k M� �1 2 1, , ..., ,
y yi
i
M
i
i
M
�
� �
� �
1 1
. (3)
Óïîðÿäî÷èâàíèå, çàäàâàåìîå îòíîøåíèåì ìàæîðèðîâàíèÿ (3), íàçûâàþò
ìàæîðèçàöèåé. Åñëè âûïîëíÿåòñÿ íåðàâåíñòâî
y yi
i
k
i
i
k
�
� �
� �
1 1
, k M�1 2, , ..., , (4)
À. Í. Òêà÷åíêî, Î. Ô. Ãðèéî Òóêàëî
80 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 2
òî ýòî çíà÷èò, ÷òî Y ñëàáî ìàæîðèðóåòñÿ
Y , èëè
Y ñëàáî ìàæîðèðóåò Y
(îáîçíà÷àåòñÿ Y Yw�
).
 ðàáîòå [3] ïîêàçàíî, êàê ìîæíî ïðèìåíèòü óïîðÿäî÷èâàíèå, çàäàí-
íîå îòíîøåíèåì ìàæîðèðîâàíèÿ (4), äëÿ ïîñòðîåíèÿ ñòðóêòóðèðîâàííûõ
âåêòîðíûõ êîäîâûõ êíèã.  äàííîì ñëó÷àå èñïîëüçóåì (4) äëÿ óïîðÿäî-
÷èâàíèÿ ñîñåäåé êàæäîãî êîäîâîãî ñëîâà j. Ïðè ýòîì òàáëèöó ñìåæíîñòè A j
íåîáõîäèìî ðàçáèòü íà îòäåëüíûå êëàññû, ôîðìèðóåìûå ñîãëàñíî óðîâíÿì
ìàæîðèçàöèè, êîòîðûå ôîðìèðóþòñÿ ïî ñëåäóþùåìó ïðàâèëó.
Áóäåì ñ÷èòàòü, ÷òî óðîâåíü ìàæîðèçàöèè Li ìàæîðèðóåòñÿ óðîâíåì
ìàæîðèçàöèè Lk , åñëè äëÿ êàæäîãî âåêòîðà Y, ïðèíàäëåæàùåãî Li , íà
óðîâíå Lk íàéäåòñÿ âåêòîð
Y , ñëàáî ìàæîðèðóþùèé Y, èëè ôîðìàëüíî
� �Y Y Li, , �
�Y Y Lk, , Y Y L Lw i k� �
� ; i k A j, � . (5)
Ðàçáèåíèå òàáëèöû ñìåæíîñòè A j íà êëàññû ñîãëàñíî çàäàííîìó êðèòå-
ðèþ (5) áóäåì íàçûâàòü ñòðóêòóðèçàöèåé. Ñòðóêòóðèçàöèÿ âûïîëíÿåòñÿ
äëÿ ñîêðàùåíèÿ âû÷èñëèòåëüíûõ çàòðàò íà ïîèñê ïðè ïåðåõîäå îò êîäî-
âîãî ñëîâà j ê êîäîâîìó ñëîâó l ñîãëàñíî (2).
Íàïðàâëåííûé ïîèñê â ðàìêàõ ïðåäëîæåííîãî ïîäõîäà ïðîèñõîäèò òàê.
1. Îïðåäåëÿåòñÿ óðîâåíü ìàæîðèçàöèè, íà êîòîðûé ïîïàäàåò âõîäíîé
âåêòîð X.
2. Ñ äàííîãî óðîâíÿ Lk ïðîèñõîäèò ïîèñê âåêòîðà Yl äëÿ ïåðåõîäà ê
êîäîâîìó ñëîâó l ñîãëàñíî (2).
3. Åñëè òàêîé âåêòîð íå íàõîäèòñÿ íà óðîâíå Lk , ïîèñê ïðîäîëæàåòñÿ
íà ñîñåäíèõ óðîâíÿõ Lk �1, Lk
1, Lk �2, Lk
2, ... .
4. Åñëè íè äëÿ îäíîãî âåêòîðà Y i Ai j, � , óñëîâèå (2) íå âûïîëíÿåòñÿ,
ïîèñê çàâåðøàåòñÿ è âåêòîð Y j ñ÷èòàåòñÿ áëèæàéøèì ê âõîäíîìó âåêòîðó
X. Èíà÷å ïðîèñõîäèò ïåðåõîä è ïóíêòû 1— 4 ñíîâà ïîâòîðÿþòñÿ äëÿ êîäî-
âîãî ñëîâà l.
Ñëåäóåò çàìåòèòü, ÷òî ïîèñê óðîâíÿ ìàæîðèçàöèè äëÿ âõîäíîãî âåê-
òîðà X íå òðåáóåò çíà÷èòåëüíûõ çàòðàò âðåìåíè è ñâîäèòñÿ ê ïðîñòîé
ïðîöåäóðå ïðîâåðêè âûïîëíåíèÿ óñëîâèÿ (4). Òàê æå, êàê â [4], â êà÷åñòâå
ïåðâîíà÷àëüíîé ãèïîòåçû âûáèðàåòñÿ èñõîäíîå êîäîâîå ñëîâî, íàéäåííîå
äëÿ ïðåäûäóùåãî ôðåéìà. Ïðåäëîæåííûé ïîäõîä ôàêòè÷åñêè ÿâëÿåòñÿ
ìîäèôèêàöèåé ìåòîäà ñîñåäíåãî ñïóñêà, íî ïîëó÷èë íàçâàíèå ìåòîäà íà-
ïðàâëåííîãî ïîèñêà ñ ìàæîðèçàöèåé (ÍÏÌ), ÷òî, íà íàø âçãëÿä, áîëåå
òî÷íî ñîîòâåòñòâóåò ñóòè ìåòîäà.
Ìîäåëèðîâàíèå ïîèñêà áëèæàéøåãî âåêòîðà ìåòîäîì ÍÏÌ. Ñ
öåëüþ ýêñïåðèìåíòàëüíîé ïðîâåðêè ïðåäëîæåííîãî ïîäõîäà â ñðåäå Vi-
sual Studio ðàçðàáîòàíî ïðîãðàììíîå îáåñïå÷åíèå äëÿ ïîñòðîåíèÿ òàáëèö
ñìåæíîñòè è íàïðàâëåííîãî ïîèñêà áëèæàéøåãî âåêòîðà. Ïîñòðîåíèå âåê-
òîðíûõ êîäîâûõ êíèã âûïîëíåíî ïðè óñëîâèÿõ, îïèñàííûõ â [6]. Äëÿ òîãî
Ìåòîä íàïðàâëåííîãî ïîèñêà âåêòîðîâ â êîäîâûõ êíèãàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 2 81
÷òîáû îáåñïå÷èòü âîçìîæíîñòü ñðàâíåíèÿ ñ ðåçóëüòàòàìè, ïðèâåäåííûìè
â [4], 10-òèìåðíûé âåêòîð LSF-ïàðàìåòðîâ áûë ðàçáèò íà äâå ÷àñòè 5 � 5,
êàæäàÿ êîäîâàÿ êíèãà ñîäåðæàëà ïî 4096 ïîäâåêòîðîâ. Òàêèì îáðàçîì,
îáúåì äàííûõ, íåîáõîäèìûõ äëÿ ïðåäñòàâëåíèÿ ñïåêòðàëüíîé èíôîðìà-
öèè â ïðåäåëàõ ôðåéìà, ñîñòàâëÿë 24 áèòà.
Äëÿ òåñòèðîâàíèÿ âûáðàí òåêñò, ïðåäñòàâëÿþùèé ñîáîé îòðûâîê èç
ðîìàíà È. Íå÷óé-Ëåâèöêîãî è ñîñòîÿùèé èç 20000 âåêòîðîâ. Ðåçóëüòàòû
ïîèñêà îöåíèâàëèñü ïî êîëè÷åñòâó ïðîïóùåííûõ âåêòîðîâ, íàèáîëåå
áëèçêèõ ê âõîäíîìó, âûðàæåííîìó â ïðîöåíòàõ, à òàêæå ïî ñóììàðíîìó
ñïåêòðàëüíîìó èñêàæåíèþ SD [1, 6].
 òàáë. 1 ïðèâåäåíû çíà÷åíèÿ Ñ ñðåäíåãî êîëè÷åñòâà âû÷èñëåíèé
ðàññòîÿíèé (ÊÂÐ) è ãëóáèíû ïîèñêà Tr, ïîëó÷åííûå ðàçëè÷íûìè ìåòî-
äàìè. Ãëóáèíîé ïîèñêà áóäåì íàçûâàòü ÷èñëî ïåðåõîäîâ ìåæäó ñîñåä-
íèìè ðåãèîíàìè, íåîáõîäèìîå äëÿ äîñòèæåíèÿ îïòèìóìà. Êàê âèäíî èç
À. Í. Òêà÷åíêî, Î. Ô. Ãðèéî Òóêàëî
82 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 2
Ìåòîä
C Tr
n
Ñðåäíåå Ìàêñèìàëüíîå Ñðåäíåå Ìàêñèìàëüíîå
FND 140,76 432 2,47 7 56,99
RND 104,46 270 4,94 19 21,15
ÍÏÌ 89,26 214 4,60 20 19,40
Òàáëèöà 1
N, %
35
30
25
20
15
10
5
0
5 10 15 20 25 Tr
1
2
3
Ðèñ. 1. Çàâèñèìîñòü ÷èñëà íàéäåííûõ âåêòîðîâ îò ãëóáèíû ïîèñêà: 1 — FND, n � 56 99, ;
2 — ÍÏÌ, n �19 40, ; 3 — RND, n � 27 15,
òàáë. 1, ìåòîä ÍÏÌ èìååò ïðåèìóùåñòâî ïåðåä îñòàëüíûìè âñëåäñòâèå
ñóùåñòâåííîãî ñîêðàùåíèÿ ñðåäíåãî ÊÂÐ äëÿ êàæäîãî ðåãèîíà n, âûïîë-
íÿåìûõ ïðè ïåðåõîäå ê ñîñåäíåìó ðåãèîíó.
Íà ðèñ. 1 ïðåäñòàâëåíà çàâèñèìîñòü ÷èñëà íàéäåííûõ áëèæàéøèõ
âåêòîðîâ N îò ãëóáèíû ïîèñêà Tr. Êàê âèäèì, ãëóáèíà ïîèñêà ïðè RND è
ÍÏÌ íåñêîëüêî âîçðàñòàåò. Òåì íå ìåíåå, ñðåäíÿÿ ñëîæíîñòü âû÷èñëåíèé
C , îïðåäåëÿåìàÿ ÊÂÐ äî âåêòîðîâ â êîäîâîé êíèãå, óìåíüøàåòñÿ:
C n Tr� � ,
ãäå n — ñðåäíåå ÊÂÐ äëÿ êàæäîãî ðåãèîíà; Tr — ñðåäíåå ÷èñëî ïåðåõîäîâ
ìåæäó ñîñåäíèìè ðåãèîíàìè.
Èç òàáë. 1 âèäíî, ÷òî ìàêñèìàëüíîå è ñðåäíåå çíà÷åíèå ÊÂÐ ñóùåñò-
âåííî îòëè÷àþòñÿ. Åñëè äëÿ îöåíèâàíèÿ ñëîæíîñòè âû÷èñëåíèé îðèåíòè-
ðîâàòüñÿ íà çíà÷åíèå ñðåäíåãî, à íå ìàêñèìàëüíîãî ÊÂÐ, ìîæíî óìåíü-
øèòü âðåìÿ, âûäåëÿåìîå íà ïîèñê, â 2,5—3 ðàçà. Îäíàêî ñðåäíåå çíà÷åíèå
ÊÂÐ íå ÿâëÿåòñÿ èíôîðìàòèâíîé õàðàêòåðèñòèêîé äëÿ ñæàòèÿ ðå÷åâûõ
ñèãíàëîâ â ðåàëüíîì âðåìåíè, ïîñêîëüêó âðåìÿ, ñýêîíîìëåííîå íà âû÷èñ-
ëåíèÿ â îäíîì ôðåéìå, íåâîçìîæíî èñïîëüçîâàòü â äðóãîì. Ïîýòîìó ñëîæ-
íîñòü âû÷èñëåíèé äîëæíà áûòü êîíñòàíòîé äëÿ ðàçíûõ ôðåéìîâ, êîòîðàÿ
îïðåäåëÿåòñÿ âðåìåííûì èíòåðâàëîì (îêíîì), îòâåäåííûì íà ïîèñê áëè-
æàéøåãî âåêòîðà â êîäîâîé êíèãå. Ëîãè÷íî ïðåäïîëîæèòü, ÷òî ýòîò èíòåð-
âàë ÿâëÿåòñÿ âåëè÷èíîé, ïðîïîðöèîíàëüíîé ÊÂÐ, è îöåíèòü äëÿ ðàçëè÷íûõ
Ìåòîä íàïðàâëåííîãî ïîèñêà âåêòîðîâ â êîäîâûõ êíèãàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 2 83
MV, %
60
40
20
0
40 60 80 100 120 ÊÂÐ
RND
HÏÌ
Ðèñ. 2.×èñëî ïðîïóùåííûõ âåêòîðîâ äëÿ ðàçëè÷íûõ îêîí
îêîí ÷èñëî ïðîïóùåííûõ âåêòîðîâ è ñïåêòðàëüíîå èñêàæåíèå. Ðåçóëüòàòû
òàêîãî èññëåäîâàíèÿ ïðèâåäåíû â òàáë. 2 è íà ðèñ. 2.
Êàê âèäèì, ïðèåìëåìûå äëÿ ïðàêòè÷åñêîãî èñïîëüçîâàíèÿ ðåçóëüòàòû
äîñòèãàþòñÿ äëÿ îêîí, çíà÷èòåëüíî ìåíüøèõ ïî ðàçìåðó, ÷åì ìàêñèìàëü-
íûå çíà÷åíèÿ ÊÂÐ, ïðèâåäåííûå â òàáë. 1. Ýòî îáúÿñíÿåòñÿ òåì, ÷òî
íàèáîëüøåå ÊÂÐ ïðèõîäèòñÿ íà ïðîâåðêó ïîñëåäíåé äèàãðàììûV j , êîãäà
ôàêòè÷åñêè íàèáîëåå áëèçêèé âåêòîð óæå íàéäåí è ïåðåõîä íå îñóùåñòâ-
ëÿåòñÿ. Ñëåäóåò çàìåòèòü òàêæå, ÷òî ìåòîä ÍÏÌ îáåñïå÷èâàåò óìåíüøå-
íèå ÷èñëà ïðîïóùåííûõ âåêòîðîâ è ñïåêòðàëüíîãî èñêàæåíèÿ ïî ñðàâíå-
íèþ ñ ìåòîäîì RND äëÿ îêîí îäèíàêîâîãî ðàçìåðà.
Âûâîäû. Ïðåäëîæåííûé ìåòîä ÍÏÌ ÿâëÿåòñÿ óñîâåðøåíñòâîâàííûì
âàðèàíòîì ìåòîäà ñîñåäíåãî ñïóñêà — RND. Êàê è ìåòîä RND, îí ïîçâîëÿåò
óñêîðèòü ïðîöåññ âûáîðà íåîáõîäèìûõ âåêòîðîâ èç êîäîâûõ êíèã â ïðîöåññå
ïåðåäà÷è ðå÷è â ðåçóëüòàòå ñîçäàíèÿ òàáëèö ñìåæíîñòè íà ïîäãîòîâèòåëüíîì
ýòàïå.  òî æå âðåìÿ ìåòîä ÍÏÌ îáåñïå÷èâàåò óìåíüøåíèå âðåìåíè ïîèñêà
áëèæàéøåãî ñîñåäíåãî âåêòîðà íà 30 % ïî ñðàâíåíèþ ñ ìåòîäîì RND
âñëåäñòâèå ïðåäâàðèòåëüíîãî óïîðÿäî÷èâàíèÿ âåêòîðîâ â òàáëèöàõ ñìåæíîñ-
òè ñîãëàñíî îòíîøåíèþ ìàæîðèðîâàíèÿ. Ïðè ýòîì îáùåå ñïåêòðàëüíîå èñêà-
æåíèå íå âîçðàñòàåò è ñîñòàâëÿåò â ðàññìàòðèâàåìîì ïðèìåðå 0,854 äÁ.
Existent approaches of accelerating the nearest vector search in codebooks are analysed at speech
transmission. A mathematical model and method of the directed search with majorization is of-
fered. The design of the nearest vector search has been conducted, that confirmed efficiency of
the offered method.
1. Paliwal K. K., Atal B. S. Efficient vector quantization of LPC parameters at 24 bits/frame // IEEE
Transaction on Speech and Audio Processing. 1993. — Vol. 1, ¹ 2. — Ð. 3—14.
2. Zhou J., Shoham Y., Akansu A. Simple Fast Vector Quantization of the Line Spectral Fre-
quencies // Image Compression and Encryption Technologies. — 2001. — Vol. 4551. —
Ð. 274—282.
À. Í. Òêà÷åíêî, Î. Ô. Ãðèéî Òóêàëî
84 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 2
ÊÂÐ
Ïðîïóùåííûå âåêòîðû MV, % Ñïåêòðàëüíîå èñêàæåíèå SD, äÁ
RND ÍÏÌ RND ÍÏÌ
40 64,50 25,93 1,028 0,915
60 42,60 8,43 0,940 0,866
80 23,08 1,88 0,893 0,857
100 10,88 0,25 0,871 0,854
120 4,73 0,05 0,862 0,854
140 1,68 0,00 0,857 0,854
Òàáëèöà 2
3. Á³ë³÷åíêî Í. Î., Òêà÷åíêî Î. Ì., Ôåôåðìàí Î. Ä., Õðóùàê Ñ. Â. Øâèäêèé ïîøóê ïðè
âåêòîðíîìó êâàíòóâàíí³ ë³í³éíèõ ñïåêòðàëüíèõ ÷àñòîò // Ðåºñòðàö³ÿ, çáåð³ãàííÿ ³
îáðîáêà äàíèõ. — 2008. — 10, ¹ 2. — Ñ. 37—47.
4. Agrell E. Spectral coding by fast vector quantization // Proc. IEEE Workshop on Speech
Coding for Telecommunications. — Sainte-Adele, Quebec, Canada. — 1993. — P. 61—62.
5. Ìàðøàëë À., Îëêèí È. Íåðàâåíñòâà: òåîðèÿ ìàæîðèçàöèè è åå ïðèëîæåíèÿ: Ïåð. ñ
àíãë. — Ì. : Ìèð, 1983. — 576 ñ.
6. Á³ë³÷åíêî Í. Î., Òêà÷åíêî Î. Ì., Ôåôåðìàí Î. Ä., Õðóùàê Ñ. Â. LSF-âîêîäåð íà îñíîâ³
âåêòîðíîãî êâàíòóâàííÿ // Ðåºñòðàö³ÿ, çáåð³ãàííÿ ³ îáðîáêà äàíèõ.— 2007. — 9, ¹ 1. —
Ñ. 35—41.
Ïîñòóïèëà 22.07.09;
ïîñëå äîðàáîòêè 04.12.09
ÒÊÀ×ÅÍÊÎ Àëåêñàíäð Íèêîëàåâè÷, êàíä. òåõí. íàóê, äîöåíò êàôåäðû âû÷èñëèòåëüíîé òåõ-
íèêè Èí-òà èíôîðìàöèîííûõ òåõíîëîãèé è êîìïüþòåðíîé èíæåíåðèè Âèííèöêîãî íàöèî-
íàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà.  1982 ã. îêîí÷èë Âèííèöêèé ïîëèòåõíè÷åñêèé èí-ò.
Îáëàñòü íàó÷íûõ èññëåäîâàíèé — öèôðîâàÿ îáðàáîòêà ðå÷åâûõ ñèãíàëîâ.
ÃÐÈÉÎ ÒÓÊÀËÎ Îêñàíà Ôðàíñèñêîâíà, ñòóäåíòêà Èíñòèòóòà èíôîðìàöèîííûõ òåõíî-
ëîãèé è êîìïüþòåðíîé èíæåíåðèè Âèííèöêîãî íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà.
Îáëàñòü íàó÷íûõ èññëåäîâàíèé — öèôðîâàÿ îáðàáîòêà ðå÷åâûõ ñèãíàëîâ.
Ìåòîä íàïðàâëåííîãî ïîèñêà âåêòîðîâ â êîäîâûõ êíèãàõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2010. Ò. 32. ¹ 2 85
`
86 ISSN 0204–3572. Electronic Modeling. 2010. V. 32. ¹ 2
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJDFFile false
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/Description <<
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-12812 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T15:59:27Z |
| publishDate | 2010 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Ткаченко, А.Н. Грийо Тукало, О.Ф. 2010-10-22T11:39:03Z 2010-10-22T11:39:03Z 2010 Метод направленного поиска векторов в кодовых книгах / А.Н. Ткаченко, О.Ф. Грийо Тукало // Электронное моделирование. — 2010. — Т. 32, № 2. — С. 77-85. — Бібліогр.: 6 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/12812 621.39 Проанализированы существующие методы ускорения поиска ближайшего вектора в кодовых книгах при передаче речевой информации. Предложена математическая модель и метод направленного поиска с мажоризацией. Проведено моделирование поиска ближайшего вектора, которое подтвердило эффективность предложенного метода. Проаналізовано іcнуючі методи прискорення пошуку найближчого вектора у кодовій книзі при передаванні мовної інформації. Запропоновано математичну модель і метод спрямованого пошуку із мажоризацією. Проведено моделювання пошуку найближчого вектора, яке підтвердило ефективність запропонованого методу. Existent approaches of accelerating the nearest vector search in codebooks are analysed at speech transmission. A mathematical model and method of the directed search with majorization is offered. The design of the nearest vector search has been conducted, that confirmed efficiency of the offered method. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Информационные технологии Метод направленного поиска векторов в кодовых книгах Article published earlier |
| spellingShingle | Метод направленного поиска векторов в кодовых книгах Ткаченко, А.Н. Грийо Тукало, О.Ф. Информационные технологии |
| title | Метод направленного поиска векторов в кодовых книгах |
| title_full | Метод направленного поиска векторов в кодовых книгах |
| title_fullStr | Метод направленного поиска векторов в кодовых книгах |
| title_full_unstemmed | Метод направленного поиска векторов в кодовых книгах |
| title_short | Метод направленного поиска векторов в кодовых книгах |
| title_sort | метод направленного поиска векторов в кодовых книгах |
| topic | Информационные технологии |
| topic_facet | Информационные технологии |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/12812 |
| work_keys_str_mv | AT tkačenkoan metodnapravlennogopoiskavektorovvkodovyhknigah AT griiotukaloof metodnapravlennogopoiskavektorovvkodovyhknigah |