Плоткин байланған - Википедия - Plotkin bound

Ішінде математика туралы кодтау теориясы, Плоткин байланған, Моррис Плоткиннің есімімен аталған, бұл кодтық сөздердің мүмкін болатын ең көп санының шегі (немесе) екілік кодтар берілген ұзындық n және минималды қашықтық берілген г..

Шектеу туралы мәлімдеме

Егер кодтық сөздер екілік белгілерді қолданса, код «екілік» болып саналады алфавит . Атап айтқанда, егер барлық кодтық сөздердің бекітілген ұзындығы болса n, онда екілік кодтың ұзындығы болады n. Эквивалентті жағдайда, бұл жағдайда кодты сөздерді элементтер деп санауға болады векторлық кеңістік үстінен ақырлы өріс . Келіңіздер минималды арақашықтық болуы керек , яғни

қайда болып табылады Хамминг қашықтығы арасында және . Өрнек екілік ұзындықтағы кодты сөздердің максималды санын білдіреді және минималды арақашықтық. Плоткин байланысы бұл өрнекке шектеу қояды.

Теорема (Плоткинмен байланысты):

и) егер тең және , содан кейін

ii) егер тақ және , содан кейін

iii) Егер тең болса, онда

iv) егер тақ болса, онда

қайда дегенді білдіреді еден функциясы.

Істі дәлелдеу и)

Келіңіздер болуы Хамминг қашықтығы туралы және , және элементтер саны болуы керек (осылайша, тең ). Шектеу мөлшерді шектеу арқылы дәлелденеді екі түрлі жолмен.

Бір жағынан, бар таңдау және әрбір осындай таңдау үшін бар таңдау . Анықтама бойынша барлығына және (), бұдан шығады

Екінші жағынан, рұқсат етіңіз болуы жолдары элементтері болатын матрица . Келіңіздер ішіндегі нөлдердің саны болуы керек 'баған . Бұл дегеніміз 'бағанда бар бір. Әр бағандағы нөл мен бір бағандағы таңдау дәл үлес қосады (өйткені ) сомаға дейін сондықтан

Оң жақтағы мөлшер максималды, егер ол болса ғана бәріне арналған (дәлелдеменің осы нүктесінде біз фактіні елемейміз, бұл бүтін сандар), содан кейін

Үшін жоғарғы және төменгі шекараларды біріктіру біз жаңа ғана шығардық,

мұны берген дегенге тең

Бастап тең, бұдан шығатыны

Бұл байланыстың дәлелі аяқталады.

Сондай-ақ қараңыз

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

  • Плоткин, Моррис (1960). «Минималды арақашықтық көрсетілген екілік кодтар». Ақпараттық теория бойынша IRE операциялары. 6: 445–450. дои:10.1109 / TIT.1960.1057584.