Кіріспе
Деректерді блоктарда кодтайтын қателерді түзейтін кодтар отбасысы. Кодтау теориясында блок кодтары – деректерді блоктарда кодтайтын қателерді түзейтін кодтардың кең және маңызды отбасысы. Блок кодтарының көптеген мысалдары бар, олардың көпшілігі кең практикалық қолданысқа ие. Блок кодтарының абстрактілі анықтамасы түсінік тұрғысынан пайдалы, себебі ол кодтау теорияшыларына, математиктерге және компьютер ғалымдарына барлық блок кодтарының шектеулерін біртұтас түрде зерттеуге мүмкіндік береді. Мұндай шектеулер көбінесе блок кодтарының әртүрлі параметрлерін бір-бірімен байланыстыратын, мысалы, оның жылдамдығы мен қателерді анықтау және түзету қабілеті сияқты шектер түрінде болады. Блок кодтарының мысалдары: Рид-Соломон кодтары, Хамминг кодтары, Хадамард кодтары, Экспандер кодтары, Голай кодтары және Рид-Мюллер кодтары. Бұл мысалдар сызықтық кодтар класына да жатады, сондықтан оларды сызықтық блок кодтары деп атайды. Әсіресе, бұл кодтар алгебралық блок кодтары немесе циклдік блок кодтары деп белгілі, өйткені оларды Бульдік полиномиалдарды пайдалана отырып жасауға болады. Алгебралық блок кодтары әдетте алгебралық декодерлерді қолдана отырып, қатаң түрде декодталады. Блок код термині сондай-ақ кіріс деректерінің биттері блогына әсер етіп, шығыс деректерінің биттерін шығаратын кез келген қателерді түзету кодын білдіре алады. Осылайша, блок кодтаушы жадсыз құрылғы болып табылады. Бұл анықтама бойынша турбо кодтар, тоқтатылған конволюциялық кодтар және басқа итерациялық декодталатын кодтар (турбо сияқты кодтар) да блок кодтары деп есептеледі. Тоқтатылмаған конволюциялық кодтаушы блоксыз (фреймделмеген) кодтың мысалы болып табылады, ол жадыға ие және оның орнына ағаш коды ретінде жіктеледі. Бұл мақалада «алгебралық блок кодтары» қарастырылады.
In coding theory, block codes are a large and important family of error correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors. Examples of block codes are Reed–Solomon codes, Hamming codes, Hadamard codes, Expander codes, Golay codes, and Reed–Muller codes. These examples also belong to the class of linear codes, and hence they are called linear block codes. More particularly, these codes are known as algebraic block codes, or cyclic block codes, because they can be generated using boolean polynomials. Algebraic block codes are typically hard decoded using algebraic decoders. The term block code may also refer to any error correcting code that acts on a block of bits of input data to produce bits of output data Consequently, the block coder is a memoryless device. Under this definition codes such as turbo codes, terminated convolutional codes and other iteratively decodable codes (turbo like codes) would also be considered block codes. A non terminated convolutional encoder would be an example of a non block (unframed) code, which has memory and is instead classified as a tree code. This article deals with "algebraic block codes".
Әліпбиі Σ
Кодталатын деректер ағыны белгілі бір әліпби бойынша тізбек ретінде модеделденеді. Әліпбидің мөлшері көбінесе деп жазылады. Егер болса, онда бұл блок коды екілік блок коды деп аталады. Көптеген қолданбаларда санын жай санның дәрежесі ретінде қарастыру және оны шекті өріспен теңестіру пайдалы.
Хабардың ұзындығы k
Хабарлар – элементтер, яғни белгілі бір ұзындықтағы тізбектер. Сондықтан, бұл сан хабардың ұзындығы немесе блок кодтың өлшемі деп аталады.
Блоктың ұзындығы n
Блок кодтың блок ұзындығы – блоктан құралған символдар саны. Осылайша, элементтері ұзындығы бар тізбектер болып табылады және қабылдағыш алатын блоктарға сәйкес келеді. Сондықтан оларды "қабылданған сөздер" деп те атайды. Егер қандай да бір хабарлама үшін , онда -ның код сөзі деп аталады.
Халықтық жазу
Бұл жазуда блок-кодты, өлшемі бар алфавит бойынша, блок ұзындығы , хабарлама ұзындығы және қашықтығы бар ретінде сипатталады. Егер блок-код сызықтық блок-код болса, онда жазудағы квадратты жақшалар осы фактіні көрсету үшін қолданылады. Бинарлық кодтар үшін , индекс кейде жіберіліп қалады. Максималды қашықтықпен ажыратылатын кодтар үшін қашықтық әрқашан , бірақ кейде нақты қашықтық белгісіз, дәлелдеу немесе айту қиын немесе қажет емес. Мұндай жағдайларда, компоненті жоғалған болуы мүмкін. Кейде, әсіресе блок емес кодтар үшін, ұзындығы код сөздерін қамтитын кодтар үшін белгі қолданылады. Блок-кодтар үшін, өлшемі бар алфавит бойынша ұзындығы бар хабарламалар үшін, бұл сан болар еді.
Мысалдар
Жоғарыда айтылғандай, қателерді түзейтін кодтардың көпшілігі шын мәнінде блок кодтар болып табылады. Бірінші қателерді түзейтін код 1950 жылы Ричард В. Хамминг әзірлеген Хамминг (7,4) коды болды. Бұл код 4 биттен тұратын хабарды 3 партиттік бит қосу арқылы 7 биттік кодтық сөзге айналдырады. Сондықтан бұл код блок-код. Бұл сонымен қатар сызықтық код болып шығады, оның қашықтығы 3-ке тең. Жоғарыда көрсетілген қысқартылған жазуда бұл Хамминг (7,4) коды – [3,7] код екенін білдіреді. Рид-Соломон кодтары – кодтар отбасы, мұнда *n* және *k* – жай санның дәрежесі. Ранк кодтары – кодтар отбасы, ал Хадамард кодтары – кодтар отбасы, мұнда *n* және *k* белгілі бір шарттарды қанағаттандырады.
Қателерді анықтау және түзету қасиеттері
Кодты сөзді өлшемдік кеңістіктегі нүкте ретінде қарастыруға болады, ал код – бұл А кодтың ішкі жиыны. А кодтың арақашықтығы бар дегеніміз, радиусымен орталанған Хамминг шарларында басқа кодты сөздер жоқ, яғни Хамминг қашықтығынан аспайтын өлшемдік сөздердің жиынтығы. (Минималды) арақашықтығы бар кодтың келесі қасиеттері бар:
can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius , no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of , the errors are detected (but no guarantee to correct). can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius , the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word , as long as the number of errors is no more than , there is only one codeword in the hamming ball centered at with radius , therefore all errors could be corrected. In order to decode in the presence of more than errors, list decoding or maximum likelihood decoding can be used. can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.
қателерді анықтауға болады: Кодты сөз радиусымен орталанған Хамминг шарларындағы жалғыз кодты сөз болғандықтан, бір кодты сөзді екіншісіне өзгертетін немесе одан аз қателер болатын қателік үлгісі болмайды. Егер қабылдағыш алынған вектордың кодты сөз емес екенін анықтаса, қателер анықталады (бірақ түзетуге кепілдік жоқ).
can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius , no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of , the errors are detected (but no guarantee to correct). can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius , the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word , as long as the number of errors is no more than , there is only one codeword in the hamming ball centered at with radius , therefore all errors could be corrected. In order to decode in the presence of more than errors, list decoding or maximum likelihood decoding can be used. can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.
қателерді түзетуге болады: Кодты сөз радиусымен өзіне орталанған Хамминг шарларындағы жалғыз кодты сөз болғандықтан, екі әртүрлі кодты сөздерге орталанған екі Хамминг шарлары, екеуінің де радиусы бірдей болса, бірін-бірі жапсарласпайды. Сондықтан, егер қателерді түзетуді алынған сөзден ең жақын кодты сөзді табу деп қарастырсақ, қателер саны болмаса, радиусымен орталанған Хамминг шарларында тек бір кодты сөз болады, демек барлық қателерді түзетуге болады. Егер қателер саны болса, тізімдік декодтау немесе максималды ықтималдық декодтау қолданылуы мүмкін.
can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius , no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of , the errors are detected (but no guarantee to correct). can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius , the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word , as long as the number of errors is no more than , there is only one codeword in the hamming ball centered at with radius , therefore all errors could be corrected. In order to decode in the presence of more than errors, list decoding or maximum likelihood decoding can be used. can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.
жоюларды түзетуге болады. Жою дегеніміз, жойылған символдың орны белгілі дегенді білдіреді. Түзетуді «өткізу» декодтау арқылы жүзеге асыруға болады: «өткізу» кезінде жойылған орын символмен толтырылады және қателерді түзету жүргізіледі. Қателер саны болмауы керек, сондықтан жоюларды түзетуге болады.
can detect errors : Because a codeword is the only codeword in the Hamming ball centered at itself with radius , no error pattern of or fewer errors could change one codeword to another. When the receiver detects that the received vector is not a codeword of , the errors are detected (but no guarantee to correct). can correct errors. Because a codeword is the only codeword in the Hamming ball centered at itself with radius , the two Hamming balls centered at two different codewords respectively with both radius do not overlap with each other. Therefore, if we consider the error correction as finding the codeword closest to the received word , as long as the number of errors is no more than , there is only one codeword in the hamming ball centered at with radius , therefore all errors could be corrected. In order to decode in the presence of more than errors, list decoding or maximum likelihood decoding can be used. can correct erasures. By erasure it means that the position of the erased symbol is known. Correcting could be achieved by passing decoding : In passing the erased position is filled with the symbol and error correcting is carried out. There must be one passing that the number of errors is no more than and therefore the erasures could be corrected.