Jarak Lee

Dalam teori kode, jarak Lee mengukur jarak dua string dengan panjang yang sama atas suatu alfabet. Jarak ini diperkenalkan ole C. Y. Lee pada tahun 1958, dan merupakan sebuah metrik. Untuk string x 1 x 2 … x n {\displaystyle x_{1}x_{2}\dots x_{n}} $x_{1}x_{2}\dots x_{n}$ dan y 1 y 2 … y n {\displaystyle y_{1}y_{2}\dots y_{n}} $y_{1}y_{2}\dots y_{n}$ dengan panjang n {\displaystyle n} $n$ atas alfabet q-ary { 0 , 1 , … , q − 1 } {\displaystyle \{0,\,1,\,\dots ,\,q-1\}} $\{0,\,1,\,\dots ,\,q-1\}$ berukuran q ≥ 2 {\displaystyle q\geq 2} $q\geq 2$ , jarak Lee didefinisikan sebagai

∑ i = 1 n min ( | x i − y i | , q − | x i − y i | ) . {\displaystyle \sum _{i=1}^{n}\min(|x_{i}-y_{i}|,\,q-|x_{i}-y_{i}|).} $\sum _{i=1}^{n}\min(|x_{i}-y_{i}|,\,q-|x_{i}-y_{i}|).$ ^[1]

Dengan menganggap alfabet sebagai grup adiktif Z_q, jarak Lee antara simbol x {\displaystyle x} $x$ dan y {\displaystyle y} $y$ adalah jarak terpendek pada graf Cayley antara mereka.^[2] Jika q = 2 {\displaystyle q=2} $q=2$ atau q = 3 {\displaystyle q=3} $q=3$ , jarak Lee akan sama dengan jarak Hamming, karena kedua jarak tersebut bernilai 0 untuk dua simbol yang sama, dan bernilai 1 untuk dua simbol yang berbeda. Untuk kasus q > 3 {\displaystyle q>3} $q>3$ hal tersebut tidak berlaku lagi, dan nilai jarak Lee antara dua simbol dapat lebih dari 1.

Contoh

Berikut adalah contoh jarak Lee atas beberapa alfabet:

Untuk alfabet biner (yakni q = 2 {\displaystyle q=2} $q=2$ ), jarak Lee antara string 1010 {\displaystyle 1010} $1010$ dan 1100 {\displaystyle 1100} $1100$ adalah

min ( 0 , 2 − 0 ) + min ( 1 , 2 − 1 ) + min ( 1 , 2 − 1 ) + min ( 0 , 2 − 0 ) = 0 + 1 + 1 + 0 = 2 {\displaystyle \min(0,2-0)+\min(1,2-1)+\min(1,2-1)+\min(0,2-0)=0+1+1+0=2} $\min(0,2-0)+\min(1,2-1)+\min(1,2-1)+\min(0,2-0)=0+1+1+0=2$ Pada alfabet ini, jarak Lee sama dengan jarak Hamming

Untuk alfabet dengan q = 6 {\displaystyle q=6} $q=6$ , jarak Lee antara string 3140 {\displaystyle 3140} $3140$ dan 2543 {\displaystyle 2543} $2543$ adalah

min ( 1 , 6 − 1 ) + min ( 2 , 6 − 2 ) + min ( 0 , 6 − 0 ) + min ( 3 , 6 − 3 ) = 1 + 2 + 0 + 3 = 6 {\displaystyle \min(1,6-1)+\min(2,6-2)+\min(0,6-0)+\min(3,6-3)=1+2+0+3=6} $\min(1,6-1)+\min(2,6-2)+\min(0,6-0)+\min(3,6-3)=1+2+0+3=6$

Daftar pustaka

Lee, C. Y. (1958), "Some properties of nonbinary error-correcting codes", IRE Transactions on Information Theory, 4 (2): 77–82, doi:10.1109/TIT.1958.1057446
Berlekamp, Elwyn R. (1968), Algebraic Coding Theory, McGraw-Hill
Voloch, Jose Felipe; Walker, Judy L. (1998). "Lee Weights of Codes from Elliptic Curves". Dalam Vardy, Alexander (ed.). Codes, Curves, and Signals: Common Threads in Communications. Springer Science & Business Media. ISBN 978-1-4615-5121-8.

Referensi

↑ Deza, Elena; Deza, Michel (2014), Dictionary of Distances (Edisi 3rd), Elsevier, hlm. 52, ISBN 9783662443422
↑ Blahut, Richard E. (2008). Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach. Cambridge University Press. hlm. 108. ISBN 978-1-139-46946-3.

Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

Artikel ini tidak memiliki konten kategori. Bantulah dengan menambah kategori yang sesuai sehingga artikel ini terkategori dengan artikel lain yang sejenis.