## Convolutional Code

Unlike block codes, convolutional codes does not send the message followed by (or interspersed with) the parity bits. In a convolutional code, the sender sends only the parity bits.

The encoder uses a a sliding window to calculate r > 1 parity bits by combining various  subsets of bits in the window. The size of the window, in bits, is called the code’s constraint length. the longer the constraint length, the larger to number of parity bits that are influenced by any given message bit. Because the parity bits are the only bits sent over the channel, a larger constraint length generally implies a greater resilience to bit errors. The trade-off is that it will take more time to decode codes for more constraint length.

If a convolutional code that produces r parity bits per windows and slides the window forward by one bit at a time, its rate is 1/r. The greater the value of r, the higher the resilience of bit errors, but the trade-off is that a proportionally ginger amount of communication bandwidth is devoted to coding overhead. In practice, it is more commen to pick 4 and the constraint length to be as small as possible while providing a low enough resulting probability of a bit error.

This is an example of a convolutional code with rate 1/2:

This is a systematic 1/3 encoder:

And this is a 2/3 encoder:

To make the convolutional code able to cope with more errors, it is not by changing the k or n (r = k/n). But by adding more memory inside the encoder (the square with D letter). Notes that all the circles with plus symbol (or the xor process) is the generator functions to determine each output. It works just like other generator of other error correction codes.

This is the Trellis Diagram of the first convolutional code:

Trellis Diagram is a graph whose nodes are ordered into vertical slices (time), and with each node at each time connected to at least one node at an earlier and at least one node at a later time. The earliest and latest times in the trellis have only one node.

This diagram gives “spatial” and “temporal” information about the code. “Temporally” it shows the state on each t while “spatially” it shows every possible route defined by the encoder design. Later, the decoding would be done by comparing the received “route” with the “most likely route” to track down the error and then correct it.

Viterbi is a scheme for decoding, using maximum likelihood decoding that set up a threshold to check the “route” with the “deviated route”.

References:

1. MIT 6.02 DRAFT Lecture Notes, Fall 2010 (Last update: October 4, 2010)
2. http://en.wikipedia.org/wiki/Trellis_(graph)
3. “Error Control Coding”, Shu Lin and Daniel J. Costello

## Amdahl’s Law and Price Elasticity

I have just noticed that Amdahl’s Law used in measuring processor performance is similar with the Price Elasticity Law (I read from the book “Starbucks (Corporations that Changed the World) – Marie Bussing-Burks”) in economic concepts.

The same principle is that there is a limit in increasing processing performance to get more throughput, or to rephrase it in business language: there is a limit in reducing price of an item to get more revenue.

Amdahl’s Law says that speedup is how a machine performs after enhancement. A SpeedUp(E) = Performance with E / Performance without E = Execution time without E / Execution time with E. Execution time = Execution time unaffected + (Execution time with E / Amount of improvement).

(Notes: Examples is taken from EL 2244 Course being taught at ITB this semester. The reference book is John L. Hennessy and  David A. Patterson , Computer Organization and Design: The Software Hardware Interface, Morgan Kaufmann Publishers, 4th Edition, 2009.)

Ex. 1:

A program runs in a machine in 10s. 50% of the time is doing multiplications. If we improve the multiplication unit so it runs twice as fast, how big is the speed up?

Answer:

Exec_time(E) = (Affected_exec_time/improvement) + unaffected_exec_time

= (5s/2) + 5s = 7,5 s

Speed_up(E) = 10s/7,5s = 1,333  which is not 2 times faster

Ex. 2:

A program runs for 10s. 70% of the time is doing additions. How much improvement on the additions if we want to reduce the running time to 3s?

Answer:

Exec_time(E) = (Affected_exec_time/improvement) + unaffected_exec_time

3s = (7s/n) + (10-7)s

3s = (7s/n) + 3s

0 = 7s/n

No amount of improvement can reduce the running time to 3s.

Now let’s see the Price Elasticity Law. Price Elasticity (E) = % change in quantity demand / % change in price.

Ex 1:

If we reduce the price of 36 inch TV from \$450 to \$400, the average price would be \$425. The absolute value of percentage change = \$50/\$425 = 0.118. Number of unit sold is increased from 200 to 300 so the average number of unit sold = 250.

So the percentage  of change in quantity demand is 100/250 x 100% = 40%.

The price elasticity = 0.4/0.118 = 3.39%

If the absolute value of price elasticity is between 0 – 0.99, demand is inelastic. Necessity items like coffee, milk, gasoline, prescription drugs are tend to be relatively insensitive to price change.

Ex 2:

A store manager drops the price of a gallon of milk from \$4 to \$3. The average price will be \$3.5. The absolute value of % change = \$1/\$3.5 = 0.29

Milk sold going from 10 to 11. The average number of gallon sold = 10.5. Percent of change in quantity demand = 1/10.5 = 0.1.

Price elasticity = 0.1/0.29 = 0.34. The demand is inelastic.

So if demand is elastic, a price cut will increase total revenue (and an increase in price will mean lower total revenue). If we take Ex 1:

price x quantity = total revenue

\$450 x 200 = \$90,000

\$400 x 300 = \$120,000

While when demand is inelastic, a price cut will decrease total revenue. As in Ex 2:

\$4 x 10 = \$40

\$3 x 11 = \$33.

The conclusion is that in terms of machine performance and total revenue, there is a limit to get “improvement”. There is a certain point that we cannot further improve the speed of a machine as well as there is a certain point that we cannot change price to get more total revenue.

## Reed Solomon – A Brief Introduction

Reed Solomon is one brilliant error correction method that is a non-binary cyclic codes. The codeword looks like the picture below. It has symbols in m-bits. The bit string is treated as a group of bits. The group of bits is treated as non-binary. We will see how it makes this method powerful.

Let’s take an example of RS(15,11). This means that we have the codeword with length 15 bits that consists of original message 11 bits  and 4 bits for parity. t is how many errors (in symbols or group of bits) that can be corrected.

p(x) or irreducible polynomial is used to generate the finite field like shown in the table below.

Now we need a generator to start the encoding process.

The process of decoding includes several steps. Let’s take an example of double-symbol error.

The first process is computing the syndrome to detect the error. For this case will have 4 syndromes: S1, S2, S3 and S4. Each S that is not equal to 0 contains error.

The second step is locating the error in e(x). This can be done using matrix.

After the location has been determined, now it is the time to calculate the values of the error so we can correct the error.

Done. We get the message corrected. Do you notice that detecting the errors in symbols (groups of bits) in this method makes it runs faster?

## 2013 in review

The WordPress.com stats helper monkeys prepared a 2013 annual report for this blog.

Here’s an excerpt:

The concert hall at the Sydney Opera House holds 2,700 people. This blog was viewed about 17,000 times in 2013. If it were a concert at Sydney Opera House, it would take about 6 sold-out performances for that many people to see it.

Click here to see the complete report.

## PhoneGap – Getting Started using Xcode

1. Download and install NodeJS and PhoneGap
2. Type this in Terminal: (make sure you have a stable internet connection because this will affect the generation of the code like missing libraries, invalid structures of directories etc.)

You have to do this project creating and building on command prompt because in later versions of XCode, they do not give you to choose Cordova application or PhoneGap application when you start a new project like shown in this picture:
3. Find the .xcodeproj and run it (it will be opened automatically in XCode)
4. And then Run the project (by pressing the button on the top left) and you will get this

You can modify the index.html or .js scripts and see how they look in simulator.An error usually occurs (the error message would be “index.html not found” when there is no index.html in www directory or the structure of the directory is not like shown below.

Note:

1. The version I’m using is Xcode 5.0, iOS Simulator 6.1, PhoneGap 2.9.0 and node.js v0.10.20. Running on Mountain Lion 10.8.5
2. If you are using different versions in either of one of them, the result might be slightly different

• #### Ripiu Info 9:29 am on December 5, 2013 Permalink | Reply

Which one do you recomend, phonegap or native ios for newbie like me ?

• #### www.hubmesh.com 11:27 pm on June 25, 2014 Permalink | Reply

Many thanks for every other useful website. The place altogether different may possibly I receive that kind of information coded in a very perfect means? I’ve got a mission i’m right now operating upon, so i are actually with the be aware of similarly info.

• #### Collum 9:22 pm on July 1, 2014 Permalink | Reply

whoah this web site is usually amazing i like reading your content. Maintain the great work! You know, many men and women want circular with this info, you are able to encourage them to enormously.

## Snow Leopard vs Mountain Lion

I owned a White Macbook for more than 5 years, and feeling very happy using Leopard and then upgrading to Snow Leopard. After enduring a phd saga for 5 years, the Macbook’s casing started to crack here and there, and then I decided to give it to cadet#1 so that it can stay at home and hopefully will stop cracking.

I got myself a new MacBook Pro with Mountain Lion (Mac OS X 10.8.4), 2.5GHz Intel Core i5, 4GB 1600MHz DDR3. At first I was astonished with new things that Mountain Lion offers like more finger gestures, mission control, side notifications etc. But after a few days I started to realize that Mountain Lion is not as snappy and as responsive as Snow Leopard.

Mountain Lion takes several seconds after hibernation to be ready to accept password while Snow Leopard will accept it right away as I open the lid. After several days without restarting the OS, Mountain Lion will acting so slow while Snow Leopard works fine for weeks without being restarted. And when I open lots of tabs on the browser, or firing up web and database server, Mountain Lion sluggishness will acting up again.

Lots of people have been complaining about Mountain Lion, and they also say that Snow Leopard is the best Mac OS. So what to do? Downgrading?

This link gives 12 reasons why Mac runs slow with Mountain Lion, and one thing I definitely would do is upgrading the RAM. There are more tips here. I will write some report after I find more ways on how to deal with the sluggish Mountain Lion.

*Update: Everybody is suggesting to upgrade to SSD and highest possible RAM. Ok will do it. This is a useful link about how to install and additional SSD drive.

• #### Wildan 1:14 am on July 28, 2013 Permalink | Reply

My old MBP Core 2 Duo with SSD still fast on Mavericks DP :)
Upgrade to SSD and 16 GB RAM :D

• #### waskita 5:26 am on July 28, 2013 Permalink | Reply

This is 2012. Please use SSD and maximum possible RAM.

• #### CG 9:39 am on July 28, 2013 Permalink | Reply

have just updated the post and saved a link about upgrading to SSD. thx all.

• #### aya 9:58 pm on August 27, 2013 Permalink | Reply

Can you help mee with this lease ?? Use Verilog HDL to design a 2-bit comparator using 2×4 decoders and any gates required.

• #### aya 1:19 am on August 28, 2013 Permalink | Reply

Can you help me with this please ?? Use Verilog HDL to design a 2-bit comparator using 2×4 decoders and any gates required.

## Installing MAMP and CodeIgniter on Mountain Lion

Installing MAMP:

1. Download MAMP at  http://mamp.info/en/. Once the .dmg file is downloaded, double click on it if it did not unzip itself. Than drag the MAMP folder into Applications folder.
2. From Application folder, double click MAMP program and click “Start Servers”. At this point the web server, database server and application server has been activated on your Mac.
3. If you click Open Start Page, MAMP will show you the MAMP Page on your local webserver (http://localhost:8888/MAMP)
4. For more details on installing and MAMP setting up, read more here.

Installing CodeIgniter:

1. Download CodeIgniter here.
2. Unzip CodeIgniter by double-clicking it.
3. Rename CodeIgniter folder into “ci” (this is the common practice).
4. Copy the folder to the PHP and mySQL enabled server, which is, in this case is in Applications/MAMP/htdocs
5. Configure system/application/config/config.php by adding \$config['base_url'] = “http://localhost/ci/&#8221;;
6. Go to http://localhost/ci/
7. More about getting started with CodeIgniter here

• #### aya 9:58 pm on August 27, 2013 Permalink | Reply

Can you help me with this lease ?? Use Verilog HDL to design a 2-bit comparator using 2×4 decoders and any gates required.

• #### aya 1:19 am on August 28, 2013 Permalink | Reply

Can you help me with this please ?? Use Verilog HDL to design a 2-bit comparator using 2×4 decoders and any gates required.

• #### Victor 3:16 am on May 20, 2014 Permalink | Reply

Above it says to add \$config['base_url'] = “http://localhost/ci/”; are there suppose to be 2 semicolons?

• #### Victor 3:24 am on May 20, 2014 Permalink | Reply

I received and error after following your instructions and adding:
\$config['base_url'] = “http://localhost/ci/&#8221″;

The error reads..

Not Found

The requested URL /CI was not found on this server.

## Principles and Analogies of Error Correction Codes

I use a very abstract visual way to explain about different error correction algorithms. Here I will over-simplify every algorithm and then use visualizations instead, just to get the principle of how they works, and why.

Linear Block Code

In linear block code, every codewords will have n-k bits of redundant checkin part, and k-bits of message.

The generator matrix would look like this, where there is some identity matrix in it, that later will be used to generate syndrome to identify errors.

Hamming Code
The picture below shows how to identify error with even parity bits. The bits in black is the message, the bits in green is the parity to make sure that the number of 1 in a circle is even, the bit in red is the error, that later can be identified because the overlapping circle area will show where the error occur.

The Hamming Code works like shown by the table below, the parity bits (unlike the previous method) are inserted in certain positions (2^0, 2^1, 2^2 and 2^3) to make sure that each of every 4 bits of message is being screened so that later the error can be tracked.

Cyclic Code

This is my favorite. This method use the characteristic of polynomial in GF(2^n). So that identifying errors can be done by divide the codeword with the generator g(x). If the result is not 0, there is an error. Another thing that I like from this method is that every codeword is a shift from previous codeword (that’s why this method called “cyclic”) . So the implementation will be very easy, just shifting here and there (using LFSR), which in hardware implementation, is “costless”.

BCH Code

This method is a little bit complicated but the point is, to make a matrix H so that this matrix can screen out every bits (that’s why there are 2 rows that are linearly redundant).

Reed Muller

This one is interesting. This method has orders to identify different number of errors. Look at the matrix below. R(1,3) means that the order is 1 and the message length is 3. In Reed Muller, the pattern is obvious. Each vector in the matrix (x1, x2, x2) are used to search the location of error in convergence. Each row will direct the algorithm to a smaller space of error possibility location.

For R(2, 3), we have the same number bits of message, which is three, but this time in order 2. Means that the matrix will be expanded and thus, more error can be detected. The part of matrix in yellow is the “basic” vectors, while the green shows the “additional” vectors to help allocating more errors.

Now look at R(3,3). More rows of the matrix, and more errors to be detected.

So oversimplifyingly, I can say that error correction code, in principle, how to encode a message (to be a codeword) to get through a channel (error correction code is in domain channel coding, while data compression is in domain source coding) so that we would be able to make the message reliable (while in source coding, the target is not reliability but efficiency), by making sure that we can locate error and fix it. And the way to decode is like the illustration of quadtree below. The methods will generate matrix, or equations, or mathematical characteristic (polynomial groups etc) to help to narrow down the search space.

Quadtree

Hopefully this article can be useful, I will teach Reed Solomon Code next week, and let’s see if I can add up more things here, or publish a new blogpost.

• #### Jaka Arya Pradana (@aajap) 7:25 am on January 1, 2014 Permalink | Reply

Wah, tanggung Bu, kurang Reed Solomon :D
Thanks for writing, Bu :)

• #### CG 3:08 pm on January 1, 2014 Permalink | Reply

will do when i have time.thx :)

## Hello World – Erlang

The easiest way to install Erlang on MacOS is by downloading the .dmg of Erlang here. And then you will get Erlang installed.

And here’s the example of Hello World using Erlang.

Useful Links:

## Polynomial Basis Squaring

Finally have successfully found some spare time to do coding to solve this polynomial squaring:

And this is the result, x^5 + x + 1 :

• #### rudi 9:37 pm on May 30, 2013 Permalink | Reply

bu, akan lebih cantik kalo nulis polinomnya pake latex,
$x^5 + x+1$

• #### CG 11:00 am on May 31, 2013 Permalink | Reply

iya belum sempet dirapihin :D biasanya saya pake latex for wordpress

• #### Akshay 11:18 pm on July 26, 2013 Permalink | Reply

Hey please mail me this complete C code. sorry I’m not execute this ….please help me…please ..

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel