Archive for November 23rd, 2009

Least common multiple


Kelipatan persekutuan terkecil (least common multiple) dari bilangan bulat positif a dan b adalah bilangan bulat positif terkecil yang dapat dibagi oleh a maupun oleh b. Kelipatan persekutuan terkecil dari a dan b dituliskan sebagai lcm(a, b). Contoh:

lcm(3, 7) = 21, lcm(4, 6) = 12, dan lcm(5, 10) = 10

Seperti halnya gcd, nilai lcm dapat dihitung melalui faktorisasi prima sebagai berikut.

a = p1a1 x p2a2 x … x pnan , b= p1b1 x p2b2 x … x pnbn

di mana p1<p2<…pn-1 <pn
dan ai, bi N untuk 1 ≤ i n,

maka lcm(a,b) = p1max(a1,b1) x p2max(a2,b2) x … x pnmax(an,bn)

Contoh: a = 60 = 22×31×51, b = 54 = 21×33×50 maka lcm(a, b) =22×33×51 = 4×27×5 = 540

sedangkan gcd(a, b) =21×31×50 = 2×3×1 = 6

                        (1)

Melalui teorema di atas, dengan mencari FPB (Faktor Persekutuan Terbesar) dari kedua bilangan, maka LCM dapat diperoleh tanpa perlu melakukan faktorisasi terhadap kedua bilangan.

Sumber : http://radar.ee.itb.ac.id/~suksmono/Lectures/el2009/ppt/2.%20Algoritma,%20%20Kompleksitas%20dan%20Teori%20Bilangan.pdf

Advertisement

verilog


Verilog pertama kali dikembangkan sebagai HDL (hardware description language) berlisensi kepemilikan untuk spesifikasi dan simulasi sistem digital oleh Gateway Design Automation Inc. sekitar 1984. Ada rumor bahwa versi awal dari bahasa ini didesain dengan mengambil fitur-fitur dari bahasa HDL yang paling popular pada waktu itu yang disebut HiLo, seperti halnya dari bahasa komputer tradisional seperti C. Pada waktu itu, Verilog tidak distandarisasi dan bahasanya dimodifikasi di hampir semua revisinya yang keluar antara 1984 sampai 1990.

Di akhir 1990, Cadence Design System, memutuskan untuk membeli Gateway Automation System. Cadence sekarang menjadi pemilik dari bahasa Verilog dan produk Gateway lainnya, dan melanjutkan untuk memasarkan Verilog sebagai sebuah bahasa sekaligus simulator. Pada saat yang bersamaan, Synopsys memasarkan metodologi desain top-down, menggunakan Verilog. Ini merupakan sebuah kombinasi yang mantap.

Pada 1990, Cadence mempublikasikan bahwa jika Verilog tetap menjadi bahasa yang tertutup, tekanan akan standarisasi akan mengakibatkan industri beralih ke VHDL. Akibatnya, Cadence membentuk Open Verilog International (OVI), dan pada 1991 memberikan dokumentasi untuk Verilog Hardware Description Language. Inilah titik baliknya Verilog menjadi bahasa yang “open“.

Lambat laun disadari bahwa jika ada terlalu banyak perusahaan di dalam pasar untuk Verilog, setiap orang akan mengubah bahasa tersebut untuk kepentingan mereka sendiri. Ini akan bertentangan dengan tujuan utama dari melepas bahasa ini ke domain publik. Alhasil pada 1994, IEEE 1364 working group dibentuk untuk mengubah OVI LRM (Language Reference Manual) ke standar IEEE. Kemudian Verilog menjadi sebuah standar IEEE pada Desember 1995.

Ketika Cadence memberikan LRM kepada OVI, beberapa perusahaan mulai bekerja pada Verilog simulator. Pada 1992, Verilog simulator pertama diumumkan. Yang paling berhasil dari semua simulator ini adalah VCS (Verilog Compiled Simulator), dari Chronologic Simulation. Ini merupakan compiler yang sesungguhnya, bukan sebuah interpreter, layaknya Verilog-XL. Alhasil, kecepatan eksekusi simulasi menjadi lebih cepat.

Popularitas dari Verilog dan PLI meningkat secara exponensial. Verilog sebagai sebuah HDL lebih digemari daripada VHDL yang strukturnya lebih baik. Hanya masalah waktu sebelum orang-orang di OVI menyadari kebutuhan akan sebuah standar yang lebih bisa diterima secara universal. Kemudian OVI meminta IEEE untuk membentuk sebuah komite kerja untuk mempersiapkan Verilog sebagai sebuah standar IEEE. Komite kerja 1364 dibentuk di pertengahan 1993 dan pada 14 Oktober 1993, pertemuan pertama dimulai.

Standarnya, yang mengombinasikan sintaks bahasa Verilog dan PLI di dalam sebuah single volume, dikeluarkan pada May 1995 dan sekarang dikenal sebagai IEEE Std. 1364-1995.

Setelah beberapa tahun, fitur-fitur baru ditambahkan ke Verilog, dan versi barunya disebut Verilog 2001. Versi ini telah memperbaiki banyak masalah yang Verilog 1995 miliki. Versi ini disebut 1364-2001.

Design flow menggunakan Verilog ditunjukkan pada gambar berikut :

gambar 1 : design flow menggunakan Verilog

Deskripsi Verilog dapat terdiri dari beragam level abstraksi dan dapat digunakan untuk tujuan berbeda pada beragam tahap pada proses mendesain seperti gambar berikut ini :

gambar 2 : level abstraksi dari Verilog

Diagram di bawah ini menunjukkan sebuah pandangan yang sudah sangat disederhanakan dari proses mendesain system elektronik dengan menggunakan Verilog.

gambar 3 : proses mendesain dengan menggunakan Verilog

Verilog mempunyai beberapa kegunaan bagi desainer, salah satunya adalah Verilog mendukung hierarki struktural dengan memperbolehkan sebuah system untuk dispesifikasikan sebagai sebuah hierarki dari modul-modul yang terinterkoneksi. Setiap modul dapat dideskripsikan dalam satu dari dua cara, yaitu dengan menggunakan modul-modul lain yang levelnya lebih rendah, atau dengan menspesifikasikan pola tingkah lakunya sebagai sebuah program.

Hierarki behavioral juga didukung oleh Verilog. Sebuah proses dari level hierarki apapun dapat membuat subproses-subproses yang berjalan bersamaan, atau dengan memecahnya menjadi sekumpulan prosedur.

Komunikasi diimplementasikan di Verilog dengan pendefinisian model memori yang di-shared, menggunakan kabel yang menghubungkan port-port pada modul, register, dan memori untuk membangun komunikasi antara proses. Verilog juga dapat mendukung sinkronisasi dalam beberapa cara, sinkronisasi dapat diimplementasikan menggunakan konstruksi percabangan dan join, dan dengan melihat perubahan nilai dari event juga dapat digunakan untuk sinkronisasi komputasi pada proses-proses yang berbeda. Contohnya :

@(negedge) clock #10 q=d;

gambar 4 : Contoh sintaks untuk sinkronisasi pada Verilog

Pernyataan di atas bermakna bahwa nilai q akan diperbarui dengan nilai d pada 10 unit waktu setelah negative edge dari clock. Pernyataan tersebut dapat juga dinyatakan sebagai berikut :

Wait (clock=0);

#10 q=d;

gambar 5 : Bentuk lain dari sinkronisasi pada Verilog

Spesifikasi pewaktuan (timing) didukung oleh Verilog dengan pemodelan delay dari gerbang dan jaringan. Ini bermakna untuk setiap kenaikan, penurunan dan peniadaan delay, Verilog mengizinkan desainer untuk menspesifikasikan nilai maksimum, minimum atau nilai tertentu. Sebagai tambahan, Verilog memperbolehkan desainer untuk menspesifikasikan delay yang menunjukkan kapan nilai dalam pernyataan assignment akan diperbarui. Contohnya saja dalam pernyataan #10 q = d, nilai q akan diperbarui pada 10 satuan waktu setelah negative edge dari clock.

Verilog juga dapat menangani exception dengan menggunakan pernyataan disable yang akan menonaktifkan blok dari sequential statement yang disebutkan dan mentransfer kontrol ke pernyataan yang mengikuti blok yang disebutkan sebelumnya.

Sumber :