MEI 2010
8.0 Penyandian Sumber dan Penyandian Kanal Karakteristik umum sinyal yang dibangkitkan oleh sumber fisik adalah sinyal tsb mengandung sejumlah informasi yang secara signifikan berlebihan . Transmisi dari informasi yang berlebih ini sangat sia-sia untuk sumberdaya komunikasi. Untuk penggunaan sumberdaya yang efisien, informasi yang berlebihan harus disingkirkan dari sinyal transmisi utama. Proses ini disebut sebagai penyadian sumber, terdapat dua skema: 1. Operasi tanpa kehilangan informasi, disebut sebagai data compaction atau kompresi data tanpa rugi-rugi, dimana data asli dapat direkonstruksi dari data tersandinya tanpa kehilangan informasi. 2. Operasi dengan hilangnya informas, disebut sebagai kompresi data, dimana data yang direkonstruksi mungkin memiliki perbedaan dengan data aslinya. Skema data komprei sering dipergunakan dalam pengolahan sinyal analog seperti audio dan video , ketika sejumlah derajat tertentu distorsi sinyal diperbolehkan. Dalam bab ini, untuk penyandian sumber, kami akan focus pada skema kompresi tanpa kehilangan data dan tidak akan membahas mengenai kompresi data. Sebagai contoh, asumsikan bahwa data biner mengandung sejumlah daftar panjang dari ‘0’ yang berurutan. Pengerim harus mengirim ulang ‘0’ beberapa kali tanpa penyandian. Efisiensi system seperti ini dapat diperbaiki dengan menggantikan ‘0’ yang berurutan dengan beberapa sandi kata spesifik. Sebagai contoh, jika yang berurutan ’0’ sebanyak 100, kemudian pengirim mungkin hanya mengirim beberapa informasi untuk memberitahu penerima bahwa terdapat 100 ‘0’ dalam arus data yang berikutnya. Agar encoder sumber menjadi efisien, kita memerlukan pengetahuan statistic mengenai sumber. Jika beberapa symbol sumber dikenali sebagai lebih
mungkin daripada yang lain, sehingga kita dapat menggunakan bentuk ini dalam pembangkitan sandi sumber. Idenya sangat sederhana, penggunaan kata sandi pendek untuk symbol sumber yang sering digunakan dan kata sandi panjang untuk symbol sumber yang jarang digunakan. Skema penyandian seperti ini disebut sebagai sandi bervariasi-panjang. Sandi morse merupakan salah satu contoh dari sandi bervariasi-panjang. Tulisan abjad disandikan ke dalam tanda dan ruang, dinotasikan sebagai titik dan garis putus-putus, dan sebaliknya. Kita bisa pahami titik-titik dan garis-garis putus ini sebagai ‘0’ dan ‘1’, seperti yang digunakan dalam system komunikasi digital. Analisa statistic atas sastradalam bahasa Inggris, menunjukan bahwa tulisan ‘e’ dijumpai lebih sering daripada tulisan ‘q’. Sehingga, sandi Morse menyandikan tulisan 'e’ menjadi sebuah titik tunggal, kata sandi paling pendek dalam skema, dan menyandikan ‘q’ menjadi - - -, kata sandi paling panjang dalam skema. Dalam sebuah system komunikasi praktis, terdapat masalah penting lainnya, bahwa informasi digital mungkin tidak secara tepat diterima oleh penerima. Fenomena ini mungkin disebabkan oleh derau atau ketidak-cocokan lain di dalam kanal komunikasi. Adalah hal penting dalam system komunikasi digital, untuk menyediakan suatu tingkat kehandalan tertentu. Untuk sebuah kanal yang tidak handal, pilihan praktis yang tersedia hanya untuk meningkatkan kehandalan adalah penggunaan penyandian kanal, dibatasi dengan ‘kendali kesalahan penyandian’. Penyandian kanal menambah kelebihan berdasarkan pada aturan yang telah ditentukan. Sebagai contoh, kita akan menyandikan bit informasi ‘0’ sebagai bit tersandi ‘000’ dan ‘1’ sebagai ‘111’, dengan dua bit kelebihan yang ditambahkan merupakan tiruan dari bit informasi. Gambar 8.1 menunjukan system komunikasi khas, yang menggunakan kedua penyandian,
penyandian
kanal
dan
penyandian
sumber.
Sumber
diskret
membangkitkan informasi dalam bentuk symbol biner. Kelebihan informasi dari
sumber pertama-tama dihilangkan dengan encoder sumber. Encoder kanal pada pengirim menerima bit pesan dari encoder sumber dan menambahkan kelebihan berdasarkan aturan penyandian kanal. Bit tersandi kemudian dipetakan ke symbol kanal dengan menggunakan sebuah modulator dan mengirimkannya melalui kanal. Pada ujung penerima, sinyal yang diterima mungkin mengalami pengurangan dengan derau kanal yang secara umum merupakan kesalahan decoding dari sumber primer. Sinyal yang diterima kemudian di-demodulasi dengan menggunakan sebuah demodulator dan kemudian dilewatkan melalui decoder kanal. Dekoder kanal memanfaatkan kelebihan untuk memperbaiki kesalahan informasi tertentu. Tujuan dari encoder dan decoder kanal adalah untuk meminimalisir efek dari derau kanal. Selanjutnya jumlah kesalahan antara masukan encoder kanal dan keluaran decoder kanal diturunkan. Informasi dari kanal encoder kemudian diumpankan lewat sandi sumber, dimana sumber diskret asli telah diperbaiki.
Gambar 8.1 Sebuah Model Sistem Komunikasi Digital
Terdapat sejumlah skema penyandian sumber dank anal. Di dalam bab ini, kita fokuskan pada konsep penyandian dan bahaimana kerja skema penyandian dengan pengmabilan contoh daripada teori penyandian. Kita akan memperkenalkan beberapa teknik penyandian sumber, yang paling terkenal sandi Huffman dipilih sebagai Palu. Selanjutnya kita akan perkenalkzn teknik pemyamdian kanal. Untuk itu, sandi Hamming dan sandi konvolusional digunakan sebagai contoh. 8.1 Panjang Kata Sandi Rata-rata dari Penyandian Sumber. Sebuah sumber biner diskrete dari abjad A={0,1} dengan statistic {p0,p1}. Dengan p0 merupakan probabilitas terjadinya sebuah bit ‘0’ dan probabilitas terjadinya sebuah bit ‘1’ merupaka p1. Kita asumsikan bahwa symbol dipancarkan oleh sumber interval sinyalnya berurutan secara statistic independent. Bit informasi sumber pertama-tama dikelompokkan ke dalam blok dengan panjang N, hasilnya dalam semua 2Nkemungkinan kata-kata biner yang dinyatakan sebagai A(N). Sebagai contoh, jika N=2 dan kita memiliki semua kemungkinan katakata biner dari A(2)={00,01,10,11} dengan himpunan statistic
{ p02, p0p1,p1 p0,
p12}. Kita bisa menuliskan kata-kata biner s0={00}, s1={01}, s2={10}, dan s3={11}. Sekarang, jika p0≠p1, probabilitas terjadinya element A(2) berbeda. Sebagai contoh, jika p0= ¾, p1= ¼, selanjutnya kita peroleh statistic { 9/16, 3/16, 3/16, 1/16 }. Untuk penyandian bervasiasi-panjang sumber, kita bisa rancang sebuah himpunan kata sandi dengan panjang yang berbeda untuk menyatakan elemen dari A(2). Tiga kemungkinan sandi symbol disajikan dalam table 8-1. Proses encoding secara sederhana menugaskan sebuah sandi kata unik untuk masing-masing elemen A(N) yang diubah menjadi sebuah string ‘0’ dan ‘1’. Kita asumsikan bahwa sumber memiliki sebuah abjad dengan perbedaan symbol K=2N, dan symbol ke-k sk terjadi dengan probabilitas pk. Kata sandi biner yang diperuntukan
untuk symbol sk oleh encoder memiliki panjang lk, diukur dalam bit. Selanjutnya dalam table 8-1, symbol-simbol 00,01,10, dan 11, dengan probabilitas masing-masing 9/16, 3/16, 3/16, dan 1/16. Panjang masing-masing symbol =2. Panjang kata sandi rata-rata dari encoder sumber adalah
didefinisikan sebagai berikut:
(8-1) Parameter
merepresentasikan jumlah bit per simbol sumber rata-rata yang
digunakan dalam proses encoding sumber. Kita bisa juga mendifinisikan panjang rata-rata per bit informasi adalah sebagai berikut:
(8-2)
Tabel 8-1 Ilustrasi tiga sandi sumber Sebagai contoh, dari table 8-1, jika tidak ada penyandian sumber, digit dari sumber secara langsung ditransmisikan tanpa proses apapun. Dalam hal ini, panjang sandi sandi rata-rata adalah sebagai berikut:
Panjang bit informasi rata-rata dapat dihitung sebagai berikut:
Sekarang asumsikan penyandian sumber digunakan. Sebagai contoh, kita asumsikan bahwa sandi III dalam table 8-1 digunakan. Sandi 8-1 menyandikan kata sandi dengan pemetaan sebagai berikut:
Hal ini akan memberikan keluaran ‘0’ jika berhadapan dengan digit sumber ‘00’ dan keluaran ‘10’ jika menghadapi digit sumber ‘01’ dan seterusnya. Sebagai contoh, jika bit sumber asli adalah ‘001011010000’, maka encoder mengambil tiap dua bit sebagai sebuah grup dan memetakannya ke kata sandi yang bersesuaian sehingga menghasilkan rangkaian’01101111000’ Panjang kode sandi rata-rata dari sandi III dapat dihitung sebagai berikut
Hasilnya menunjukkan bahwa jika sandi III digunakan, maka panjang kata sandi ratarata dapat dikurangi dari 2 menjadi 1,6875, sehingga kita bisa menggunakan bit tersandi yang lebih sedikit untuk merepresentasikan bit informasi asli. Panjang ratarata per bit informasi untuk sandi III dapat dihitung sebagai berikut:
8.7 Sandi Konvolusional Seperti yang dituliskan pada sub bab 8.4, sandi konvolusional
berbeda
dengan sandi blok yang di dalam encodernya dilengkapi memory. Pada satuan waktu kapan pun yang diberikan, encoder menerima k bit informasi dan mengeluarkan n bit tersandi. N sandi tersandi pada satuan waktu kapanpun yang diberikan tergantung tidak hanya pada k masukan saat itu tetapi juga tergantung pada m masukan sebelumnya. Kita akan menunjukan sandi konvolusional sebagai sandi konvolusional (n,k,m). Sebuah contoh sederhana dari sandi konvolusional disajikan dalam gambar 810. Rangkaian informasi masukan merupakan satu bit pada waktu kapan pun dan ditunjukkan dengan ui pada waktu berindex i. Terdapat dua bit keluaran tersandi pada waktu kapan pun. Bit tersandi ditunjukkan dengan vi(1) dan vi(2). Dua elemen memory yang digunakan dalam encoder untuk menyimpan bit informasi sebelumnya ui-1 dan ui-2. Bit tersandi vi(1) dan vi(2)merupakan fungsi dari ui, ui-1 dan ui-2 dan dinyatakan sebagai berikut:
(8-12) dimana notasi
menunjukan operator logika eksklusif OR (XOR). Karena encoder
merupakan sebuah rangkaian sekuensial maka merupakan mesin keadaan berhingga ( FSM=Finite State Machine ). Dari sini perilakunya dapat ditebak dengan menggunakan diagram keadaan.
Gambar 8-10 Encoder Konvolusional (2,1,2 ) Difinisikan keadaan encoder pada waktu I sebagai (ui-1, ui-2 ), yang terdiri dari dua bit pesan yang disimpan dalam register geser. Terdapat 2m = 22 = 4 kemungkinan keadaan. Pada waktu kapan pun, encoder harus berada dalam satu dari tiga keadaan. Encoder mengalami keadaan transisi ketika bit pesan digeser ke dalam register. Masukan ui dapat menyebabkan keadaan transisi dari (ui-1, ui-2 )ke Keluaran vi
(1)
dan vi
(2)
(ui, ui-1 ).
dapat dengan mudah dimengerti sebagai sebuah fungsi dari
keadaan saat ini (ui-1, ui-2 )dan masukan ui. Masing-masing keadaan disajikan dalam sebuah vertex atau titik pada suatu bidang. Transisi dari keadaan satu ke keadaan lainnya disajikan dalm sebuah garis berarah. Gambar 8-11 menunjukan FSM sebuah encoder. MAsing-masing cabang diberi label dengan sebuah notasi masukan/keluaran ui/ vi(1) vi(2). Sebagai contoh, label 1/01 menyatakan bahwa informasi masukan adalah ui=1, dan keluarannya vi(1) vi(2)=01.
Gambar 8-11 Diagram Transisi Keadaan dari Sebuah Sandi Konvolusional ( 2, 1, 2 ) Diagram transisi keadaan dapat juga dijabarkan dengan sebuah pohon sandi, seperti yang disajikan dalam gambar 8-12 untuk sebuah masukan stringdari tiga bit. Dalam pohon ini, masing-masing bit di atas tepi merupakan bit input dan dua bit di bawah tepi merupakan bit-bit keluaran. Catatan bit keluaran tidak berhubungan dengan bit masukan secara tepat, hal ini merupakan karakteristik khusus dari sandi konvolusional.
Gambar 8-12 Pohon Sandi untuk Sandi Konvolusional
Dalam aplikasi praktis, panjang bit informasi adalah berhingga. Panjang bit informasi dinyatakan dengan L. Maka (u1, u2, …., uL) menjadi bit informasi. Keadaan awal dari encoder seharusnya dibuat tetap menjadi (ui-1, ui-2 )=(0,0). Untuk tampilan yang lebih baik, keadaan final dari encoder juga harus dibuat nol. Oleh karena itu, pada ujung masing-masing rangkaian informasi, m zero ( nol )harus ditambahkan untuk menggeser keluar register sehingga keadaan final dapat diakhiri pada keadaan zero. Pada contoh ini, karena m=2, dua zero diperlukan untuk ditambahkan pada ujung rangkaian informasi, menghasilkan rangkaian informasi yang ditambahi zero (u1, u2, …., uL, 0). Rangkaian tertambahi zero kemudian dimasukkan ke encoder konvolusional. Keluaran encoder konvolusional dapat dinyatakan sebagai:
Kita dapat nyatakan rangkaian tersebut dengan vector berikut ini:
Untuk aplikasi umum, L sangat besar jika dibandingkan dengan m, jika overhead dari kelimpahan ditambahan pada ujung rangkaian tersandi tidaklah signifikan. Kita ambil contoh sederhana, dengan L= 5, maka (u1, u2, u3, u4, u5) = ( 1,0,1,1,1 ). Rangakaian tertambahi zero menjadi (u1, u2, u3, u4, u5, 0, 0) = ( 1,0,1,1,1,0,0 ). Dari persamaan (8-12) atau dari gambar 8-11 dengan keadaan awal (0,0), kita dapatkan rangkaian tersandi sebagai (1,1,0,1,0,0,1,0,0,1,1,0,1,1). Selanjutnya kita anggap bahwa kita akan mengirimkan dua bit, sebut aja 00, 01, 10, dan 11. Karena kita telah tetapkan bahwa kita harus kembali ke keadaan sebelumnya yaitu keadaaan awal, kita tambahkan 00 ke masing-masing string
masukan. Sehingga, string masukan menjadi 0000, 0100, 1000, dan 1100. String masukan dan kata sandi yang bersesuaian sebagai berikut:
Bayangkan jika kita menerima 000110111, kita dapat dengan mudah menemukan kata tersandi dan tidak ada kesalahan. Andai kata kita menerima 00111111, kita dapat menentukan bahwa kata sandi terdekat dengan kata yang diterima adalah 00110111 dan kita selanjutnya masih dapat menyimpulkan bahwa bit string yang dikirim adalah 0100. Setiap kata sandi dari sebuah sandi konvolusi dapat disajikan sebagai sebuah tapak berarah di dalam diagram transisi keadaan dan tapak berarah manapun dari panjang L merupakan kata sandi. Keadaan awal dari tapak seharusnya
dibuat
keadaan zero, dan keadaan final seharusnya juga dibuat keadaan zero. Diagram transisi keadaan sangat bermanfaat untuk menentukan unjukkerja dari sandi konvolusional. Unjuk kerja sandi konvolusional dinyatakan dengan jarak sandi konvolusional Hamming. Ukuran jarak yang paling penting untuk sandi konvolusional adalah jarak minimum bebas yang dinyatakan sebagai dfree. Jika panjang bit L dibuat tetap, kita bisa melihat sandi konvolusional sebagai sebuah sandi block dengan bit masukan kL dan bit keluaran n(L+m). CL menjadi himpunann semua kemungkinan kode sandi informasi dengan panjang L. Jarak bebas untuk CL :
(8-13) Dimana H( v1, v2 ) merupakan jarak Hamming antar v1 dan v2. Bobot Hamming dinotasikan sebagai sebuah vector dengan W(v) yang menyajikan sejumlah
elemen
non-zero
dari
v.
Sehingga
kita
Sebagai contoh tentukan v1
dapat =
menunjukan
(1,0,1,1) dan v2=(0,1,1,0).
Dengan jelas terlihat bahwa H( v1, v2 )=3. Sekarang tentukan v=v1 kita juga memiliki W(v1
bahwa
v2=(1,1,0,1),
v2)=W(v)=3.
Sandi konvolusional memiliki properti tersebut, jika v1 dan v2 semestinya CL, vector v=v1
v2 juga semestinya CL, sehingga sandi konvolusional linear sesuai
aturan dalam XOR. Oleh karena itu, jarak bebas dapat disederhanakan menjadi:
(8-14) Persamaan di atas mengindikasikan bahwa jarak bebas sandi konvolusional merupakan bobot minimum dari kata sandi nonzero. Bobot minimum dari kata sandi nonzero dapat ditentukan dari diagram transisi keadaan, kita bisa mencari bobot minimum kata sandi nonzero merupakan tapak dari keadaan (00) ke (10), (01) dan kembali ke keadaan (00). Bobot dari kata sandi yang bersesuaian adalah 2+1+2=5. Oleh karena itu, jarak bebas dari sandi konvolusional = 5.
Gambar 8-13 Sebuah Diagram Transisi Keadaan dengan Pelabelan Bobot
Proses Dekoding Bayangkan bahwa penerima menerima rangkaian bit y= 111110. Tugas dari proses decoding adalah menentukan rangkaian bit terkirim yang harus memiliki panjang=3, dalam kasus ini. Untuk mengilustrasikan proses, mari kita pertama-tama menampilkan proses encoding secara keseluruhan untuk sebuah string masukan dari tiga bit seperti pada gambag 8-14.
Gambar 8-14 Sebuah Pohon Ilustrasi Proses Penyandian yang Melibatkan Sebuah Rangkaian Masukan 3-bit Seperti yang terlihat, terdapat 23=8 rangkaian kemungkinan; dan untuk masing-masing rangkaian xi bersesuaian dengan rangkaian tersandi yi seperti yang diperlihatkan. Bit di atas masing2 tepi
merupakan bit masukan dan dua bit
dibawahnyamerupakan bit output yang bersesuaian. Catatan bahwa keluaran bukan merupakan fungsi dari masukan, hanya sebagai sandi konvolusi yang memiliki memori. Untuk menentukan rangkaian masukan asli, kita bisa mencari secara mendalam dari semua ats kedelapan rangkaian keluaran dan konsekuensinya menentukan jarak antara y7=111010 dan y=111110 adalah 1 merupakan yang
terkecil. Sehingga kita simpulkan bahwa rangkaian masukan adalah 110. Hal ini harus dibuat jelas bahwa tidak ada error selama rangkaian bit ditransmisikan. Untuk masing-masing rangkaian yang diterima, kita mungkin mengubah pohon pada gambar 8-14 menjadi pohon lain yang sesuai dengan rangkaian ini. Contoh seperti yang ditampilkan pada gambar 8-15. Pada Masing-masing tepi dari pohon pembeda pada gambar 8-15, kita sesuaikan dengan harga yang berbeda antara dua bit yang diterima dan dua bit yang disandikan. Sebagai contoh, dengan tepi v01 v11 adalah 2. Di pihak lain, untuk tepi v01 v12, bit tersandinya adalah 11 dan bit yang diterima juga 11. Konsekuensinya, harga dari tepi v01 v12adalah 0.
Gambar 8-15 Pohon pembeda untuk Rangkaian Bit yang Diterima y=111110 Dengan membangun sebuag pohon yang berbeda, masalah decoding menjadi penemuan tapak/ jalur terpendek dari akar v01 untuk titik daun dari pohon. Pada kasus ini, jalur terpendek merupakan adalah v01 v12 v24 v37 yang memiliki total 0+1+0=` yang merupakan jalur terpendek diantara semua harga jalur. Sekali lagi, jalur terpendek ini berseuaian dengan rangkaian masukan 110 yang sesuai. Pendekatan ini untuk men-dekode rangkaian yang diterima secara lansung dan mudah untuk diimplementasikan, hal ini menghadapi masalah yang serius yaitu jumlah titik daun akan meningkat eksponensial dengan panjang rangkaian masukan.
Sebagai contoh, jika rangkaian masukan terdiri dari 4 bit, pohon yang berseuaian akan memiliki 16 titik daun. Secara umum, jika panjang rangkaian masukan adalah k, maka akan terdapat 2k titik daun dan 2k jalur untuk menemukannya. Ketika sandi konvolusional kita tidak menempatkan sebuah batasan pada panjang rangkaian masukan, pendekatan semacam ini tidaklah praktis. Dapatkah kita mencegah sebuah peningkatan eksponensial akan pencarian mendalam? Ya, kita dapat mencegahnya. Mari kita pertama-tama mengeksploitasi penandaan keadaan. Lihat kembali gambar 8-11. Dalam gambar tersebut, kita dapat melihat bahwa terdapat empat keadaan yaitu : (00),(01),(10), dan (11). Untuk kenyamanan, mari kita kasih label sebagai a=(00), b=(11), c=(01) dan d=(10). Kemudian kita gambar ulang gambar 8-15 sehingga diperoleh gambar 8-16, fakta bahwa hanya terdapat empat keadaan yang berbeda. Tandai bahwa jalur pada gambar 8-16 adalah bukan lagi merupakan sebuah pohon, suatu karakteristik yang kita seharusnya gunakan untuk men-dekode pesan yang diterima. Kita dengan mudah menyebutnya sebagai sebuah jalur multi-tingkatan yang berbeda.
Gambar 8-16 Sebuah Jalur Multi-Tingkatan untuk Rangkaian Masukan y=111110
Marilah kita pertimbangkan titik c3. Terdapat dua jalur yang berakhir pada titik ini, disebut sebagai a0a1b2c3 dan a0b1d2c3. Harga untuk a0a1b2c3= 2+0+2=4 dan untuk yang a0b1d2c3= 0+1+0=1. Kemudian kita bisa mengabaikan jalur a0b1d2c3 karena tidak masalah jika yang berikutnya dari sini, kita tidak pernah menggunakan jalur ini. Catat bahwa kedua jalur a0a1a2b3 dan a0b1c2b3 dibatasi oleh b3. Dengan alas an yang sama, kita bisa mengabaikan jalur a0a1a2b3karena harga jalur ini =2+2+1=5 yang lebih besar daripada harga jalur a0b1c2b3 yang memiliki harga =0+1+1=2. Berdasarkan pada diskusi di atas, kita bisa menggambarkan ulang gambar 8-16 sebagai pohon pembeda yang disederhanakan seperti pada gambar 8-17, jalur yang dapat diabaikan saat ini telah diabaikan. Catat bahwa hanya terdapat empat titik daun di dalam pohon pembeda seperti pada gambar 8-17. Kita dapat dengan mudah melihat dari sana, dengan menggunakan alas an yang sama, kita bisa selalu mengurangi jalur pembeda ke dalam pohon pembeda dengan hanya meninggalkan empat titik daun. Gambar 8-18 menunjukkan kasus dengan memperluas pohon dengan tingkatan yang lain. Pembaca dengan mudah melihat bahwa terdapat dua jalur pembatas yang disebut sebagai b4 dan salah satu diantara mereka diabaikan.
Gambar 8-17 Jalur Pembeda dalam Gambar 8-16 Disederhanakan dengan Mengabaikan Beberapa Jalur
Penjelasn di atas merupakan prinsip yang digunakan dalam algoritma Viterbi untuk men-dekode sandi konvolusional. Sebenarnya, hal ini merupakan strategi pengembangan pemrograman, yaitu merupakan sebuah strategi yang secara umum digunakan untuk perancangan algoritma. BAnyak algoritma yang didasarkan pada pendekatan ini. Kita seharusnya tidak menguraikan pemrograman dinamis dalam buku ini. Pembaca bisa secara tersamar memahami prinsipnya sebagai berikut: andaikata kita ingin mencari jalur terpendek dari s ke t. Andaikata terdapat dua titik, katakanlah x dan y, pergi ke y dan kemudian ke t . Terdapat jalur berbeda dari s ke x dan jalur berbeda antara s dan y. Kita tidak tahu dalam solusi final, titik mana yang seharusnya digunakan. Pemrograman dinamis mengajari kita bahwa tidak masalah apakah
x
merupakan
solusi
final
atau
bukan,
kita
seharusnya
hanya
mempertimbangkan jalur terpendek dari s ke x dan mengabaikan semua jalur dari s ke x. Argumen yang sama digunakan untuk s ke y.
Gambar 8-18 Pohon dalam Gambar 8-17 Diperluas dengan Tingkatan yang Lain
