Pencuplikan Kompresif (2)

Ada dua transformasi penting dalam pencuplikan kompresif, yaitu sparsity transform dan projection transform. Transformasi pertama dipakai untuk mencari komponen sparse dari sinyal, sedangkan yang kedua dipakai dalam operasi pengukuran atau pengamatan. Tulisan ini memberikan contoh sederhana cara melakukan pencuplikan kompresif dan rekonstruksi sinyal secara eksak dari cuplikan terkompresi.

Aspek Penting dalam Pencuplikan Kompresif

Pada pembahasan mengenai dekomposisi sinyal dan pencarian basis ideal, telah dijelaskan cara menemukan vektor basis penyusun suatu sinyal hasil sintesis K buah vektor kamus basis , atau sebuah sinyal K-sparse. Berdasarkan prinsip ketidakpastian yang diperumum, jika jumlah komponen K kurang dari dengan menyatakan koherensi dari kamus basis, maka semua komponen penyusun sinyal akan dapat ditemukan oleh optimisasi terkendala P₁ (basis pursuit). Pada akhir pembahasan ditunjukkan, bahkan ketika sinyal sudah tercampur derau, seluruh komponen masih dapat ditemukan sehingga sinyal dapat direkonstruksi secara eksak.

Pencuplikan kompresif bekerja berdasarkan prinsip yang mirip seperti diatas, yakni: diberikan informasi M buah hasil pengamatan dari sinyal K-sparse, sinyal asal sepanjang N>>M>K akan dapat direkonstruksi jika dengan C bergantung pada sistem basis yang dipilih. Hal yang perlu dicermati disini, jumlah cuplikan yang diperlukan menjadi jauh lebih kecil daripada N, bahkan hanya dalam orde logaritma-nya. Disamping itu, nilai M juga dipengaruhi oleh tingkat sparsity K dari sinyal yang dapat dianggap menggambarkan kandungan informasi dari sinyal yang sebenarnya. Pemilihan kamus-basis akan menentukan kinerja kompresi karena dapat menentukan besar-kecilnya jumlah data cuplikan yang diperlukan. Berdasarkan penjelasan ini, ada beberapa hal penting yang perlu diperhatikan dalam melakukan pencuplikan secara kompresif.

Pertama, sinyal yang akan dicuplik haruslah bersifat K-sparse. Kebanyakan sinyal hasil pengamatan di dunia nyata pada dasarnya adalah sinyal sparse terhadap suatu basis tertentu, meskipun belum tentu demikian di kawasan sinyal tersebut diukur. Sistem basis atau transformasi yang membuat suatu sinyal menjadi bersifat sparse disebut sebagai transformasi penjarang (sparsity transform). Termasuk dalam kategori ini antara lain, berbagai sistem transformasi ortogonal yang telah disinggung pada tulisan-tulisan sebelumnya seperti, DCT, Hadamard, DFT, wavelet, … dll.

Aspek penting kedua adalah observasi atau pengukuran (observation/ measurement). Proses pencuplikan klasik dapat dianggap sebagai proses observasi dari suatu sinyal kontinyu. Secara umum, observasi dapat dinyatakan sebagai proyeksi sinyal pada basis tertentu. Pencuplikan klasik adalah proyeksi dari sinyal kontinyu ke basis impuls, sistem pencitraan SFCW-GPR (stepped-frequency continuous wave ground penetrating radar), MRI (magnetic resonance imaging), dan teleskop VLBI (very large base line interferometry) melakukan observasi data spasio-temporal didalam basis Fourier, sedangkan CT (computed tomography) scanner melakukan observasi dalam kawasan Radon. Sistem basis atau transformasi dimana suatu sinyal diamati disebut sebagai transformasi proyeksi (projection transform).

Yang terakhir, besarnya konstanta C yang akan menentukan jumlah minimum data observasi M berkaitan erat dengan derajat koherensi sistem basis. Kedua macam transformasi yang disebutkan akan menentukan besarnya nilai ini karena yang diukur adalah koherensi antara transformasi penjarang dengan transformasi proyeksi.

Gambar 1. Diagram ranah-jamak [1] dalam sistem pencuplikan kompresif sederhana

Hubungan berbagai transformasi yang terlibat dalam pencuplikan kompresif dilukiskan sebagai diagram ranah-jamak [1] pada Gambar 1. Sinyal s sepanjang N-cuplikan bersifat K-sparse dalam sistem basis . Pencuplikan atau pengamatan akan menghasilkan sinyal yang hanya mengandung sebagian data dari sinyal asalnya karena ada informasi yang hilang, yaitu . Jika jumlah pengamatan mencukupi, meskipun jauh dibawah N, K-buah basis sparse dapat ditemukan melalui P₁. Dengan demikian, karena seluruh basis S dapat ditemukan, maka sinyal asal dapat direkonstruksi secara eksak. Pada diagram ini, transformasi penjarang adalah , sedangkan transformasi proyeksi adalah .

Pencuplikan Kompresif Sederhana

Sebagai ilustrasi, akan ditinjau suatu sinyal s yang bersifat sparse terhadap basis DCT dengan derajat sparsity sebesar 4. Bagaimana cara melakukan pencuplikan kompresif dari sinyal ini dan cara melakukan rekonstruksinya?

Pada kasus ini bisa dipilih suatu basis acak Gaussian yang dinormalisasi sebagai transformasi proyeksi-nya. Karena pencuplikan langsung dari sinyal analog melibatkan beberapa hal teknis yang baru akan dibahas pada tulisan mendatang, anggap bahwa pengamatan ini dapat direpresentasikan sebagai subsampling terhadap sinyal waktu diskrit s sepanjang N-cuplikan. Dengan demikian, tahap pertama yang harus dilakukan adalah membentuk matriks pengamatan atau transformasi proyeksi . Dimensi matriks ini adalah MxN, dimana M<<N adalah jumlah pengamatan yang diharapkan. Berdasarkan teorema pencuplikan kompresif, agar sinyal s bisa direkonstruksi secara eksak, maka jumlah ini minimal-nya adalah sekitar CK log(N).

Berbagai peneliti bidang ini memberi nilai C yang berlainan. Pada umumnya nilai ini sebesar koherensi kamus-basis (yang tak-ternormalisasi), dimana kamus basis adalah perkalian antara matriks proyeksi dengan matriks sparsity, sehingga . Pada percobaan ini akan diambil C=1, dengan demikian yang kemudian menentukan M adalah derajat sparsity (K=4) dan logaritma dari cuplikan Nyquist N. Sebagai contoh diambil N=64, jadi M~17 yang berarti adalah faktor kompresi sekitar 3.8 kalinya.

Gambar 2. Sinyal asli dan sinyal cuplikan kompresif

Gambar 2 menunjukkan sinyal s dan cuplikan kompresif-nya . Terlihat bahwa hasil pencuplikan kompresif memberikan data yang lebih ringkas atau lebih pendek dari sinyal asalnya. Dalam skema pencuplikan yang sedang dibahas, sinyal ini adalah .

Gambar 3. Vektor basis terpilih hasil optimisasi P₁

Rekonstruksi dilakukan dengan terlebih dahulu mencari vektor sparse S dalam kawasan DCT melalui optimisasi P₁:

(P₁): min||S||₁ s.t.

Optimisasi ini memiliki arti: pilihlah vektor S paling sparse dalam basis yang dapat menjelaskan hasil pengamatan . Hasilnya ditampilkan dalam Gambar 3, dimana semua basis terpilih tepat sama dengan basis penyusun sinyal.

Gambar 4. Perbandingan sinyal asli dan hasil rekonstruksi

Rekonstruksi dilakukan dengan menyusun kembali sinyal dari vektor basis terpilih. Hasilnya ditampilkan pada Gambar 4, dimana sinyal rekonstruksi identik dengan sinyal asalnya dan sinyal kesalahan bernilai nol.

Pemilihan basis acak sebagai transformasi proyeksi sangat menguntungkan jika dilihat dari beberapa sisi. Yang pertama, setiap data cuplikan didalam s dapat dianggap sama pentingnya. Dengan demikian tidak perlu skema pencuplikan adaptif dengan memilih komponen dominan saja karena semuanya sama penting. Yang kedua, basis acak bersifat universal karena hampir ortogonal ke semua basis lain. Basis ini bisa diterapkan ke berbagai kasus pencuplikan kompresif. Dan yang terakhir, modulasi dengan basis acak untuk mendapatkan membuat hasil pengamatan sedikit terenkripsi (weakly encrypted). Hal ini sangat menguntungkan jika pencuplikan kompresif akan dipakai didalam sistem sensor tersebar kompresif (distributed compressed sensing) dan data yang diamati bersifat rahasia.

Daftar Pustaka

1. AB Suksmono, “A graphical representation of the multi-domain signal processing,” Proc. of SICE-ICASE 2006, Busan, Korea.

Program Matlab

%———————————————–
%Contoh Pencuplikan Kompresif
%———————————————–
clear;%close all;clc;
N=64; %panjang sinyal
%Pembentukan sinyal 4-sparse
PSI=dct(eye(64,64)); %buat matriks DCT
K_sparse=4;%tingkat sparsity
%pN=randperm(nAtoms);
pN=[3 13 42 58];
x=zeros(N,1);
X=zeros(N,1);%’transformed-domain signal
for k=1:K_sparse;
x=x+(-1)^k*PSI(:,pN(k)); %masukkan faktor polaritas basis
X(pN(k))=1;
end;
x0=x;

%lakukan pengukuran atau subsampling
%estimasikan minimal jumlah cuplikan M>CKlog(N)
mu=1*(1/sqrt(N)); %tentukan koherensi->perkiraan
C=sqrt(N)*mu; %koherensi tak ternormalisasi=sqrt(N).koh
M_sub=ceil(C*K_sparse*log(N))
%bentuk matriks pengukuran
PHI=orth(randn(M_sub,N)’)';
%lakukan pengukuran x_sub=PHI*x
x_sub=PHI*x;
x_sub_xtd=zeros(N,1); x_sub_xtd(1:M_sub)=x_sub(1:M_sub);
figure(1);plot(1:N, x0,’k-’,1:N,x_sub_xtd,’b:’);title(’subsampling’);
legend(‘original’,’sub-samples’); xlabel(‘time’);ylabel(‘amplitude’);
%Lakukan recovery
%Bentuk dictionary D=PHI*PSI
D=PHI*PSI;

[D_row,D_col]=size(D);
D_pos=-D;
%define dictionary A
A=zeros(D_row,2*D_col);
A(:,1:D_col)=D;
A(:,D_col+1:2*D_col)=D_pos;

%Pecahkan P1
f=ones(2*D_col,1);
lb=zeros(2*D_col,1);

%*******************
%alpha1=alpha;
f1=ones(2*D_col,1);
lb1=zeros(2*D_col,1);
A1=-A;
x_sub1=x_sub;
%*******************

alpha0=linprog(f,[],[],A,x_sub,lb); %ambil solusi positif
alpha1=linprog(f1,[],[],A1,x_sub1,lb1); %ambil solusi negatif

alpha=alpha0-alpha1; %gabungkan keduanya
%Tampilkan hasil
figure(2);plot(1:D_col,X,’r.’,1:D_col,abs(alpha(1:D_col)),’b-’);
title(‘extracted dct vectors by P1′);
legend(‘original components’,'extracted components’);
xlabel(‘DCT vector index’);ylabel(‘magnitude’);
%obtain a few largest component, by sorting alpha
[z,imax]=sort(abs(alpha(1:D_col)),’descend’);
%Reconstruct the estimated values
x_hat=zeros(N,1);
for k=1:K_sparse;
x_hat=x_hat+alpha(imax(k))*PSI(:,imax(k));
end;
figure(3);plot(1:N,x0,’k.’,1:N,x_hat,’r:’,1:N,x0-x_hat,’b-’);
xlabel(‘time’);ylabel(‘amplitude’);
legend(‘original’,'reconstructed’,'error’);

Pencuplikan Kompresif (1)

Pencuplikan adalah salah satu proses terpenting dalam tahapan pengolahan sinyal dijital, dimana sinyal analog diubah menjadi sinyal diskrit (dijital). Teorema pencuplikan Shannon menetapkan aturan batas minimal laju pencuplikan agar sinyal dapat direkonstruksi ke asalnya, yakni sebesar dua kali lebar-pita dari sinyal. Berdasarkan paradigma pencuplikan kompresif, aturan ini dapat dilanggar karena yang berperanan dalam menentukan rekonstruktivibilitas bukanlah kandungan frekuensi sinyal, melainkan kandungan informasinya yang tercermin dalam derajat sparsity.

Batas Nyquist untuk Pencuplikan Sinyal

Didalam Pengolahan sinyal dijital, pencuplikan (sampling) adalah proses mengambil cuplikan dari sinyal analog secara periodik. Proses ini dapat dinyatakan sebagai perkalian antara sinyal analog dengan deretan impuls , dimana n adalah bilangan bulat dan T adalah perioda pencuplikan. Besaran yang lebih populer dibandingkan dengan T, yaitu kecepatan pencuplikan atau fekuensi pencuplikan .

Seperti yang tergambar didalam blok diagram pengolahan sinyal dijital, pita frekuensi dari sinyal akan terlebih dahulu dibatasi (bandlimited) dengan sebuah tapis anti-aliasing sebelum pencuplikan dilakukan. Secara matematis, proses pencuplikan dapat dirumuskan sebagai perkalian antara (modulasi) sinyal analog dengan sebuah deretan impuls

(1)

Gambar 1 menjelaskan proses pencuplikan yang dilihat dari kawasan waktu. Tinjauan kawasan waktu berguna untuk melihat terbentuknya sinyal waktu diskrit (dijital) dan aspek pencuplikan selang-seragam (uniform sampling) terhadap keluarannya. Namun demikian, untuk mengetahui persyaratan laju pencuplikan minimum atau selang pencuplikan maksimum agar sinyal s_a(t) dapat diperoleh kembali, maka proses ini perlu dilihat dari kawasan frekuensi.

Gambar 1. Pandangan proses pencuplikan dari kawasan waktu.

Ekspresi suatu sinyal dalam kawasan frekuensi dapat diperoleh melalui transformasi Fourier dari persamaan dalam kawasan waktu-nya. Karena perkalian dalam kawasan waktu ekivalen dengan konvolusi dalam kawasan frekuensi, maka hasil transformasi Fourier dari persamaan (1) adalah

(2)

Gambar 2 memperlihatkan proses pencuplikan jika dilihat dari kawasan frekuensi. Karena transform Fourier dari deretan impuls adalah juga suatu deretan impuls, maka konvolusi antara spektrum sinyal dengan impuls menghasilkan pergeseran spektrum sejauh . Sebagai akibatnya akan terjadi pengulangan (tiling) spektrum di seluruh rentang frekuensi pada posisi kelipatan dari frekuensi pencuplikan. Gambar 2 bagian kiri bawah menunjukkan spektrum dari sinyal yang lebar pitanya yang kemudian mengalami proses tiling akibat proses pencuplikan.

Gambar 2. pencuplikan dilihat dari kawasan frekuensi

Jika jarak antar pengulangan atau grid tiling cukup lebar, seperti diperlihatkan pada Gambar 3 bagian atas, yang juga berarti bahwa frekuensi pencuplikannya cukup besar, maka tidak akan terjadi tumpang tindih antar spektrum yang bertetangga. Kondisi ini disebut sebagai non-aliasing. Selanjutnya sifat keunikan dari transformasi Fourier akan menjamin bahwa sinyal asal dapat diperoleh secara sempurna. Sebaliknya, jika kurang besar, maka akan terjadi tumpang tindih antar spektrum yang mengakibatkan hilangnya sebagian dari informasi. Peristiwa ini disebut aliasing, seperti diperlihatkan pada Gambar 3 bagian bawah. Pada kondisi ini, sinyal tidak dapat lagi direkonstruksi secara eksak.

Gambar 3. Kondisi non-aliasing dan aliasing pada proses pencuplikan

Dengan memahami peristiwa aliasing dalam kawasan frekuensi, maka batas minimum laju pencuplikan atau batas Nyquist dapat diperoleh, yaitu sebesar . Hasil ini durumuskan sebagai teorema Shannon untuk pencuplikan sebagai berikut:

Teorema Pencuplikan Shannon. Suatu sinyal pita-terbatas dengan lebar dapat direkonstruksi secara eksak dari cuplikannya jika laju pencuplikan minimum dua kali dari lebar pita tersebut, atau .

Sebagai contoh, manusia dapat mendengar suara dari frekuensi 20 Hz sampai dengan sekitar 20kHz, artinya lebar pita dari suara yang mampu didengar manusia adalah sekitar 20 KHz. Dengan demikian, pengubahan suara menjadi data dijital memerlukan laju pencuplikan sedikitnya 2×20kHz = 40 kHz atau 40.000 cuplikan/detik supaya sinyal suara dapat direkonstruksi secara sempurna, yang berarti juga kualitas dari suara hasil perekaman dijital dapat dimainkan tanpa distorsi.

Pada teori pencuplikan klasik, rekonstruksi sinyal s_r(t) akan ditempuh dengan cara melakukan konvolusi antara sinyal disktrit s(n) hasil cuplikan, dengan tapis rekonstruksi

(3)

Dengan demikian,

(4)

adalah sinyal terekonstruksi yang diinginkan. Tanggapan impuls dari tapis rekonstruksi pada persamaan (3) diperlihatkan pada Gambar 4 berikut ini.

Gambar 4. Tanggapan impuls dari tapis rekonstruksi

Pencuplikan Sub-Nyquist dengan Compressive Sensing

Teorema pencuplikan Shannon memberikan batas minimal laju pencuplikan atau jumlah cuplikan persatuan waktu supaya sinyal kontinyu dapat direkonstruksi secara eksak. Pencuplikan dibawah laju ini akan mengakibatkan terjadinya distorsi atau cacat aliasing. Apakah ada cara untuk memperkecil batas ini tanpa mengakibatkan distorsi?

Teorema pencuplikan diatas didasarkan pada analisis Fourier, dimana fungsi basis dalam transformasi sinyal berupa fungsi sinusoid dari berbagai frekuensi. Bahkan, makna sebenarnya dari transformasi Fourier adalah penguraian suatu sinyal kedalam basis sinusoid. Batas Nyquist menjaga supaya semua komponen frekuensi tetap utuh didalam hasil cuplikan sehingga sinyal dapat dikembalikan ke bentuk asalnya. Jika basis selain sinusiod dipakai dalam mendekomposisi sinyal, tentu aturan ini akan berubah karena yang sebenarnya menggambarkan kandungan informasi dari sinyal bukanlah lebar pita fekuensi-nya.

Gambar 5. Pencuplikan dan rekonstruksi sebuah impuls

Kaitan antara pencuplikan dan kandungan informasi diperlihatkan pada Gambar 5. Sebuah impuls akan memiliki transform Fourier S(k) yang tersebar ke seluruh kawasan frekuensi. Berdasarkan informasi kandungan frekuensi sinyal, maka seluruh komponen frekuensi didalam S(k) diperlukan untuk merekonstruksi sebuah impuls. Penghilangan sebagian dari cuplikan, dalam gambar diperlihatkan hanya 25% nya saja, akan menghasilkan rekonstruksi yang tak sempurna. Sinyal impuls yang telah terdistorsi akibat hilangnya sebagian dari komponen frekuensi diperlihatkan pada Gambar 5 bagian bawah.

Seandainya diketahui ada satu buah impuls di kawasan waktu diskrit dalam selang 32 cuplikan, berapa banyakkah informasi yang dibutuhkan untuk mendeskripsikan sinyal ini?

Gambar diatas menyatakan bahwa seluruh 32 buah komponen frekuensi perlu. Tetapi yang sebenarnya diperlukan hanya satu buah saja, yaitu posisi dari impuls. Informasi inilah yang sesungguhnya lebih esensial dibandingkan dengan lebar pita frekuensi. Satu buah informasi, dalam hal ini posisi impuls, disebut juga sebagai derajat kebebasan dari sinyal s(n). Dalam terminologi CS, besaran ini dinamakan tingkat sparsity dari sinyal. Dengan demikian, sinyal s(n) diatas adalah sebuah sinyal 1-sparse. Hasil penting dari pencuplikan kompresif dirumuskan dalam teorema berikut ini:

Teorema Pencuplikan Kompresif. Suatu sinyal K-sparse sepanjang N-cuplikan dapat direkonstruksi secara eksak berdasarkan buah cuplikannya, dimana C sebuah konstanta kecil yang nilainya bergantung pada sistem-basis yang digunakan.

Jumlah M ini jauh lebih kecil daripada N didalam teknik pencuplikan klasik. Inilah alasan mengapa pencuplikan kompresif dapat dianggap sebagai pencuplikan Sub-Nyquist. Bagaimana melakukan rekonstruksi sinyal jika cuplikannya jauh lebih kecil dari batas Nyquist? Yang jelas, proses rekonstruksi klasik melalui konvolusi sinyal pengamatan dengan tapis rekonstruksi tidak lagi bisa dipakai.

Referensi

1. D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, 52, 2006, pp.1289-306.
2. E. J. Candes and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Problems, 23 (2007), pp.696-985.
3. E.J. Candes, J. Romberg, and T. Tao, “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inf. Theory, Vol. 52, No. 2, Feb. 2006, pp. 489-509.

Kode Matlab

Kode Matlab untuk membuat kurva tanggapan impuls dari tapis rekonstruksi

%MATLAB codes to generate hr(t)

%define sampling period

T = 0.1 ;%0.1 seconds, sampling at 10 Hz

%define time axis

t=-1.0:0.001:1.0; %2 second

hr=sin(pi*t/T)./(pi*t/T);

figure(1);plot(10*t,hr);

xlabel(‘time in Ts’); ylabel(‘hrec’)

title(‘ideal reconstruction filter’);

Kode Matlab untuk melihat pengaruh penghilangan sebagian cuplikan terhadap hasil rekonstruksi sinyal impuls.

%generate an impulse in N=32 sample intervals;

clear;close all; clc;

N=32; s=zeros(N,1);

s(16)=1; %put impulse in the middle

figure(1);stem(s);title(‘Time Domain’);

xlabel(‘time’); ylabel(‘magnitude’);

S=fft(s); %transform s into freq-domain S

figure(2); stem(abs(S));title(‘Frequency Domain’);

xlabel(‘time’); ylabel(‘magnitude’);

%discard some 25% of the components

S1=S; for k=1:round(N/4); S1(4*k)=0;end;

s1=ifft(S1); %signal inversion by IDFT

figure(3); stem(abs(S1));title(‘Frequency Domain’);

xlabel(‘time’); ylabel(‘magnitude’);

figure(4);stem(abs(s1));title(‘Time Domain’);

xlabel(‘time’); ylabel(‘magnitude’);

Dongeng dari Negeri Tanahjarang

oooOOOooo

Tanahjarang adalah nama sebuah negeri yang diperintah oleh seorang Raja yang pandai, adil, bijaksana, dan selalu memikirkan kesejahteraan dan kebahagiaan rakyatnya.

Musim kemarau tahun ini membuat hasil pertanian menurun tajam hingga mengancam kesejahteraan negeri. Raja yang bijak sudah lama memperkirakan kejadian seperti ini dan bersiap menghadapinya dengan membuat lumbung padi, gudang penyimpan ikan dan daging yang diawetkan, dan sebuah fasilitas istimewa untuk menyimpan berbagai sayuran dan buah-buahan.  Selama beberapa musim panen belakangan, rakyat telah diminta menyisihkan hasil sawah dan kebun mereka ke gudang makanan untuk menghadapi masa sulit yang akan segera tiba.

Ketika akhirnya paceklik datang, Kerajaan Tanahjarang dan seluruh rakyat di penjuru negeri siap menghadapinya. Raja yang pandai tahu bahwa masa sulit akan berlangsung lama. Dengan demikian, makanan didalam lumbung dan gudang harus dibagikan dengan sehemat mungkin. Tapi Raja yang bijak juga tahu pentingnya nutrisi yang lengkap untuk rakyatnya, supaya anak negeri ini kelak tumbuh menjadi pemuda yang sehat dan cerdas. Menurut penasihat kerajaan, rakyat tidak hanya cukup diberi nasi saja, tetapi juga lauk-pauk, buah-buahan, dan sayur-sayuran. Bukan hanya itu, setiap desa di pelosok negeri memiliki masakan khas masing-masing, meskipun semuanya terbuat dari bahan pokok yang sama. Ada desa yang suka masakan pedas, masakan asam, masakan manis, masakan asin, dan lain-lain rasa yang jenisnya sebanyak jumlah desa di negeri ini.

Raja ingin selalu membuat rakyat bahagia, bahkan dalam hal selera makan mereka. Karena ketersediaan bahan pangan yang terbatas, tidak mungkin memberikan langsung bahan-bahan pokok ini ke masing-masing penduduk. Sang Raja juga telah belajar dari sahabatnya, Maharaja Hindia, bahwa masalah pembagian makanan bukanlah hal yang sederhana. Lumbung padi di pelosok Negeri Hindia pernah habis karena sang Maharaja ceroboh bertaruh dengan seorang pecatur ulung yang berhasil mengalahkannya; meskipun hadiah yang dimintanya nampak sepele: berikan satu butir beras ke kotak catur pertama, dua butir ke kotak kedua, empat butir di kotak ketiga, …, dan seterusnya sampai ke kotak ke-enampuluh empat. Permintaan sederhana ini telah menyedot persediaan beras di seluruh negeri. Jadi, jika tidak hati-hati,  maka seluruh Negeri Tanahjarang bisa tertimpa bencana.

Raja yang bijak akhirnya memutuskan bahwa rakyat tidak akan diberikan bahan makanan, melainkan masakan yang sudah jadi. Dengan demikian, seluruh juru masak yang mewakili desa dipanggil ke Kerajaan Tanahjarang untuk secara bersama-sama mempersiapkan masakan bagi penduduk desa masing-masing. Hal ini dilakukan supaya tidak ada bahan makanan yang terbuang percuma karena takaran adonan untuk setiap jenis masakan berlainan.

Beberapa bulan kemudian musim kemarau berlalu. Hujan kembali turun, tanah menjadi subur. Petani kembali kesawah menanam padi, peternak menggiring sapi ke ladang mencari rumput. Penduduk Negeri Tanahjarang bekerja dengan penuh sukacita. Masa sulit itu telah berhasil mereka lalui berkat Raja yang bijak dan dicintai rakyatnya.

oooOOOooo

Apa hubungan dongeng diatas dengan compressive sensing … ? Legenda menyebutkan bahwa Sang Raja adalah keturunan langsung dari Maharaja Heisenberg, seorang Raja yang berhasil menjadikan negerinya makmur sejahtera dengan membuat aturan ketat tentang pembagian jatah makanan di masa paceklik.

Dekomposisi Sinyal dan Pencarian Basis Ideal (4)

Masalah pencarian vektor basis ideal dari sebuah sinyal telah dapat diformulasikan sebagai proses optimisasi berkendala (constrained optimization) P₁. Tulisan ini akan terlebih dahulu membahas secara sekilas konsep optimisasi linier, khususnya LP (Linear Programming), dan metode pemecahannya. Meskipun kendala dalam P₁ sebenarnya bersifat tak-linier, pengaturan parameter yang tepat dan batas-batas yang sesuai dapat mengubahnya menjadi permasalahan pemrograman linier. Suatu contoh pencarian basis ideal dari sinyal hasil bentukan sepasang ortobasis dipakai untuk menunjukkan kegunaan LP. Jika batasan sparsity terpenuhi, LP dapat menemukan seluruh basis penyusun sinyal sehingga sinyal dapat direkonstruksi secara eksak.

Pemrograman Matematika dan Optimisasi

Didalam optimisasi ada suatu fungsi objektif yang akan dioptimumkan; dibuat minimum atau maksimum. Kendala memberi batas wilayah dimana fungsi ini berlaku. Dari berbagai macam metoda optimisasi yang ada, salah satu yang memiliki pemakaian luas adalah pemrograman linier (LP/Linier Programming), suatu bentuk khusus dari pemrograman matematika (Mathematical Programming). Bahkan metoda Simpleks yang ditemukan oleh G. Dantzig untuk mencari solusi masalah LP dinobatkan sebagai satu dari sepuluh algoritma terbaik abad keduapuluh.

LP pada dasarnnya merupakan masalah pencarian nilai optimum dari suatu fungsi linier dengan kendala yang juga berbentuk linier. Berikut ini contoh sederhana dari permasalahan LP:

Tentukan harga dan yang meminimumkan nilai , dengan syarat bahwa , , dan .

Masalah diatas dapat dituliskan kedalam bentuk baku sebagai berikut:

minimize

subject to:

,

,

.

Nilai yang akan dioptimalkan disebut sebagai fungsi obyektif, dalam soal diatas adalah . Pemecahan masalah ini dapat dilakukan secara grafis dengan cara menggambarkan semua kendala, lalu mencari titik dimana nilai obyektif mencapai optimum dalam daerah solusi:

Gambar 1. Ilustrasi pencarian titik optimum dalam LP

Pada Gambar 1 diatas, daerah yang diarsir adalah pasangan yang memenuhi semua kendala yang diberikan atau disebut juga feasible region. Kita harus mencari satu titik dimana nilai fungsi obyektif mencapai optimal. Pada LP, solusi selalu terletak di pojok wilayah daerah atau titik simpul. Program Matlab berikut dapat dipakai untuk mencari solusinya:

%pemrograman linier untuk masalah sederhana

% min c’x s.t. Ax<=b; x1>=1, x2>=1

%——————————————

c=[1;-1]; % koefisien fungsi obyektif

A=[1 1; 1 -1]; %matriks A

b=[10; 5]; % kendala

lb=[1 1] ; %batas bawah x1 dan x2

[x, fval,exitflag,output,lambda]=linprog(c,A,b,[],[],lb);

disp(sprintf(‘x1= %f x2=%f\n’,x(1),x(2))); %tampilkan

Dari eksekusi program akan diperoleh nilai yang akan menghasilkan nilai fungsi objektif paling kecil, yaitu -8. Posisi titik optimum ini terletak dipojok paling kiri atas dari politop yang menyatakan daerah solusi.

Metoda simpleks dari Dantzig melakukan perunutan setiap tepian wilayah hingga ditemukan titik optimal yang selalu terletak di sudut atau verteks dari politop. Dengan demikian, dapat ditunjukkan bahwa pada kondisi terburuk, metoda ini akan memiliki kompleksitas yang tumbuh secara eksponensial. Namun kebanyakan masalah praktis dapat dipecahkan dengan cukup cepat, karena kompleksitas rata-ratanya cukup kecil hingga dapat ditangani.

Masalah pertumbuhan kompleksitas perhitungan dalam metoda Simpleks akhirnya dapat diatasi oleh Narendra Karmakar dengan metoda interior point (IPM), yang memiliki kompleksitas polinomial. IPM tidak hanya dipakai pada optimisasi linier, kasus lain yang taklinier-pun dapat dipecahkan dengan metoda ini asalkan daerah solusi bersifat konveks. IPM mencapai kompleksitas polynomial karena tidak lagi merunut tepian daerah solusi, tapi masuk menerobos kedalam wilayah ini sampai solusi yang dicari dapat ditemukan.

Masalah optimisasi seperti diatas dapat dituliskan dalam bentuk umum sebagai berikut:

minimize

subject to:

bahkan dengan dengan menggunakan slack variables

, i = 1, 2, …, m

LP dapat dituliskan dalam bentuk matriks yang lebih ringkas, yaitu

minimize subject to

Masalah mencari nilai minimum suatu fungsi obyektif dapat diubah menjadi pencarian maksimum fungsi obyektif yang lain dan demikian pula sebaliknya. Dengan demikian, pencarian nilai minimum diatas memiliki solusi yang sama dengan masalah dual-nya, yaitu pencarian nilai maksimum. Jika fungsi objektif dan kendala tidak lagi linier, fungsi dari peubah x ini dapat ditulis sebagai c(x) dan kendala dapat ditulis sebagai .

Metode Basis Pursuit dengan Pemrograman Linier

Metoda basis pursuit merumuskan pencarian basis ideal didalam kamus-basis berdimensi NxM sebagai masalah pemrograman konveks:

(P₁):

Telah diketahui sejak lama bahwa optimisasi non-linier l₁ seperti ini ekivalen dengan LP

jika dilakukan substitusi sebagai berikut

M↔2M; x↔ ; c↔[1 1 …. 1; 1 1… 1]; A↔ ; b↔s

Artinya, kamus-basis digabung dengan nilai negatif dari kamus tersebut untuk menggantikan peran matriks A, batas kendala b digantikan dengan sinyal s, panjang vektor solusi dibuat menjadi dua-kalinya, sedangkan fungsi objektif adalah penjumlahan masing-masing koefisien vektor solusi sparse dan dimensi kolom diperbesar menjadi duakali-nya.

Cara ini selanjutnya akan dipakai untuk memecahkan masalah dekomposisi sinyal s terdahulu yang terdiri dari dua impuls dan dua vektor basis DCT. Sebagai tambahan, sinyal ini tercampur dengan derau acak Gaussian. Berikut ini kode Matlab-nya.

%———————————————–

%Basis pursuit on overcomplete basis

%Using Matlab Optimization Toolbox

%To search for solution … modified

%———————————————–

%length of signal

clear;close all;clc;

N=64; %signal dimension

over_factor=2; %over complete factor

nAtoms=N*over_factor;

%create pair of orto-basis dictionary

D1=eye(N,N); D2=dct(eye(N,N)); D=[D1;D2]‘;

%create a signal with N_support’

N_support=4;

pN=[8 32 73 125]; %dpt diganti dng indeks acak jika perlu

x=zeros(N,1); X=zeros(nAtoms,1);%’transformed-domain signal

for k=1:N_support;

x=x+D(:,pN(k)); X(pN(k))=1;

end;

x0=x;

figure(1);plot(x0);title(‘Original Signal’);

%perform measurement, >> add noise

derau=randn(N,1);

y = x0 + 5*derau/(derau’*derau);

min_y=min(y);

D_pos=-D;

%define dictionary A

A=zeros(N,2*over_factor*N);

A(:,1:over_factor*N)=D;

A(:,over_factor*N+1:2*over_factor*N)=D_pos;

%Basis Pursuit on random basis

f=ones(2*nAtoms,1); lb=zeros(2*nAtoms,1);

alpha=linprog(f,[],[],A,y,lb);

figure(2);plot(1:nAtoms,X,’r:’,1:nAtoms,alpha(1:nAtoms),’b–’);

legend(‘original’,'alpha’);

%obtain a few largest component, by sorting alpha

[z,imax]=sort(alpha(1:nAtoms));

%Reconstruct estimated signal

x_hat=zeros(N,1);

for k=1:N_support;

x_hat=x_hat+ D(:,imax(nAtoms-k+1));

end;

x_hat1=D*alpha(1:nAtoms);

figure(3);plot(1:N,x0,’k.’,1:N,y,’b-’,1:N,x_hat,’r:’,1:N,y-x0,’g-’,1:N,x_hat1,’k–’);

legend(‘original’,'noisy’,'estimated’,'noise-level’,'D*alpha’);

figure(4);plot(1:N,y-x0,’r-’,1:N,x_hat-x0,’b-’,1:N,x_hat1-x0,’k-’);

legend(‘initial error’,'estimation error’,'D*alpha error’);

Gabungan pasangan sistem-basis impulse-DCT menghasilkan sebuah kamus-basis berukuran 64×128. Batas sparsity Elad-Bruckstein untuk pasangan basis ini adalah sekitar (0.9).8 atau sekitar 7. Dengan hanya mengambil 4 buah vektor basis penyusun, yaitu vektor pada urutan ke 8, 32, 73, dan 125 haruslah P1 dapat menemukan solusi eksak-nya.

Gambar 2. Vektor basis terpilih didalam kamus basis

Gambar 2 menunjukkan vektor basis terpilih oleh P1 yang tepat berhimpit dengan basis penyusun sinyal. Dengan demikian seluruh komponen sinyal telah berhasil ditemukan. Disamping itu, koefisian basis lainnya jauh lebih kecil daripada komponen basis penyusun. Komponen ini biasanya dihilangkan dengan peng-ambangan (tresholding).

Gambar 3. Sinyal asal dan hasil rekonstruksi

Gambar 4. Sinyal kesalahan

Berbagai sinyal dibandingkan dalam Gambar 3. Terlihat bahwa sebenarnya tingkatan sinyal derau (kurva berwarna hijau) cukup tinggi jika dibandingkan dengan sinyal asalnya (titik-titik hitam), menghasilkan distorsi yang signifikan (sinyal warna biru). Namun demikian, karena semua koefisien berhasil ditemukan, sinyal dapat direkonstruksi secara eksak. Hal ini ditunjukkan pada Gambar 4, dimana sinyal kesalahan (biru) berharga nol.

Catatan: Beberapa browser menerjemahkan karakter ‘prime’ secara salah sehingga program yang ada di blog ini tidak bisa langsung di-copy paste dari halaman web ke Command Window Matlab untuk dijalankan. Perbaiki terlebih dahulu kesalahan ini sebelum menjalankan program.

Dekomposisi Sinyal dan Pencarian Basis Ideal (3)

Pencarian basis untuk pasangan transformasi waktu-frekuensi dapat diperluas untuk sebarang pasangan basis ortonormal. Berbagai macam basis baru yang telah ditemukan seiring maraknya penelitian wavelet dan analisis multiresolusi, baik yang ortonormal (mis. wavelet, Fourier, DCT, Hadamard, ridgelets), yang tak-ortonormal (mis. Gabor, pseudo-polar FFT), maupun transformasi non-kuadratis (Laplacian pyramid, wavelet invarian-geser) perlu dielaborasi supaya bisa dipakai untuk menyatakan berbagai macam bentuk sinyal yang ditemui di dunia nyata. Pencarian vektor basis ”ideal” didalam gabungan berbagai macam basis memerlukan generalisasi sifat keunikan dari representasi sinyal sparse. Tulisan ini memberikan penjelasan secara garis besar hasil-hasil yang telah dicapai oleh Elad-Bruckstein dan perbandingannya dengan formulasi dari Donoho.

Batas Keunikan Elad-Bruckstein dari Pasangan Orto-basis

Pada tulisan terdahulu telah diberikan batas Donoho-Huo (DHB: Donoho-Huo Bound) dari jumlah komponen penyusun sinyal untuk setiap pasangan sistem basis ortonormal (ortobasis) dan supaya sinyal dapat dinyatakan secara unik dan P₁ sanggup menemukannya, yaitu

Batas P₁ Donoho-Huo:

dimana adalah koherensi antar basis. Pada kasus pasangan ortobasis ini, Elad dan Bruckstein memberikan batas yang lebih baik, sehingga cukup penting untuk dijelaskan terlebih dahulu.

Sebuah sinyal s sepanjang N-cuplikan dapat dinyatakan dalam sebarang sistem ortobasis, misalnya sebagai atau . Sebagaimana yang telah disinggung pada tulisan sebelumnya, koherensi antar sistem basis dapat dinyatakan sebagai

Koherensi pasangan basis: (1)

Jumlah support sinyal s dari kedua kawasan adalah . Untuk setiap dua bilangan bulat positif x dan y, maka akan berlaku sifat . Karena maka akan berlaku pula , sehingga . Dengan demikian relasi berikut akan berlaku:

Teorema 1. (2)

Hubungan antara dua suku terakhir pada pertidaksamaan diatas, yaitu , dapat dijelaskan dengan analisis sederhana sebagai berikut:

1. Nilai minimum terjadi jika keduanya basis impuls yang hanya memiliki satu komponen vektor bernilai tak-nol dan , sehingga dan . Untuk pasangan basis ini, nilai koherensi mencapai maksimum atau sehingga berlaku.
2. Disisi lain, nilai maksimum terjadi jika semua komponen dari vektor dan tak nol, misalnya jika keduanya basis Hadamard. Pada saat tersebut dan . Nilai koherensi akan mencapai nilai maksimum juga, yaitu . Dengan demikian juga berlaku.

Akhirnya diperoleh hubungan antara koherensi dengan batas dari jumlah koefisien dikedua kawasan, yaitu:

Batas P₁ Elad-Bruckstein: (3)

Batas atas ini tentu lebih baik daripada yang telah diperoleh Donoho-Huo sebelumnya, yang untuk kasus sinyal s ini dapat dituliskan:

Batas P₁Donoho-Huo: (4)

Andaikan bahwa sinyal ternormalisasi (berenergi satu satuan) s dapat dinyatakan dengan dua cara berbeda didalam kamus-basis , yaitu . Dengan demikian

Akibatnya atau . Berdasarkan prinsip ketidakpastian, maka

, atau

Ini berarti bahwa dua representasi dari sinyal yang sama tidak akan sekaligus sparse. Akhirnya diperoleh hasil berikut:

Teorema 2. Jika ada suatu representasi yang memenuhi syarat

batas keunikan P₀ Elad-Bruckstein: (5)

maka haruslah representasi itu unik atau yang paling sparse.

Sampai dengan tahap ini, pencarian basis ideal masih mengandalkan P₀. Tahap berikutnya adalah mencari batas sparsity dimana P₁ sanggup menemukan solusi yang identik dengan solusi P₀.

Untuk suatu sinyal , dengan asumsi sparsity pada dan jumlah koefisien k₁<k₂ sehingga vektor

memiliki k₁ buah koefisien tak nol dalam N koefisien pertama (yaitu di dalam ) dan k₂ buah tak nol untuk N koefisien kedua (didalam ), Elad-Bruckstein mendapatkan hasil berikut:

Jika k1 dan k2 memenuhi hubungan , maka P₁ akan dapat menemukannnya.

Hasil yang lebih lemah tapi bentuknya sederhana diberikan oleh , sehingga

Batas Keunikan P₁ Elad-Bruckstein: (6)

Sebagai ilustrasi, untuk sinyal s sepanjang N=1024 cuplikan yang tersusun dari komponen pasangan basis impulse-Fourier, maka P₀ akan sanggup menemukan solusi untuk 32 vektor basis. Bandingkan dengan P₁ yang memberikan harga lebih kecil lagi, yaitu 16 menurut DHB. Untuk kasus pasangan basis ini, EBB memberikan angka untuk P₁ yang lebih besar, yaitu 29 buah.

Batas Keunikan P₀ dan P₁ untuk Kamus Basis

Keunikan untuk sepasang ortobasis telah diturunkan secara langsung dari prinsip ketidakpastian. Sebuah kamus basis bersifat overcomplete, yakni jumlah vektor basisnya jauh lebih banyak dari yang seharusnya cukup untuk membentuk sebuah vektor berdimensi N. Andaikan suatu sinyal s sepanjang N-cuplikan dapat dinyatakan dalam dua representasi didalam kamus-basis yang dinyatakan sebagai matriks berdimensi NxK, dimana K>>N , dengan demikian atau

Hasil terakhir menyatakan kombinasi linier vektor-vektor kolom dari yang saling bergantung dan akan dicari sekelompok vektor yang demikian. Untuk keperluan ini akan diperkenalkan konsep spark dari suatu matriks yang dilambangkan sebagai sebagai berikut

Definisi. Spark dari suatu matriks yang dituliskan sebagai adalah bilangan bulat terkecil yang menyatakan banyaknya anggota dari sekelompok vektor kolom dari yang saling bebas.

Berikut ini ilustrasi dari konsep nilai spark untuk dua buah matriks yang sederhana.

sedangkan

Apa hubungannya dengan rank? Rank sebuah matriks adalah jumlah maksimum vektor kolom yang saling-bebas, sedangkan spark adalah jumlah minimum vektor kolom yang tidak-saling-bebas. Secara umum hubungan berikut ini akan berlaku:

Berdasarkan definisi, untuk sinyal s yang diatas akan berlaku , dengan demikian atau .Akhirnya untuk kamus basis akan diperoleh hubungan yang mirip dengan prinsip ketidakpastian yaitu

(7)

yang artinya bahwa dua buah representasi berbeda dari suatu sinyal s didalam kamus-basis tidak boleh keduanya sekaligus sparse. Selanjutnya akan diperoleh persyaratan keunikan sinyal s sebagai berikut

Teorema 3. Representasi sinyal dimana akan bersifat unik.

Koherensi suatu kamus-basis dapat didefinisikan dengan cara yang mirip seperti pasangan orto-basis sebagai berikut

Koherensi kamus-basis: [8]

Berdasarkan teorema piringan Gershgorin, dapat ditunjukkan bahwa batas bawah (pesimistik) spark adalah . Dengan demikian, dari [8] akan diperoleh

dan dari Teorema 3 akan diperoleh

Teorema 4. Representasi sinyal dimana akan bersifat unik.

Dengan cara yang sama seperti sebelumnya, keunikan sinyal s didalam kamus basis terhadap optimasi P₁ dapat dinyatakan sbb;

Teorema 5. Diberikan suatu sinyal s dengan representasi , jika maka P₁ atau algoritma Basis Pursuit akan dapat menemukannya.

Apa bedanya dengan yang diperoleh Donoho-Huo pada tulisan sebelumnya? Perbedaan pertama, jumlah support dari sinyal yang dibentuk pasangan orto-basis dalam penurunan Elad-Bruckstein lebih tinggi dari yang diberikan Donoho-Huo. Yang kedua, Elad-Bruckstein memberikan generalisasi dari pasangan basis ortogonal ke kamus-basis dengan batas sparsity yang diberikan oleh (9).

Contoh Permasalahan

Soal-1: Tentukan koherensi antara ortobasis DCT dan ortobasis acak tersebar normal, masing-masing berdimensi 512×512. Tentukan batas sparsity untuk P₁ berdasarkan DHB (Donoho-Huo Bound) dan EBB (Elad-Bruckstein Bound).

Jawab: Perhatikan bahwa sistem yang ditinjau adalah dua orto-basis, bukan kamus-basis. Dengan demikian, perhitungan koherensi akan memakai rumus (2) sedangkan batas sparsity adalah rumus (1) untuk DHB dan rumus (6) untuk EBB. Kode Matlab berikut dapat dipakai.

% progam menghitung koherensi dan batas sparsity

% antara basis DCT dengan basis acak Gaussian

clear;close all;clc;

N=512; %panjang sinyal yang diasumsikan

%buat basis DCT berdimensi NxN

THETA=dct(eye(N,N));

%buat basis acak Gaussian NxN

PSI=orth(randn(N,N)’)';

%hitung koherensi antara DCT dengan Gauss

mu_DCT_Gauss=mu_THETA_PSI(THETA,PSI);

disp(sprintf(‘koherensi DCT-Gauss = %f\n’, mu_DCT_Gauss));

%Tentukan batas sparsity

%kasus-1: DHB (Donoho-Huo bound)

N_DHB=floor(0.5*(1+1/mu_DCT_Gauss));

disp(sprintf(‘batas sparsity Donoho-Huo= %d\n’, N_DHB));

%kasus-2: EBB (Elad-Bruckstein bound)

N_EBB=floor((sqrt(2)-0.5)/mu_DCT_Gauss);

disp(sprintf(‘batas sparsity Elad-Bruckstein= %d’, N_EBB));

%==FUNGSI ===

%fungsi menghitung koherensi dua orto basis

function [mu]=mu_THETA_PSI(THETA,PSI);

[M,N]=size(PSI); %THETA diasumsikan berdimensi sama

CORR=transpose(conj(THETA))*PSI;

mu=max(max(CORR));

Hasil perhitungan memberikan nilai koherensi , DHB =2, dan EBB = 4. Terlihat perbedaan cukup signifikan antara EBB dengan DHB.

Soal-2: Tentukan tingkat koherensi dari sebuah kamus-basis acak tersebar normal yang berdimensi 64×1024 dan hitunglah batas sparsity dari sinyal s sepanjang 64 cuplikan yang terbentuk dari kamus-basis ini!

Jawab: Didalam compressive sensing, basis acak dapat dianggap sebagai basis universal karena bersifat hampir ortogonal ke semua sistem basis lain. Koherensi dihitung menurut rumus (7) sedangkan batas sparsity memakasi rumus (9). Program Matlab berikut ini dapat dipakai untuk membantu pemecahan masalah ini.

% progam menghitung koherensi dan

% batas sparsity basis acak Gaussian

clear;close all;clc;

N=64;M=1024; %dimensi kamus basis

%buat basis acak Gaussian MxN

D=orth(randn(N,M)’)';

%hitung koherensi kamus basis D

mu=mu_PHI(D);

disp(sprintf(‘koherensi kamus-basis = %f\n’, mu));

%Tentukan batas sparsity

N_sparse=floor(0.5*(1+1/mu));

disp(sprintf(‘batas sparsity = %d’, N_sparse));

% === fungsi yang dipakai ===

%fungsi menghitung koherensi kamus basis

function [mu]=mu_PHI(PHI);

[M,N]=size(PHI);

CORR=transpose(conj(PHI))*PHI;

mu=max(max(CORR));

Hasil running program Matlab diatas menghasilkan nilai koherensi dan batas sparsity sebesar 5. Dengan demikian, sebarang sinyal sepanjang 64 cuplikan yang terbentuk dari kombinasi linier kamus basis berukuran 64×1024 akan dapat ditemukan dengan optimasi P₁ atau algoritma Basis Pursuit.

Referensi

1. M.Elad and A.M. Bruckstein, “A generalized uncertainty principle and sparse representation in pairs of bases”, IEEE Trans. on Information Theory, Vol. 48, pp. 2558-2567, September 2002.
2. D. L. Donoho and M. Elad, “Maximal sparsity representation via l1 minimization”, Proc. of the National Academy of Science, Vol. 100, pp. 2197-2202, March 2003.
3. S.S. Chen, D. Donoho, and MA Saunders, ”Atomic decomposition by basis pursuit,” SIAM J. on Scientific Computing, 20(1):33-61, 1999.

Dekomposisi Sinyal dan Pencarian Basis Ideal (2)

Penggabungan berbagai basis ortogonal menjadi sebuah kamus basis-lewat-lengkap (overcomplete) diharapkan dapat menaikkan efisiensi dekomposisi sinyal. Peningkatan kinerja sistem kompresi terjadi karena dua hal: (1) tingkat kompresi tinggi karena koefisien yang diambil hanya sedikit, dan (2) sejumlah kecil koefisien tadi sudah cukup untuk merekonstruksi sinyal secara baik. Namun demikian pencarian vektor didalam basis overcomplete dengan kriteria cacah koefisien terkecil memerlukan sumberdaya komputasi yang sangat besar. Melalui prinsip ketidakpastian, masalah ini dapat diubah menjadi optimisasi konveks yang lebih mudah dipecahkan. Syaratnya, sinyal harus bersifat sparse.

Tinjau gabungan M buah sistem basis ortogonal yang masing-masing berukuran N×N menjadi satu buah basis overcomplete . Basis baru ; yang juga disebut sebagai dictionary (kamus basis), akan memiliki dimensi N×MN. Suatu sinyal s=[s₁ s₂ ... s_N]^T sepanjang N cuplikan dapat dinyatakan dengan berbagai macam kombinasi linier vektor-vektor basis yang ada didalam , bahkan dari masing-masing sistem basis ortogonal karena bersifat lengkap. Dengan pertimbangan efisiensi yang merupakan tuntutan kompresi sinyal, haruslah dipilih kombinasi yang berbentuk:

(1)

dimana adalah vektor basis didalam . Pada penjumlahan tersebut menyatakan bahwa komponen tersebut adalah vektor basis ke–i didalam sistem basis . Pertimbangan efisiensi mengharuskan cacah , yaitu

(2)

sekecil mungkin. Sebagai ilustrasi arti norm diatas , tinjau contoh perhitungan berikut ini.

Suatu dictionary yang merupakan hasil penggabungan 2 buah basis ortogonal memiliki dimensi 4×2, dimana
, , dan

Tiga dari empat basis didalam ini dapat dipakai untuk menyatakan sebuah sinyal yang panjangnya dua cuplikan, misalnya . Sinyal ini dapat terbentuk dari , masing-masing dengan koefisien . Dengan demikian , sehingga

Terlihat bahwa norm diatas hanya menghitung cacah dari koefisien terpilih.

Pencarian basis representasi sinyal s didalam dengan cacah terkecil disebut sebagai masalah (P₀) yang dapat dinyatakan sebagai optimisasi berikut:

(3)

Mengingat ada sejumlah tak-berhingga solusi dari sistem persamaan linier yang underdetermined, apakah nilai minimum ini dapat ditemukan? Untuk pasangan basis waktu-frekuensi, Donoho memberikan batasan supaya pencarian menemukan solusi yang unik dengan menggunakan prinsip ketidakpastian sebagai berikut.

Teorema 1. Jika s(n) adalah sinyal waktu diskrit sepanjang N cuplikan yang memiliki N_t buah support (koefisien tak-nol), sedangkan S(k) adalah transform Fourier sinyal tersebut yang memiliki N_w buah support, maka atau
(4)

Jika cuplikan yang bernilai tak-nol (support) dari sinyal di kedua wilayah kurang dari setengah batas prinsip ketidakpastian diatas, maka P₀ akan memiliki solusi yang unik.

Teorema 2. Tinjau sinyal s(n) yang tersusun dari himpunan T vektor basis kawasan waktu dan himpunan basis dari kawasan frekuensi. Jika
(5)
maka P₀ akan memiliki solusi yang unik. Sementara itu akan ada sinyal s(n) lain sedemikian hingga dan P₀ akan memiliki solusi yang tidak unik.

Pada teorema ini, notasi |.| menyatakan kardinalitas atau banyaknya anggota himpunan. Donoho menunjukkan hasil diatas dengan meninjau kasus fungsi ekstremal sisir Dirac (Dirac comb) yang telah dijelaskan sebelumnya. Untuk N bilangan kuadrat sempurna (perfect square), misalnya 4, 9, 16, … dst, sisir Dirac memiliki support sebesar di kawasan waktu maupun kawasan frekuensi. Ini berarti bahwa sebuah sisir Dirac dapat dinyatakan sebagai buah vektor basis impuls atau buah basis Fourier, sehingga representasinya didalam basis gabungan impuls-Fourier tidaklah unik. Akibatnya solusi dari P₀ juga tidak unik. Sebaliknya, jika jumlah support-nya kurang dari , maka akan hanya ada satu buah solusi saja, sehingga solusi P₀ akan bersifat unik.

Meskipun solusinya unik, memecahkan masalah P₀ bukanlah hal yang mudah. Untuk mengatasi hal ini, Chen dan Donoho mengajukan teknik Basis Pursuit, yaitu dengan menggantikan P₀ dengan optimisasi P₁ sebagai berikut:

(6)

Keberadaan solusi P₁ memerlukan batasan support sinyal didalam yang lebih kecil lagi, yaitu kurang dari setengah batas P₀. Untuk basis waktu-frekuensi, ketentuan ini dinyatakan dalam teorema berikut.

Teorema 3. Untuk sinyal s seperti pada Teorema 2, jika

maka solusi dari P₁ adalah unik, yang juga merupakan solusi unik untuk P₀. Sementara itu, ada sinyal yang jika dimana P₁ memiliki solusi yang tidak unik.

Sinyal dengan support dibawah batas ketentuan P₁ ini disebut sebagai sinyal sparse karena dapat dibentuk hanya dari sejumlah kecil vektor basis didalam . Secara singkat dapat dirangkum sebuah hasil penting berikut ini:

Jika suatu sinyal s bersifat sparse dalam kawasan waktu-frekuensi, maka dekomposisinya bersifat unik dan algoritma Basis Pursuit atau P₁ akan dapat menemukannya.

Bagaimana dengan pasangan basis selain waktu-frekuensi? Pada tulisan sebelumnya dikatakan bahwa prinsip ketidakpastian di sebarang kawasan telah diperumum oleh Elad dan Bruckstein dengan memasukkan faktor koherensi antara sistem basis yang secara konsisten akan kembali menjadi WHUP jika kedua basis adalah pasangan waktu-frekuensi. Dasar pemikiran ini dipakai oleh Elad-Bruckstein maupun Donoho-Huo untuk menghasilkan teorema keunikan dari solusi P₁ berikut.

Teorema 4. Andaikan adalah gabungan kedua basis. Jika suatu sinyal waktu diskrit s dapat dinyatakan sebagai dengan memenuhi syarat
(7)
maka adalah solusi unik dari P₁ dan juga sekaligus merupakan solusi unik dari P₀.

Dalam bahasa yang kurang-teknis, teorema ini mengatakan bahwa suatu sinyal s yang terbentuk dari kombinasi linier vektor-vektor basis didalam kamus-basis dapat ditemukan vektor basis penyusunnya dengan memecahkan masalah optimisasi (P₁), asalkan jumlah vektor basis penyusun sinyal ini kurang dari nilai tertentu.

Seberapa besar signifikansi perubahan optimisasi P₀ menjadi P₁? Meskipun sekilas optimisasi ini hanya mengubah norm dari l₀ menjadi l₁, perubahan yang terjadi sangat besar. Saat ini, kebanyakan algoritma optimisasi didalam pengolahan sinyal justru menggunakan kriteria atau fungsi biaya kuadratis yang tak lain adalah l₂. Penjelasan diatas bahkan menginginkan pencarian solusi ideal dengan kriteria l₀. Dari sudut pandang pencarian ruang solusi, optimisasi dengan kriteria l₂ dan l₁ bersifat konveks, sedangkan l₀ bukan konveks. Algoritma untuk mencari solusi dari optimisasi konveks yang efisien telah banyak tersedia. Transformasi dari masalah l₀ menjadi l₁ ini disebut juga sebagai proses konveksifikasi.

Salah satu contoh sederhana didalam statistik mengenai berbagai norm ini adalah perhitungan mencari nilai tengah dari populasi. Meminimumkan nilai kesalahan kuadrat terkecil, yang tak lain adalah l₂, akan menghasilkan nilai mean cuplikan, sedangkan jika yang diminumkan adalah nilai absolut kesalahan atau l₁, solusinya akan berupa median. Pada pengolahan sinyal atau citra dijital, para peneliti menemukan bahwa tapis median lebih kokoh (robust) terhadap derau jika dibandingkan dengan tapis mean. Analogi yang sama dapat dipakai untuk menjelaskan mengapa P₁ ini memiliki peranan yang sangat penting dalam pencarian basis sinyal yang ideal.

Referensi

[1]. M. Elad and A.M. Bruckstein, “A generalized uncertainty principle and sparse representation in pairs of basis,” IEEE Trans. Info. Theory, 49. 2558-3567.

[2]. S.S. Chen, D. Donoho, and MA Saunders, ”Atomic decomposition by basis pursuit,” SIAM J. on Scientific Computing, 20(1):33-61, 1999.

[3]. DL Donoho & PB Stark, ”Uncertainty principles and signal recovery”, SIAM J. on Applied Math., 49(3):906-31, 1989.

[4]. DL Donoho & X. Huo, Uncertainty Principles and Ideal Atomic Decomposition, Tech. Report, Stanford University.

Dekomposisi Sinyal dan Pencarian Basis Ideal (1)

Pemanfaatan transformasi ortogonal untuk kompresi sinyal telah ditunjukkan pada tulisan sebelumnya. Secara intuitif dapat difahami bahwa sistem kompresi menghendaki terkumpulnya energi di kawasan transformasi hanya ke sejumlah kecil koefisien supaya tingkat kompresi nya tinggi dengan kualitas hasil rekonstruksi yang terjaga. Namun demikian hal ini tidak selalu bisa dilakukan karena bagaimanapun setiap sistem basis hanya cocok untuk segolongan sinyal-sinyal tertentu saja. Basis sinusoid dalam transformasi Fourier atau DCT melakukan pengkompakan energi dengan baik jika sinyal asalnya tersebar di kawasan waktu. Sebaliknya, sinyal yang terlokalisir dalam kawasan ini sebaiknya memakai basis impuls atau wavelet.

Gambar 1. Beberapa vektor basis impuls

Gambar 2. Beberapa vektor basis DCT

Gambar diatas memperlihatkan beberapa vektor basis dari sistem basis impuls dan sistem basis DCT . Sifat lokalisasi sinyal terlihat dengan jelas pada kedua gambar; basis impuls terlokalisir sedangkan DCT tersebar. Program Matlab berikut dapat dipakai untuk menampilkan vektor-vektor basis seperti diatas.

%———————————————–

% Sistem Basis Impuls dan DCT

%———————————————–

N=64; %dimensi vektor basis

x=1:N; %buat sumbu x

PHI=eye(N,N); %Basis Impulse

PSI=dct(eye(N,N)); %Basis DCT

figure(1);plot(x,PHI(2,:),x,1+PHI(4,:),x,2+PHI(8,:),…

x,3+PHI(16,:),x,4+PHI(32,:),x,5+PHI(60,:));

title(‘Vektor basis impuls’);

figure(2);plot(x,PSI(2,:),x,0.5+PSI(4,:),x,1+PSI(8,:), …

x,1.5+PSI(16,:),x,2+PSI(32,:),x,2.5+PSI(60,:));

title(‘Vektor basis DCT’);

Suatu sinyal biasanya merupakan campuran dari komponen yang terlokalisir dan yang tersebar. Basis mana yang harus dipilih dalam kasus yang demikian? Tinjau suatu sinyal s(n) yang terbentuk dari sistem basis berupa vektor basis ke-4 dan ke-32 dan dua buah lainnya dari sistem basis , yaitu vektor basis ke-8 dan ke-60. Prinsip kompresi sederhana yang sudah dijelaskan dapat dicobakan untuk setiap sistem basis, yaitu dengan mengalikan matriks transformasi-nya dengan vektor s(n),

Dekomposisi sinyal ke basis impuls:

Dekomposisi sinyal ke basis DCT:

Langkah berikutnya, ambil beberapa koefisien dengan energi (magnitudo) terbesar. Tentu cara lain dapat dilakukan, misalnya tresholding dengan mencari koefisien-koefisien yang energi/magnitudo-nya berada diatas ambang nilai tertentu. Untuk indeks dari koefisien latex {\hat{s}}_{1}(n)=\sum_{k \in K}{S}_{1}(k) \Phi(k) &s=-2 $

Rekonstruksi dengan basis DCT:

Kinerja dari rekonstruksi sinyal dapat dilihat dari energi sinyal kesalahan (error) rata-rata atau RMSE (Root Mean Square Error) masing-masing, yang dinyatakan sebagai:

, dimana

Semakin kecil nilai ini, maka secara obyektif hasil rekonstruksi semakin baik. Nilai RMSE yang besar menandakan terjadinya distorsi signifikan pada sinyal.

Gambar 3. Sinyal asli s(n)

Gambar 4. Magnitudo koefisien terurut

Gambar 3 menunjukkan sinyal asal s(n) berupa gabungan dua sinusoid dan dua sinyal impuls. Sinyal ini akan didekomposisi dengan basis impuls dan kemudian dengan basis DCT. Dekomposisii sinyal ini kedalam sistem basis tersebut akan menghasilkan koefisien yang dinyatakan sebagai vektor S₁ dan S₂. Untuk mengamati sebaran energi, magnitudo atau nilai mutlak S₁ dan S₂ diurutkan dan kemudian dibuatkan kurvanya. Kedua kurva diberikan pada Gambar 4. Terlihat bahwa, meskipun beberapa koefisien awal dominan, penurunan nilai energi koefisien lainnya tidaklah terlalu tajam. Dengan demikian, pengambilan sejumlah kecil komponen dominan akan tetap menghasilkan sinyal kesalahan yang cukup tinggi energinya. Ini artinya rekonstruksi sinyal kurang berhasil.

Gambar 5. Perbandingan sinyal asli dengan hasil rekonstruksi

Gambar 6. Sinyal kesalahan

Gambar 5 memperlihatkan hasil rekonstruksi dengan menggunakan delapan buah vektor basis. Kurva biru merupakan hasil dari basis impuls, sedangkan kurva merah dari basis DCT. Perbandingan dengan sinyal asli yang dinyatakan sebagai titik-titik berwarna hitam memperlihatkan beda yang cukup signifikan. Perbedaan ini semakin jelas setelah sinyal kesalahan e₁(n) dan e₂(n) diperlihatkan pada Gambar 6.

Gambar 7 Kinerja RMSE

Kinerja rekonstruksi dapat dievaluasi dengan mengukur RMSE berbagai jumlah vektor basis seperti yang diperlihatkan pada Gambar 7. Penurunan RMSE terjadi secara perlahan dan mencapai nol ketika seluruh N vektor basis diikutsertakan; yang artinya tidak ada kompresi. Program Matlab berikut dapat dipergunakan untuk menunjukkan proses proyeksi dan rekonstruksi diatas.

% Pencarian basis

clear;%close all;clc;

N=64; %dimensi vektor basis

x=1:N; %buat sumbu x

PHI=eye(N,N); %Basis Impulse

PSI=dct(eye(N,N)); %Basis DCT

%bentuk sinyal dari basis DCT saja

s1=zeros(N,1);s1=zeros(N,1);

s1=(PHI(4,:)+PHI(32,:))’;

s2=(PSI(8,:)+PSI(60,:))’;

s=zeros(N,1); s=s1+s2;

figure(1);plot(x,s); title(’sinyal kombinasi impuls dan DCT’);

xlabel(‘n’);ylabel(’s(n)’);

S1=PHI*s; S2=PSI*s; %cari koefisien

%urutkan koefisien dan ambil dua terbesar

[S1_oval,S1_oidx]= sort(abs(S1),’descend’);

[S2_oval,S2_oidx]= sort(abs(S2),’descend’);

% rekonstruksi sinyal

s_hat1=zeros(N,1); s_hat2=zeros(N,1);

for k=1:8; s_hat1=s_hat1+(S1(S1_oidx(k))*PHI(S1_oidx(k),:))’; end;

for k=1:8; s_hat2=s_hat2+(S2(S2_oidx(k))*PSI(S2_oidx(k),:))’; end;

%hitung kesalahan

e1=s-s_hat1;e_rms1=sqrt(e1′*e1)/N;

disp(sprintf(‘rms error-Impulse %f’,e_rms1));

e2=s-s_hat2;e_rms2=sqrt(e2′*e2)/N;d

isp(sprintf(‘rms error-DCT %f’,e_rms2));

figure(2); plot(x,S1_oval,’r-’, x,S2_oval,’b-’);

title(‘magnitudo koefisien terurut’);

xlabel(‘index’);ylabel(‘|S|-terurut’);

legend(‘proyeksi Impuls’,'proyeksi DCT’);

figure(3);plot(x,s,’k.’,x,s_hat1,’b:’,x,s_hat2,’r-’);

title(‘perbandingan hasil rekonstruksi’);

xlabel(‘n’);ylabel(’s(n)’); legend(‘asli’,'rek. impuls’,'rek. DCT’);

figure(4);plot(x,e1,’r-’,x,e2,’b–’);title(’sinyal kesalahan’);

xlabel(‘n’);ylabel(‘e(n)’);

legend(’sinyal error impulse’,’sinyal error DCT’);

%data error beberapa nilai k

x_e=[2 4 8 16 32 64]‘;

e_PHI=[2.18e-2 2.05e-2 1.78e-2 1.33e-2 5.94e-3 0.0]‘;

e_PSI=[2.16e-2 2.02e-2 1.77e-2 1.32e-2 6.28e-3 0.0]‘;

figure(5);plot(x_e,e_PHI,’r-’,x_e,e_PSI,’b-’); title(‘kinerja RMSE pengkodean’);

xlabel(‘jumlah koefisien’);ylabel(‘RMS Error’); legend(‘Impulse’,'DCT’);

Melihat hasil yang kurang baik saat menggunakan satu buah basis ortogonal saja, apakah mungkin kinerja-nya meningkat seandainya dua atau lebih sistem basis digabungkan? Memang cara inilah yang paling masuk akal, akan tetapi cara ini menimbulkan satu masalah besar lainnya. Gabungan kedua basis akan menghasilkan suatu basis baru yang dimensinya menjadi Nx2N. Dilihat dari sistem persamaan linier, permasalahan menjadi lebih sulit dipecahkan karena kita harus mencari solusi dari N buah persamaan dengan 2N peubah yang tak diketahui . Sistem persamaan linier yang demikian disebut sebagai underdetermined.

Sebagai ilustrasi, tinjau suatu matriks transformasi A berukuran 2×2 yang bisa dianggap sebagai transformasi vektor pada bidang atau transformasi sinyal 2 cuplikan x=[x₁ x₂] menjadi y=[y₁ y₂]. Pencarian koefisien transformasi x(n) yang tepat dari sinyal teramati y(n) dapat dinyatakan sebagai persamaan matriks: Ax=y dengan x tak diketahui atau

Bentuk sistem persamaan liniernya adalah

Karena yang tak-diketahui ada dua {x₁, x₂} dan ada dua persamaan, jika matriks A tak-singular tau memiliki inverse, maka sistem persamaan linier diatas dapat dipecahkan dengan eliminasi Gauss atau mengalikan inverse A dengan vektor [y₁ y₂ ]^T dari kiri.

Sebaliknya, penggabungan sistem basis A dengan basis baru B menjadi D=[A;B] akan membuat persamaan matriks diatas menjadi

Atau dinyatakan sebagai sistem persamaan linier berikut:

Sistem persamaan linier ini terdiri dari empat buah variabel, yaitu {x₁, x₂, x₃, x₄} sedangkan jumlah persamaan hanya ada dua. Karena masing-masing sistem basis bersifat lengkap, akan ada banyak sekali kombinasi yang dapat muncul untuk menyatakan suatu vektor y. Pencarian basis ke seluruh ruang solusi memerlukan sumberdaya komputasi yang sangat besar karena termasuk permasalahan kombinatorial. Bagaimana cara mengatasinya?

Prinsip Ketidakpastian dan Kompresi Data (3)

Pada kawasan diskrit, WHUP dinyatakan sebagai penjumlahan RoS (Region of Support) dari waktu- dan frekuensi- diskrit sinyal. Prinsip ini dapat diperumum untuk sebarang pasangan kawasan melalui hubungan matriks transformasi atau himpunan fungsi basis-nya. Batas daerah dukung ditentukan oleh tingkat koherensi antar basis ini.

Prinsip Ketidakpastian untuk Kawasan Waktu-Frekuensi Diskrit

Prinsip ketidakpastian Weyl-Heisenberg (WHUP) melarang sebuah sinyal kontinyu untuk terlokalisir pada kawasan waktu dan frekuensi sekaligus. Derajat lokalisasi suatu sinyal dinyatakan sebagai lebar/luas wilayah dimana sinyal ini memiliki nilai yang tidak nol, atau daerah-dukung (RoS-region of support) dari fungsi atau sinyal tersebut. Sebagai contoh, fungsi delta Dirac hanya memiliki nilai tak nol pada waktu t=0; dengan demikian RoS-nya adalah satu. Sebaliknya, sinyal sinusoidal terbentang ke seluruh kawasan waktu sehingga memiliki RoS di kawasan waktu yang tak berhingga.

Pengertian RoS untuk sinyal (waktu-) diskrit mirip dengan penjelasan diatas, yaitu daerah atau sekumpulan indeks waktu n dimana sinyal diskrit s(n) bernilai tak nol. Sinyal diskrit s(n) sepanjang N cuplikan akan memiliki transform Fourier

; dimana k = 0, 1, 2, …, N-1.

Untuk sinyal ini, WHUP menyatakan bahwa penjumlahan RoS (yang dilambangkan sebagai supp) sinyal di kawasan waktu dan RoS di kawasan frekuensi dibatasi oleh suatu nilai tertentu, yakni:

Nilai terkecil dari jumlah kedua RoS ini, yaitu , dicapai oleh fungsi Dirac Comb yang support-nya bersifat invarian terhadap transformasi Fourier. Fungsi ini dinyatakan sbb:

Gambar berikut ini memperlihatkan sinyal s(n) dan transform Fouriernya untuk kasus N=16.

Sifat ini menunjukkan bahwa batas bawah dari prinsip ketidapkastian adalah ketat (tight), dan telah dipenuhi oleh sebuah fungsi ekstremal berupa Dirac comb. Kedua gambar sinyal diatas dapat dibuat dengan memanfaatkan script Matlab berikut ini:

%————————————————–

%Sifat Invarian Sisir Dirac (Dirac Comb)

%terhadap Transformasi Fourier

%—————————————————

clear; clc;

N=16; s=zeros(N,1);

sqrt_N = round(sqrt(N));

maxIdx = floor(N/sqrt_N);

for m=1:maxIdx; s(m*sqrt_N) =1; end

figure(1);stem(s);title(‘Time-domain Dirac Comb’);

xlabel(‘Time’);ylabel(‘Amplitude’);

%Dirac Comb in Frequency Domain

S=fft(s)/sqrt(N);

figure(2);stem(abs(S)); title(‘Frequency domain abs(Dirac Comb)’)

xlabel(‘Frequency’);ylabel(‘Magnitude’);

Prinsip Ketidakpastian untuk Sebarang Kawasan Diskrit

Apakah prinsip ketidakpastian berlaku juga untuk pasangan kawasan selain waktu-frekuensi? Seperti telah diuraikan pada tulisan sebelumnya, suatu sinyal dapat dilihat dari berbagai kawasan melalui transformasi. Transformasi pada dasarnya adalah perubahan basis dan operasi untuk sinyal diskrit dapat dilihat sebagai perkalian antara vektor sinyal dengan matriks transformasi .

Suatu matriks transformasi akan berisi vektor-vektor basis lengkap yang membentang ruang vektor. Ini berarti bahwa setiap sinyal dalam kawasan ini dapat dilihat sebagai kombinasi linier dari vektor-vektor basis tersebut. Untuk sepasang basis ortonormal (saling tegak-lurus dan panjangnya satu) dan , Elad dan Bruckstein memperkenalkan sebuah prinsip ketidakpastian yang diperumum atau GUP (Generalized Uncertainty Principle):

dimana:

Pada ekspresi diatas, adalah support dari sinyal dalam basis (kawasan) , sedangkan, adalah support dari sinyal dalam basis (kawasan) . Besaran disebut koherensi (mutual coherence) antara kedua basis dan haruslah memenuhi syarat

Koherensi menggambarkan tingkat keserupaan kedua basis: nilainya akan kecil jika keduanya berbeda dan akan bernilai satu jika mereka identik.

Sebagai contoh, tinjau kasus WHUP kawasan diskrit yang merupakan kasus khusus dari GUP. Sinyal s(n) berada pada kawasan waktu memiliki pasangan S(k) pada kawasan frekuensi. Bisa dianggap bahwa s(n) memiliki basis berupa matriks identitas I, sedangkan S(k) memiliki basis Fourier diskrit. Dengan demikian bisa dianggap bahwa pasangan basis ini adalah

dimana:

Nilai maksimum dari perkalian skalar vektor basis akan tercapai untuk sebarang pasangan vektor dan semuanya akan menghasilkan koherensi yang bernilai sama dengan akibat faktor normalisasi dari basis Fourier. Dengan demikian GUP akan menjadi atau seperti pada WHUP untuk kasus diskrit yang telah diuraikan sebelumnya. Tingkat koherensi beberapa pasangan basis lain dapat dihitung dengan menggunakan kode Matlab berikut ini.

%Hitung koherensi beberapa pasangan basis

N=4; %dimensi basis

I=eye(N,N); %basis identitas / waktu

DFT=fft(eye(N,N))/(sqrt(N)); %basis DFT

H2=[1 1 1 1; 1 -1 1 -1; 1 1 -1 -1; 1 -1 -1 1]/2;

mu1=mu_GUP(I,DFT); %koherensi waktu-frekuensi

disp(sprintf(‘Koherensi basis waktu-frekuensi %f\n’,mu1));

mu2=mu_GUP(H2,DFT); %koherensi Hadamard-Fourier

disp(sprintf(‘Koherensi basis Hadamard-Fourier %f\n’,mu2));

% === FUNGSI %====

function [mu_value]= mu_GUP(PHI, PSI);

% fungsi untuk menghitung koherensi dua buah sistem basis

% untuk memperlihatkan Generalized Uncertainty Principle

% masukan: PHI, PSI dua buah matriks berdimensi sama

[M,N]=size(PHI);

G=PHI’*conj(PSI);

mu_value = sqrt(M)*max(max(abs(G)));

Seperti pada kompresi dengan matriks ortogonal, metoda CS (compressed sensing) juga mengambil komponen dominan dari suatu sistem basis. Namun demikian, basis yang dipakai bersifat overcomplete, dimana ada banyak sekali kemungkinan memilih basis yang sesuai untuk menyatakan suatu sinyal. Oleh karena itu perlu kendala tambahan agar solusi bisa ditemukan, yakni sinyal yang direkonstruksi dianggap bersifat sparse. Metoda CS memerlukan dua buah basis pada saat melakukan pencuplikan atau sensing, yaitu sparsity basis dan projection basis . Tingkat koherensi kedua basis menentukan batas minimum banyaknya cuplikan untuk merekonstruksi suatu sinyal secara eksak.

Prinsip Ketidakpastian dan Kompresi Data (2)

Prinsip ketidakpastian Weyl-Heisenberg memiliki konsekuensi yang penting untuk pengolahan sinyal, yaitu sinyal kontinyu yang tersebar dalam kawasan waktu akan terlokalisir dalam kawasan frekuensi dan demikian pula sebaliknya. Perubahan sinyal antar kawasan pada prinsip ini terhubung melalui transformasi Fourier. Tulisan ini memperlihatkan bahwa prinsip ketidakpastian dapat berlaku untuk sinyal waktu diskrit. Disini juga diperkenalkan adanya konsep kawasan yang lebih umum. Sifat penting transform Fourier berupa pengumpulan energi ke sejumlah kecil koefisien ternyata juga dimiliki oleh beberapa transformasi ortogonal atau uniter. Sifat ini dapat dimanfaatkan untuk melakukan kompresi sinyal secara sederhana, yaitu dengan memilih koefisien transform yang dominan dan membuang sisanya.

Prinsip Pengolahan Sinyal secara Dijital
Supaya dapat diolah oleh komputer atau pengolah DSP (Digital Signal Processor), sinyal-sinyal alami yang analog seperti suara atau gambar harus terlebih dahulu diubah menjadi sinyal dijital. Prinsip pengolahan sinyal secara dijital digambarkan dalam diagram blok berikut ini.

Diagram Blok Pengolahan Sinyal Dijital

Pengolah ini menerima masukan sinyal listrik analog dari pengindera atau transducer, yaitu sinyal s(t) yang merupakan berisikan campuran dari sinyal dikehendaki s_a(t) dan sinyal lain s’_a(t). Tapis (filter) antialiasing berfungsi untuk menghapus s’_a(t) sehingga tinggal s_a(t) yang mengandung semua informasi didalam pita frekuensi yang akan diolah. Pada gambar diperlihatkan sinyal akan menjadi lebih ”halus” setelah melalui tapis ini karena komponen frekuensi tinggi diluar pita kerja sudah hilang.

Blok S/H (sampling and hold) mengambil cuplikan sinyal kontinyu dalam kawasan waktu secara periodik dan akibatnya sinyal berubah menjadi sinyal waktu diskrit s_a(n), dimana n adalah bilangan bulat. Sinyal ini masih memiliki amplitudo kontinyu. Karena pengolah bekerja dengan register terbatas, sinyal ini terlebih dahulu diubah menjadi sinyal dijital oleh perangkat A/D (analog to digital converter). Sebuah kartu ADC biasanya telah dilengkapi dengan tapis antialiasing dan perangkat S/H. Keluaran dari A/D ini akan berupa sinyal dijital s(n).

Pengolah dijital (DSP processor) selanjutnya memproses sinyal sesuai dengan tujuan saat perancangan, misalnya penapisan lolos rendah, lolos tinggi, dst. Bagian ini mengubah sinyal asal s(n) menjadi sinyal y(n).

Supaya bisa disajikan kembali ke pengguna, sinyal dijital y(n) harus dikembalikan menjadi sinyal analog dengan memakai perangkat D/A (digital to analog converter). Selanjutnya sebuah tapis rekonstruksi untuk menghilangkan cacat akibat konversi dijital ke analog, dan akhirnya diperoleh keluaran y_a(t) yang siap disajikan.

Aljabar Pengolahan Sinyal

Sinyal dijital dapat dianggap sebagai suatu deretan bilangan dan dapat dituliskan sebagai vektor kolom. Sebagai contoh, vektor s=[2 3 7]^T menyatakan sebuah sinyal dijital sepanjang 3 cuplikan. Karena berbentuk vektor, manipulasi atau pengolahan sinyal ini dapat dilakukan dengan operasi-operasi matriks atau vektor, misalnya penjumlahan atau pengurangan, perkalian dengan skalar, perkalian dengan matriks, dll.

Salah satu proses yang sangat penting didalam DSP adalah transformasi sinyal. Pada dasarnya transformasi sinyal adalah proses mengubah sinyal dari suatu kawasan ke kawasan yang lain. Secara geometrik transformasi sinyal pada hakekatnya merupakan perubahan sistem koordinat.

Pandangan Geometrik dari Transformasi Sinyal

Gambar diatas memperlihatkan sinyal asal s yang berada dalam sistem koordinat (x, y, z) diubah menjadi sinyal S dalam sistem koordinat baru (x’, y’, z’) melalui transformasi T. Kita bisa menganggap vektor basis dari koordinat asal sebagai {i, j, k}={(1,0,0), (0,1,0), (0,0,1)}, sedangkan vektor basis dari koordinat yang baru adalah {i’, j’, k’}.

Menurut Aljabar Linier, transformasi dari vektor s menjadi vektor S dapat dinyatakan sebagai perkalian antara vektor s dengan matriks transformasi T, yakni

S= Ts

Ada sekelompok transformasi penting didalam pengolahan sinyal yang disebut sebagai transformasi ortogonal, dimana semua vektor basis-nya memiliki panjang satu satuan dan bersifat saling tegak lurus. Transformasi ini bersifat mempertahankan panjang atau magnitudo vektor s. Secara geometrik transformasi yang demikian akan merupakan suatu perputaran sistem koordinat. Rotasi terhadap sumbu z sebesar sudut q dapat dinyatakan sebagai transformasi dengan matriks:

Akibat rotasi terhadap sumbu-z sebesar 45 derajat, maka sinyal s=[2 3 7]^T pada contoh sebelumnya akan berubah menjadi sinyal S = [-0.71 3.54 7.00]^T. Perhitungan ini dapat dilakukan dengan bantuan Matlab sebagai berikut:

%** Transformasi sinyal **

s=[2 3 7]‘, % sinyal asli

% ** Definisikan matriks transformasi **

T=[cos(pi/4) -sin(pi/4) 0; sin(pi/4) cos(pi/4) 0; 0 0 1];

S=T*s, % sinyal hasil transformasi

Matriks Transformasi Uniter dan Ortogonal

Transformasi uniter merupakan bentuk umum dari transformasi ortogonal dimana vektor basis-nya memiliki magnitudo satu satu satuan, saling tegak lurus, tetapi nilai komponennya berupa bilangan kompleks. Transformasi Fourier adalah contoh dari transformasi uniter. Matriks DFT dapat diperoleh secara mudah dengan Matlab dengan melakukan operasi fft terhadap suatu matriks identitas yang berukuran NxN

% cara-1: kalikan sinyal dengan matriks DFT

s=[2 3 7]‘, % sinyal asli

N=length(s);

U=fft(eye(N,N))/sqrt(N); %bentuk matriks DFT 3×3

S1= U*s, % hasil transformasi Fourier

%cara-2: langsung dengan perintah fft

S2=fft(s)/sqrt(N), %sama dengan S1

Tranformasi sinyal s pada contoh terdahulu memerlukan pembentukan matriks DFT berukuran 3´U. Perkalian dari matriks U dengan s menghasilkan sinyal kawasan frekuensi yaitu S, yang dalam kode Matlab diatas akan sama dengan S1 maupun S2.

Kita akan memakai hasil diatas untuk menunjukkan konsep-konsep penting yang dibahas sebelumnya. Yang pertama, suatu matriks U disebut uniter jika perkalian matriks ini dengan transpose dari konjugasi kompleksnya menghasilkan matriks satuan, atau U^*T×U = I. Kedua, kita akan memeriksa berlakunya Teorema Parseval yang menyatakan bahwa pengukuran energi dikawasan waktu akan sama dengan hasil pengukuran energi dikawasan frekuensi, atau s^*T×s = S^*T×S. Dan yang terakhir, kita akan melihat sifat pengkompakan energi dengan memeriksa sebaran energi dikawasan frekuensi E = S×S^*. Script Matlab berikut dapat ditambahkan pada script sebelumnya:

S=S1; % dan ini sama juga dng S=S2

% Cek sifat uniter, T. Parseval, dan sebaran

conj(transpose(U))*U, %jika uniter akan menghasilkan I berukuran NxN

E_waktu=sum(conj(transpose(s))*s), %Energi kawasan waktu

E_frekuensi=sum(conj(transpose(S))*S) , %Energi kawasan frekuensi

E_dist_frek = S.*conj(S), %sebaran energi

Analisis terhadap hasil perhitungan pada kode diatas memberikan kesimpulan bahwa U memang memiliki sifat uniter karena hasil perkalian dengan konjugasi transpose-nya menghasilkan matriks identitas. Perhitungan juga memberikan nilai energi kawasan waktu sebesar E_waktu=62 dan energi kawasan frekuensi sebesar E_frekuensi=62, jadi keduanya identik dan Teorema Parseval telah dipenuhi. Hal yang juga menarik terdapat pada sebaran energi dikawasan frekuensi, yakni E_dist_frek=[48.0 7.0 7.0]^T. Disini terlihat bahwa energi hasil transformasi telah terkumpul pada sejumlah kecil koefisien, dalam hal ini hanya pada koefisien yang pertama saja.

Disamping matriks DFT yang dijelaskan diatas, beberapa matriks ortogonal atau uniter lain juga memiliki sifat pengkompakan energi. Disini akan ditinjau dua buah matriks ortogonal yang sering dipakai untuk melakukan transformasi sinyal, yaitu matriks DCT dan matriks Hadamard. Terlebih dahulu sinyal asal diperpanjang menjadi empat cuplikan, misalnya s=[2 3 7 11]^T. Dengan demikian haruslah dipilih matriks DCT dan Hadamard yang ukurannya 4´4, masing-masing diberi notasi D dan H₂.

Matriks DCT dapat diperoleh dengan perintah Matlab dct(eye(4,4)), sedangkan matriks Hadamard bisa dibentuk secara rekursif dengan konstruksi Sylvester, yaitu melalui perkalian Kronecker dengan matriks dasar H₁.

Script Matlab berikut ini dapat dipakai untuk mempelajari sifat-sifat penting kedua transformasi ortogonal tersebut.

%transformasi ortogonal: DCT dan Hadamard

s=[2 3 7 11]‘, % sinyal asli

N=length(s);

%bentuk matriks transformasi

D=dct(eye(N,N)); %bentuk matriks DCT 4×4

H2=[1 1 1 1; 1 -1 1 -1; 1 1 -1 -1; 1 -1 -1 1]/2;

S_dct= D*s, % hasil transformasi DCT

S_had= H2*s, % hasil transformasi Hadamard

E_asli= sum(transpose(s)*s), %energi sinyal asal

E_dct =sum(transpose(S_dct)*S_dct) , %Energi kawasan DCT

E_hadamard =sum(transpose(S_had)*S_had) ,

%Energi kawasan Hadamard

E_dist_dct = S_dct.*S_dct, %sebaran energi DCT

E_dist_had = S_had.*S_had, %sebaran energi Hadamard

%gambarkan sebaran energi

figure(1); bar(E_dist_dct); title(‘Sebaran energi di kawasan DCT’);

figure(2); bar(E_dist_had); title(‘Sebaran energi di kawasan Hadamard’);

Perhitungan dengan script diatas menegaskan kembali berlakuknya hukum konservasi energi yang tersirat dari Teorema Parseval, karena diperoleh hasil E_asli=E_dct=E_had = 183. Sifat pengkompakan energi juga ditemukan dikedua transformasi ini. Sebaran masing-masing energi digambarkan dalam histogram berikut ini

Sebaran Energi Sinyal di Kawasan DCT

Sebaran Energi Sinyal di Kawasan Hadamard

Kompresi Data dengan Transformasi Ortogonal

Kompresi data sederhana dapat dilakukan dengan cara memilih beberapa koefisien yang memiliki energi dominan dan membuang yang lain. Sebagai contoh, hasil transformasi DCT untuk sinyal s adalah S=[11.5 -6.9 1.5 0.1]^T. Jika dipilih dua komponen dominan saja (untuk kompresi sebesar dua kali) dan mengisi komponen sisanya dengan nol, maka kita akan memperoleh pendekatan dari S , yaitu S_hat = [11.5 -6.9 0 0]. Hasil transformasi balik sinyal ini (dengan perintah Matlab: D’*[11.5 -6.9 0 0]‘ ) akan memberikan nilai pendekatan dari sinyal asal sebesar s_hat=[1.2 3.9 7.6 10.3]. Sebaliknya, jika dua komponen tak-dominan yang dipilih, maka dengan tingkat kompresi yang sama akan diperoleh s_hat1= D’*[0 0 1.5 0.1]‘=[0.8 -0.8 -0.7 0.7]^T yang sama sekali berbeda dengan sinyal aslinya. Ukuran dari baik-buruk-nya pendekatan sinyal yang satu terhadap yang lain dapat ditentukan dengan menghitung jarak Euclidian kedua sinyal. Caranya: kurangkan kedua sinyal komponen demi komponen, lalu kuadratkan setiap beda komponen dan jumlahkan. Akar kuadrat dari hasil terakhir menunjukkan jarak yang kita cari. Analisis untuk transformasi Hadamard sejalan dengan penjelasan ini, tinggal menggantikan D dengan H₂.

Pada tulisan sebelumnya telah diperoleh hasil berupa implikasi tak-langsung dari WHUP, yaitu sinyal yang tersebar dikawasan waktu akan terkumpul di kawasan frekuensi dan begitu pula sebaliknya. Tulisan ini menunjukkan hasil WHUP dengan Matlab dengan cara menghitung energi dari koefisien transformasi Fourier diskrit. Sifat ini juga dimiliki oleh transformasi ortogonal atau uniter yang lainnya, misalnya transformasi DCT dan transformasi Hadamard. Sebuah teknik kompresi data sederhana, yaitu dengan mengambil dua dari komponen dominan koefisien transformasi DCT, telah dijelaskan. Hasil inversi dari data kawasan transformasi yang telah dikompresi dengan cara ini lebih menyerupai sinyal aslinya jika dibandingkan dengan pilihan koefisien lainnya.

Kompresi JPEG (versi lama) memakai DCT dan bukan transformasi Fourier karena pertimbangan praktis. Menyimpan koefisien kompleks yang terdiri dari bagian riil dan imajiner terlalu merepotkan dan kurang efisien. Lagipula, DCT adalah hampiran yang cukup baik dari transformasi ideal KLT (Karhunen-Loeve Tranform) untuk sinyal acak Gauss-Markov orde satu, sebuah model yang mendekati sinyal alami. Cara kerja kompresi JPEG mirip dengan kompresi sederhana yang telah dijelaskan dengan tambahan adanya kompresi tak-merugi berupa entropy coding.

Penutup dan Tulisan Mendatang

Pada “kompresi” DCT diatas telah dipilih komponen yang dominan dan letaknya bisa berubah bergantung pada sinyal masukannya, meskipun pada JPEG letak komponen dan alokasi bit-nya telah ditentukan sebelumnya. Pemilihan yang mengikuti bentuk sinyal seperti ini disebut sebagai pemilihan koefisien secara adaptif; ini adalah masalah yang sebaiknya dihindari. Terlebih lagi kompresi dilakukan pada data dijital yang pada saat dikumpulkan (pemotretan gambar atau perekaman suara) menghasilkan sejumlah besar data yang kemudian dibuang pada saat kompresi. Teknik terbaru yang disebut sebagai Compressed Sensing/ Compressive Sampling (CS) menghindari cara yang tidak efisien seperti ini. Disamping itu, CS juga tidak memerlukan pencuplikan koefisien dominan secara adaptif karena semua komponen sama pentingya, dapat diambil yang manapun asalkan batas minimum jumlah cuplikan terpenuhi. Jumlah cuplikan yang diperlukan untuk rekonstruksi sinyal didalam CS ternyata jauh dibawah batas Nyquist yang dinyatakan oleh Teorema Shannon. Teori CS memerlukan generalisasi dari hubungan waktu-frekuensi supaya prinsip ketidakpastian tetap berlaku. Tulisan mendatang akan mengulas teknik CS ini dengan lebih rinci.

Numerologi dan Motif Rangkaian Invarian

Problema Desainer: ”Sebuah perusahaan multinasional yang bermarkas di kawasan BHTV, yaitu Invariant Circuits Ltd, memproduksi peralatan elektronik bernama Invarray. Perusahaan ini melayani berbagai macam pembeli; mulai dari perorangan, universitas/ lembaga riset, industri telekomunikasi, sampai badan ruang angkasa. Elemen dasar Invarray adalah Frakcell, suatu komponen yang diproduksi secara massal dan semuanya memiliki impedansi (tahanan) seragam sebesar R. Pada dasarnya Invarray adalah Frakcell yang dirangkai secara serial, paralel, self-similar dan kombinasinya. Karena rangkaian penyesuai impedansi juga diproduksi massal dengan impedansi yang juga seragam, diinginkan agar berapapun Frakcell yang terpasang, impedansi total dari Invarray tetap sama, yaitu sebesar R. Kinerja alat yang dibuat dan ongkos pembuatannya sebanding dengan M, jumlah Frakcell yang ada dalam suatu Invarray. Jika bentuk desain rangkaian apapun dapat dilayani tanpa tambahan biaya, berikan desain dan nilai M terdekat sesuai pesanan tanpa mengorbankan kinerja alat ini.”

Permasalahan yang dihadapi dalam mendesain rangkaian invarian kurang lebih dapat dinyatakan dalam Problema Desainer seperti diatas. Desainer dalam PT Invariant Circuit harus berpikir keras agar jumlah FrakCell dalam Invarray sesedikit mungkin, tetapi kinerja minimal yang diinginkan pemesan dapat dipenuhi. Karena pemesan bervariasi, mulai dari peneliti perorangan sampai dengan badan ruang angkasa sekelas, ada baiknya desainer punya tabel atau basis data desain.

Analisis lebih lanjut menunjukkan adanya berbagai macam kombinasi rangkaian invarian yang dapat dibuat. Bahkan, untuk jumlah tahanan M yang sama bisa jadi ada banyak pilihan desain atau ada berbagai motif/ topologi. Dengan demikian permasalahan ini sebenarnya tidak sesederhana, oleh karena disini hanya akan ditinjau beberapa desain saja.

Desain pertama tentu adalah R_F^[k] terdahulu yang akan kita sebut sebagai (rangkaian invarian) Tipe-1, dengan jumlah resistor yang dibutuhkan sebesar M₁=(4)^k dimana k=0, 1, 2, … dst. Dengan demikian, resistor sebanyak M₁ = 1, 4, 16, 64, … akan secara sempurna membentuk Tipe-1 ini.

Gambar 1. Rangkaian Invarian Type 2

Variasi dari Tipe 1 diperoleh jika satu sisi dari segiempat pada jembatan digantikan dengan R_F, sedangkan sisanya dibiarkan sebagai satu buah R saja. Selanjutnya, pengembangan ke orde tinggi hanya dilakukan pada R_F seperti diperlihatkan pada Gambar 1. Bentuk ini akan disebut sebagai Tipe 2 dan memiliki nilai M₂= 4^k+3 untuk k=0, 1, 2, … dst. Dengan demikian jumlah resistor yang dapat dipakai adalah M₂ = 4, 7, 19, 67, …dst.

Gambar.2 Rangkaian Invarian Tipe 2.A

Jika perkalian Kronecker dilakukan pada elemen dasar pada Tipe 2, akan didapatkan jenis baru dari rangkaian invarian yang akan dinamakan sebagai Tipe 2.A. TIpe ini membutuhkan resistor sejumlah M_2A= 7^k dimana k=0, 1, 2, 3, … dst sehingga M_2A = 1, 7, 49, 343, 2401 … dst.

Gambar 3. Rangkaian Invarian Tipe 3

Proses yang sama seperti sebelumnya pada pembentukan Tipe 2 dapat dilakukan dengan menggantikan satu lagi tambahan R_F pada elemen dasar Tipe 1. Hasilnya adalah Tipe 3 dengan M₃= 2(4^k)+2; dimana k = 0, 1, 2, 3, … dst atau M₃=4, 10, 34, 130, … dst.

Gambar 4. Rangkaian Invarian Tipe 3.A

Selanjutnya, perkalian Kronecker dari elemen dasar Tipe 3 tersebut akan menghasilkan jenis baru yaitu Tipe 3.A dimana M_3A= 10^k; k=0, 1, 2, … dst sehingga diperoleh M_3A = 1, 10, 100, 1000, 10.000, …dst

Gambar 5. Rangkaian Invarian Tipe 4

Proses diatas dapat dilanjukan untuk memperoleh Tipe 4, yaitu menyisakan hanya satu lengan yang terdiri dari satu R sedangkan 3 yang lain adalah R_F. Tipe-4 akan memiliki M₄= 3(4^k)+1; k=0, 1, 2, 3, … dst sehingga diperoleh M₄=4, 13, 49, 193, … dst.

Gambar 6. Rangkaian Invarian Tipe 4.A

Rangkaian invarian Tipe 4.A diperoleh dari perkalian Kronecker pada elemen dasar Tipe 4. Dengan demikian jumlah tahanan yang dibutuhkan untuk membangun tipe ini adalah M_4A= 13^k; k=0, 1, 2, … dst sehingga diperoleh M_4A=1, 13, 169, 2197, … dst.

Gambar 7. Rangkaian Invarian Tipe 5

Disamping itu yang telah disebutkan diatas, ada lagi bentuk lain yang lebih sederhana yaitu dengan cara merangkai seri/paralel k buah resistor secara bergantian. Kita sebut jenis ini sebagai Tipe 5 dengan jumlah tahanan sebesar M₅=k² dimana, k=0, 1, 2, … dst. Dengan demikian maka M₅= 1, 4, 9, …. dst. Desain ini diusulkan oleh salah seorang pengunjung ber-identitas masadi.

Gambar 7. Rangkaian Invarian Type-6

Sementara itu pengunjung lain, Budi Sulistyo, memberikan desain yang juga tidak kalah uniknya. Langkah pembentukannya sbb: Sebuah rangkaian yg terdiri dari: (1R) diseri dgn (2R yg diparallel), maka akan diperoleh 3/2 R. Misal nilai ini kita lambangkan dgn R’.Kemudian 3 buah rangkaian_1 ini (R’) dirangkai dalam bentuk segitiga: (2R’ diseri) diparallel dgn (1R’) sehingga diperoleh nilai: 2/3 R’. Jadi nilai total hambatan adalah 2/3 * (3/2 R)=R. Hasilnya kita sebut sebagai Tipe 6 dengan M₆=3^2k = 9^k, dimana k=0, 1, 2, … dst, atau M₆= 1, 9, 81, 729, … dst.

Sebagai rangkuman, dari beberapa desain diatas kita telah mendapatkan nilai-nilai M sebagai berikut:

M₁ = 1, 4, 16, 64, …, 4^k, …

M₂ = 4, 7, 19, 67, …, 4^k+3, …

M_2A = 1, 7, 49, 343, …, 7^k, ….

M₃ = 4, 10, 34, 130, … , 2(4^k)+2, …

M_3A = 1, 10, 100, 1000, 10.000, …, 10^k, …

M₄ = 4, 13, 49, 193, …, 3(4^k)+1, …

M_4A = 1, 13, 169, 2197, …, 13^k, …

M₅ = 1, 4, 9, …., k², …

M₆ = 9, 81, 729, …, 9^k, …

Problema Desainer dapat dinyatakan kedalam suatu permainan (game). Jenis permainan ini mungkin cocok dilombakan pada seleksi asisten lab atau calon dosen Teknik Elektro …

Invariant Game: Setiap pemain diberikan M buah resistor yang nilai tahanannya seragam sebesar R. Peserta diminta untuk membuat rangkaian dengan menggunakan resistor yang disediakan sebanyak mungkin selama tahanan total yang dirangkai tetap bernilai R. Pemenang adalah pemain yang berhasil merangkai tahanan terbanyak atau yang menyisakan tahanan paling sedikit.

Punya usulan desain lainnya?

Tentu saja masih banyak bentuk rangkaian lain disamping yang telah diberikan diatas. Pembaca yang ingin menyampaikan hasil rancangannya dapat membuat dan memperlihatkan desain tsb di web dan kemudian mengirimkan alamat web tersebut ke komentar di blog ini. Selain gambar beberapa iterasi awal (dengan format PNG atau JPG), sebaiknya ada keterangan mengenai proses pembentukan, nilai-nilai M yang memenuhi syarat, dan identitas diri (jika mau).