Coding theory is the study of the properties of codes and their respective fitness for specific applications.
Teori kode atau Teori pengkodean adalah studi tentang sifat kode dan kesesuaian untuk aplikasi tertentu.
Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage.
Kode digunakan untuk kompresi data, kriptografi, deteksi dan koreksi kesalahan, transmisi data dan penyimpanan data.
Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods.
Kode dipelajari oleh berbagai disiplin ilmu: seperti teori informasi, teknik listrik, matematika, linguistik, dan ilmu komputer untuk tujuan merancang metode transmisi data yang efisien dan andal.
This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.
Penghapusan redundansi dan koreksi atau deteksi kesalahan dalam data yang dikirimkan.
For example, DEFLATE data compression makes files smaller, for purposes such as to reduce Internet traffic.
Misalnya, kompresi data ZIP membuat file data lebih kecil, untuk tujuan seperti untuk mengurangi lalu lintas Internet.
The ordinary user may not be aware of many applications using error correction.
Pengguna biasa tidak mengetahui banyak aplikasi yang menggunakan koreksi kesalahan.
A typical music compact disc (CD) uses the Reed–Solomon code to correct for scratches and dust.
CD musik (CD) menggunakan kode Reed-Solomon untuk mengoreksi goresan dan debu.
In this application the transmission channel is the CD itself.
Dalam aplikasi ini saluran transmisinya adalah CD.
Data modems, telephone transmissions, and the NASA Deep Space Network all employ channel coding techniques to get the bits through, for example the turbo code and LDPC codes.
Modem data, transmisi telepon, dan NASA Deep Space Network seluruhnya menggunakan teknik pengkodean saluran untuk mendapatkan bit, misalnya kode turbo dan kode LDPC.
In this fundamental work he used tools in probability theory, developed by Norbert Wiener, which were in their nascent stages of being applied to communication theory at that time.
Dalam pekerjaan mendasar, ia menggunakan alat dalam teori probabilitas, yang dikembangkan oleh Norbert Wiener,
Shannon developed information entropy as a measure for the uncertainty in a message while essentially inventing the field of information theory.
Shannon mengembangkan entropi informasi sebagai ukuran untuk ketidakpastian dalam pesan sementara pada dasarnya menciptakan bidang teori informasi.
The binary Golay code was developed in 1949.
Kode biner Golay ditemukan pada tahun 1949.
It is an error-correcting code capable of correcting up to three errors in each 24-bit word, and detecting a fourth.
Kode ini adalah kode koreksi kesalahan yang mengoreksi hingga tiga kesalahan dalam setiap kata 24-bit, dan mendeteksi kesalahan keempat.
Richard Hamming won the Turing Award in 1968 for his work at Bell Labs in numerical methods, automatic coding systems, and error-detecting and error-correcting codes.
Richard Hamming memenangkan Turing Award pada tahun 1968 untuk karyanya di Bell Labs dalam metode numerik, sistem pengkodean otomatis, dan pendeteksi kesalahan dan kode koreksi kesalahan.
He invented the concepts known as Hamming codes, Hamming windows, Hamming numbers, and Hamming distance.
Dia menemukan konsep yang dikenal sebagai kode Hamming, jendela Hamming, bilangan Hamming, dan jarak Hamming.
In 1972, Nasir Ahmed proposed the discrete cosine transform (DCT), which he developed with T. Natarajan and K. R. Rao in 1973.
Pada tahun 1972, Nasir Ahmed mengusulkan transformasi kosinus diskrit (DCT), yang ia kembangkan bersama T. Natarajan dan K. R. Rao pada tahun 1973.
The aim of source coding is to take the source data and make it smaller.
Tujuan sumber pengkodean adalah untuk mengambil data sumber dan membuatnya lebih kecil.
Data can be seen as a random variable X : Ω → X }} , where x ∈ X }} appears with probability P
Data dapat dilihat sebagai variabel acak X : Ω → X }} , di mana x ∈ X }} dengan probabilitas P
Data are encoded by strings (words) over an alphabet Σ .
Data dikodekan oleh string (kata) di atas alfabet Σ .
A code is a function C : X → Σ ∗ }\to \Sigma ^{*}} (or Σ + } if the empty string is not part of the alphabet).
Kode adalah fungsi C : X → Σ ∗ }\to \Sigma ^{*}} (atau Σ + } jika pita kosong bukan bagian dari alfabet).
C ( x ) is the code word associated with x .
C ( x ) adalah kata kode terkait dengan x .
Expected length of a code is l ( C )
Panjang kode yang diharapkan adalah l ( C )∑ x ∈ X l ( C ( x ) ) P
}}l(C(x))\mathbb {P} [X=x].} The concatenation of code words C ( x 1 , … , x k )C ( x 1 ) C ( x 2 ) ⋯ C ( x k ) ,\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})} .
}}l(C(x))\mathbb {P} [X=x].} Rangkaian kata kode C ( x 1 , … , x k )C ( x 1 ) C ( x 2 ) ⋯ C ( x k ) ,\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})} .
The code word of the empty string is the empty string itself: C ( ϵ )
Kata kode dari string kosong adalah string kosong: C ( ϵ )
ϵ C : X → Σ ∗ }\to \Sigma ^{*}} is non-singular if injective.
ϵ C : X → Σ ∗ }\to \Sigma ^{*}} adalah non-singular jika injeksi.
C : X ∗ → Σ ∗ }^{*}\to \Sigma ^{*}} is uniquely decodable if injective.
C : X ∗ → Σ ∗ }^{*}\to \Sigma ^{*}} adalah dapat didekodekan secara unik jika bersifat injeksi.
C : X → Σ ∗ }\to \Sigma ^{*}} is instantaneous if C ( x 1 ) )} is not a proper prefix of C ( x 2 ) )} (and vice versa).
C : X → Σ ∗ }\to \Sigma ^{*}} adalah awalan jika C ( x 1 ) )} bukan awalan dari C ( x 2 ) )} (dan sebaliknya).
Entropy of a source is the measure of information.
Entropi dari suatu sumber adalah ukuran informasi.
Basically, source codes try to reduce the redundancy present in the source, and represent the source with fewer bits that carry more information.
Pada dasarnya, kode sumber mencoba mengurangi redundansi yang ada di sumber, dan mewakili sumber dengan bit lebih sedikit yang membawa lebih banyak informasi.
Various techniques used by source coding schemes try to achieve the limit of entropy of the source.
Berbagai teknik yang digunakan oleh skema pengkodean sumber mencoba untuk mencapai batas entropi sumber.
C(x) ≥ H(x), where H(x) is entropy of source (bitrate), and C(x) is the bitrate after compression.
C(x) ≥ H(x), di mana H(x) adalah entropi sumber (bitrate), dan C(x) adalah bitrate setelah kompresi.
In particular, no source coding scheme can be better than the entropy of the source.
Secara khusus, tidak ada skema pengkodean sumber yang lebih baik daripada entropi sumber.
Source coding removes all data superfluous to the need of the transmitter, decreasing the bandwidth required for transmission.
Pengkodean sumber menghilangkan semua data yang berlebihan untuk kebutuhan pemancar, mengurangi bandwidth yang diperlukan untuk transmisi.
The purpose of channel coding theory is to find codes which transmit quickly, contain many valid code words and can correct or at least detect many errors.
Tujuan dari teori pengkodean saluran adalah untuk menemukan kode yang mengirimkan dengan cepat, berisi banyak kata kode yang valid dan dapat memperbaiki atau setidaknya mendeteksi banyak kesalahan.
While not mutually exclusive, performance in these areas is a trade-off.
Meskipun tidak eksklusif satu sama lain, kinerja di bidang ini merupakan trade off.
So, different codes are optimal for different applications.
Jadi, kode yang berbeda optimal untuk aplikasi yang berbeda.
The needed properties of this code mainly depend on the probability of errors happening during transmission.
Sifat yang diperlukan dari kode ini terutama bergantung pada kemungkinan kesalahan yang terjadi selama transmisi.
CDs use cross-interleaved Reed–Solomon coding to spread the data out over the disk.
CD menggunakan penyandian silang Reed-Solomon untuk menyebarkan data ke luar disk.
Although not a very good code, a simple repeat code can serve as an understandable example.
Meskipun bukan kode yang sangat bagus, kode berulang sederhana dapat berfungsi sebagai contoh yang dapat dimengerti.
Suppose we take a block of data bits (representing sound) and send it three times.
Misalkan kita mengambil satu blok bit data (mewakili suara) dan mengirimkannya tiga kali.
The block of data bits is first divided into 4 smaller blocks.
Blok bit data pertama-tama dibagi menjadi 4 blok yang lebih kecil.
This is done three times to spread the data out over the surface of the disk.
Hal ini dilakukan tiga kali untuk menyebarkan data ke seluruh permukaan disk.
However, there are more powerful codes known which are very effective at correcting the "burst" error of a scratch or a dust spot when this interleaving technique is used.
Namun, kode yang dikenal sangat efektif untuk mengoreksi kesalahan dari goresan atau titik debu saat teknik interleaving ini digunakan.
Algebraic coding theory is basically divided into two major types of codes: Linear block codes Convolutional codes It analyzes the following three properties of a code – mainly: Code word length Total number of valid code words The minimum distance between two valid code words, using mainly the Hamming distance, sometimes also other distances like the Lee distance Linear block codes have the property of linearity, i.e. the sum of any two codewords is also a code word, and they are applied to the source bits in blocks, hence the name linear block codes.
Teori pengkodean aljabar pada dasarnya dibagi menjadi dua jenis kode utama: Kode blok linear Kode konvolusional Menganalisis tiga properti kode berikut, terutama: Panjang kata kode Jumlah total kata kode yang valid Minimum jarak antara dua kata kode valid, terutama menggunakan jarak Hamming, terkadang juga jarak lain seperti jarak Lee Kode blok linear memiliki sifat linieritas, yaitu jumlah dari dua codeword juga merupakan kata kode, dan mereka diterapkan ke bit sumber dalam blok, maka nama kode blok linear.
Linear block codes are summarized by their symbol alphabets (e.g., binary or ternary) and parameters (n,m,dmin) where n is the length of the codeword, in symbols, m is the number of source symbols that will be used for encoding at once, dmin is the minimum hamming distance for the code.
Kode blok linear diringkas dengan huruf simbolnya (misalnya, biner atau terner) dan parameter (n,m,dmin) where n adalah panjang kata sandi, dalam simbol, m adalah jumlah simbol sumber yang akan digunakan untuk pengkodean sekaligus, dmin adalah jarak hamming minimum untuk kode.
But block codes rely on more dimensions which cannot easily be visualized.
Namun, kode blok mengandalkan lebih banyak dimensi yang tidak dapat dengan mudah divisualisasikan.
The powerful (24,12) Golay code used in deep space communications uses 24 dimensions.
[24,12) kode Golay yang kuat yang digunakan dalam komunikasi angkasa menggunakan 24 dimensi.
MacKay, David J. C. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003.
ISBN 978-9-81463-589-9. MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003.