lib for the image processing stuff

This is the library file for that image processing project.

-- PPMlib.hs
-- Library for 433-152 Project 2007
-- Bernard Pope

module PPMlib where

import Text.ParserCombinators.Parsec

type Pixel = (Int, Int, Int)

data PPM
= PPM Int Int Int [Pixel]
deriving Show

getPixels :: PPM -> [Pixel]
getPixels (PPM _ _ _ ps) = ps

getWidth :: PPM -> Int
getWidth (PPM w _ _ _) = w

getHeight :: PPM -> Int
getHeight (PPM _ h _ _) = h

getMaxVal :: PPM -> Int
getMaxVal (PPM _ _ m _) = m

{- transform interface
example: transform verify greyScale "in.ppm" "out.ppm"
-}

transform :: (PPM -> Maybe String) -> (PPM -> PPM) -> String -> String -> IO ()
transform verify trans inFile outFile = do
result <- parser inFile
case result of
Left e -> print e
Right ppm -> do
case verify ppm of
Nothing -> do
let newPPM = trans ppm
case verify newPPM of
Nothing -> writeFile outFile $ pretty newPPM
Just err -> do
putStrLn "Error in transformed image"
putStrLn err
Just err -> do
putStrLn "Error in input image"
putStrLn err

{- pretty printing PPM files -}

pretty :: PPM -> String
pretty (PPM width height maxVal pixels)
= "P3 " ++ unwords [show width, show height] ++ "\n" ++
unlines (show maxVal : prettyPixels pixels)
where
prettyPixels :: [Pixel] -> [String]
prettyPixels = map prettyPixel
prettyPixel :: Pixel -> String
prettyPixel (r,g,b) = unwords $ map show [r,g,b]

{- parsing PPM files -}

parser :: String -> IO (Either ParseError PPM)
parser = parseFromFile parsePPM

parsePPM :: Parser PPM
parsePPM = do
string "P3"
junk
width <- parseInt
junk
height <- parseInt
junk
maxVal <- parseInt
junk
pixels <- many parseTriplet
return $ PPM width height maxVal pixels

comment :: Parser ()
comment = do
char '#'
manyTill anyChar newline
spaces

junk :: Parser ()
junk = do
spaces
optional comment

parseTriplet :: Parser (Int, Int, Int)
parseTriplet = do
red <- parseInt
spaces
green <- parseInt
spaces
blue <- parseInt
spaces
return (red, green, blue)

parseInt :: Parser Int
parseInt = do
ds <- many1 digit
return $ read ds

my Proj.hs

This is our project for 433-152: Algorithmic Problem Solving. Had finished the 8 functions a few days before, but found that the pictures my program generated were different from the example files provided using the Unix tool 'diff'. Then I spent about 8 hours fixing and debugging. This was really painful! I struggled for two hours just with the order of base case for 'enlarge'! I should have put it before the main body of the function but didn't realize that! WTF!! Okay, I'll cut my crap, it's the project main file Proj.hs. I'll put the library file on here using another blog entry. Take a look at it if you're interested in Haskell or image processing!


-- Proj.hs
-- Your file for 433-152 Project 2007
-- Stub code by Bernard Pope and Anthony Wirth

module Proj where

import PPMlib
import Data.Map hiding (map)

type Coord = (Int, Int)

noVerify :: PPM -> Maybe String
noVerify _ = Nothing

verify :: PPM -> Maybe String
verify (PPM w h m pixel) =
-- if there's at least one wrong pixel, return error msg otherwise return Nothing
if (and (map (verify' w h m) pixel) == False) then Just "Invalid PPM file" else Nothing
-- see whether the attributes of the picture are valid
where
verify' w h m (r, g, b)
| g > m || r > m || b > m = False
| g < 0 || r < 0 || b < 0 = False
| w < 0 || h < 0 || m < 0 = False
| otherwise = True


-- simple one!
greyScale :: PPM -> PPM
greyScale (PPM w h m pixel) =
PPM w h m (map change pixel)
where
change :: (Int, Int, Int) -> (Int, Int, Int)
change (r, g, b) = (grey, grey, grey)
where
-- grey = floor (0.3 * (fromIntegral (r::Int)) + 0.59 * (fromIntegral (g::Int)) + 0.11 * (fromIntegral (b::Int)))
grey = div (r + b + g) 3


-- mothod is like the one above.
negative :: PPM -> PPM
negative (PPM w h m pixel) =
PPM w h m (map (invert m) pixel)
where
invert :: Int -> (Int, Int, Int) -> (Int, Int, Int)
invert m (a, b, c) = (m - a, m - b, m - c)

-- Stupid way which I used at first!
-- inverter m ([]) = []
-- inverter m ((a, b, c) : rest) = (m - a, m - b, m - c) : (inverter m rest)


-- This seems perfectly right, but it never stops when run.
-- replicate and concat
-- replicate n : get a list of n duplicated items
-- concat : convert a list of tuples into a list with all the original iterms
-- (left, right) = splitAt halfway pixel. this is a really useful way, learnt from the lecture. A good way to split things up.
enlarge :: Int -> PPM -> PPM
enlarge n (PPM w h m pixel) =
PPM (w * n) (h * n) m (vertical w n (horizontal n pixel))
-- horizontally stretching
horizontal :: Int -> [(Int, Int, Int)] -> [(Int, Int, Int)]
horizontal n pixel = concat $ map (replicate n) pixel
-- vertically stretching
-- duplicate each row and append the handled rest to it
vertical :: Int -> Int -> [(Int, Int, Int)] -> [(Int, Int, Int)]
vertical w n [] = []
vertical w n pix = (concat $ replicate n row) ++ (vertical w n rest)
where
(row, rest) = splitAt (n * w) pix

--crap this is what I did at first, obviously it's wrong
--concat $ map (replicate n) pixel
--concat (map (replicate n) pixel)


-- I have an idea, but don't know how to write code for it.
-- I take the average value of the corresponding pixels and let it be the new pixel.
-- What I'm not sure is, what if w or h is not divisible by n? How to handle the remainder?
reduce :: Int -> PPM -> PPM
reduce _ _ = undefined


-- reconstruct rows in the reverse order, pretty simple.
reflectRow :: PPM -> PPM
reflectRow (PPM w h m pixel) =
PPM w h m (reflect w pixel)
reflect :: Int -> [a] -> [a]
-- base case
reflect w [] = []
-- append rows from the bottom to the top
reflect w pixel = (reflect w right) ++ left
where
(left, right) = splitAt w pixel


-- reverse all the pixels in each row and then append all the rows together!
reflectCol :: PPM -> PPM
reflectCol (PPM w h m pixel) =
PPM w h m (revcol w pixel)
revcol :: Int -> [a] -> [a]
revcol w [] = []
-- reverse and append
revcol w pixel = (reverse left) ++ (revcol w right)
where
(left, right) = splitAt w pixel

-- Really don't know how to do it
rotate :: Float -> Coord -> PPM -> PPM
rotate _ _ _ = undefined


-- a pretty easy one, used the function min
threshold :: Int -> PPM -> PPM
threshold t (PPM w h m pixel) =
PPM w h m (map change pixel)
where
change :: (Int, Int, Int) -> (Int, Int, Int)
change (a, b, c) = ((min t a), (min t b), (min t c))


-- First take out extra columns and then rows
crop :: Coord -> Coord -> PPM -> PPM
crop (a, b) (c, d) (PPM w h m pixel) =
PPM (d - b + 1) (c - a + 1) m (croprow h a c (d - b + 1) (cropcol w b d pixel))
-- eliminate columns that we don't need
cropcol w b d [] = []
cropcol w b d pix = image ++ (cropcol w b d rest)
where
-- get each row
(row, rest) = splitAt w pix
-- for each row, take out unwanted part to the left of the selected area
(junk1, rowrest) = splitAt b pix
-- for each row, take out the part to the right of the wanted image part
(image, junk2) = splitAt (d - b + 1) rowrest
--take out extra rows
croprow h a c w' [] = []
croprow h a c w' pix = image
where
-- extra rows above the selected image
(upperjunk, rest) = splitAt (a * w') pix
-- rows delow the wanted part of image
(image, lowerjunk) = splitAt (w' * (c - a + 1)) rest


translate :: Coord -> PPM -> PPM
translate (a, b) (PPM w h m pixel) =
PPM w h m (transrow w h a (transcol w b pixel))
-- move the left edge of the picture to the correct column.
transcol :: Int -> Int -> [(Int, Int, Int)] -> [(Int, Int, Int)]
transcol w b [] = []
transcol w b pix = case b >= 0 of
True -> black b ++ left ++ transcol w b rest
False -> rightn ++ black (-b) ++ transcol w b rest
where
(row, rest) = splitAt w pix
(left, right) = splitAt (w - b) row
(leftn, rightn) = splitAt (-b) row
-- move the top edge to the correct row.
transrow :: Int -> Int -> Int -> [(Int, Int, Int)] -> [(Int, Int, Int)]
transrow w h a [] = []
transrow w h a pix = case a >= 0 of
True -> black (a * w) ++ image
False -> uimage ++ black ((-a) * w)
where
(image, rest) = splitAt ((h - a) * w) pix
(urest, uimage) = splitAt ((-a) * w) pix
-- make black pixels
black :: Int -> [(Int, Int, Int)]
black 0 = []
black n = (0, 0, 0) : black (n - 1)


-- don't have enough time to do it.
normalize :: PPM -> PPM
normalize _ = undefined

Plato's View that Philosophers Should Rule

The famous philosopher Plato holds that the world should be ruled by true philosophers. This idea involves a great deal of wisdom and have been studied by many philosophers. It will be discussed in this essay.

Plato not only has the opinion that philosophers should rule, but also has developed a whole theory to support this. According to Plato's masterpiece the Republic, there are three distinctions between philosophers and non-philosophers and these are important factors which to some extent, determine philosophers' absolute ruler position. Firstly, unlike most lovers of beautiful things, philosophers in addition love beauty itself, which is the Form introduced by Plato. Secondly, philosophers live in the real world, non-philosophers in their dream world. Lastly, philosophers are people who have true knowledge,, but counterfeit philosophers only have beliefs or opinions. Plato further conceives a model containing images of the Sun, the Line and the Cave to strengthen his theory. To elaborate, this model mainly illustrates the relation and difference between knowledge and ignorance, dream and reality.

As for Plato's viewpoint of distinctions between philosophers and non-philosophers, I argue that this is enough to note that philosophers should rule and they can run the world in the most balanced state. This is not purely because philosophers have knowledge, which others don't, but also because there are no better alternatives for them. Cross (1964) says that the difference between true philosophers and their rivals is that true philosophers know reality of which many counterfeit philosophers' 'reality' is appearance. This means true philosophers grasp the eternal and internal knowledge of things and this knowledge acts in real world as theorems and axioms do in mathematics. They are the rules that determine how everything in the world works. So a philosopher's mind is like an abstraction of non-philosopher's thoughts. But this kind of abstraction or high level of understanding is somewhat away from practice. They can't adjust their knowledge with times, so there exists a distance between their knowledge and the real world (Pappas, 1995). However, as is known to all, what play the fundamental role in the world are the natures of things and only philosophers can reach them. So despite their limitation of practical knowledge, philosophers are still more qualified to rule than any other people because they are fundamentally correct.

Plato's model of the Sun, the Line and the Cave also indicates that philosophers have the utmost intelligence and should rule the world. Because it basically shows different levels of the world – the visible and the intelligible. Cross (1964) perceives the model that those who stand at the top know the Form of the Good – the Sun, knowledge – the top of the Line, and truth – one who receives education and has broken out of the Cave. This model also to some degree, proves the point that philosophers being the rulers mainly because there are no better alternatives for them – they are on the top, despite the fact that this point of view might be slightly different from Plato's original meaning of philosophers being the rules.

All in all, although there might arise many explanations, there's an agreement that philosophers have the highest level of knowledge and should rule the world in order to achieve the most balanced state of the world.


References

Bobonich . C, “Why Should Philosophers Rule? Plato's Republic and Aristotle's Protrepticus”, Philosophy, Stanford University, Available at:
http://journals.cambridge.org/action/displayAbstract;jsessionid=11DEBBE7A2E0E52611522068E4C2DA0E.tomcat1?fromPage=online&aid=1031904

Cross. R. C, Plato's Republic – A Philosophical commentary, London, New York St Martin's Press, 1964.

Pappas Nickolas, Plato and the Republic, from the Republic of Plato translated by Allan Bloom, 1995.

Plato, The republic, edited by G.R.F. Ferrari ; translated by Tom Griffith, Published by New York. Cambridge University Press, 2000.

last sem's essay

Didn't do it very well, but yeh, at last I handed in a full draft. If you wanna reference, PLEASE CITE THE SOURCE.

Chinese Post World War II Immmigration



INTRODUCTION

After World War II, the reconstruction effort and low birthrate in Australia called for more immigrants. Although encouraging immigration under the White Australian Policy resulted in dramatic increase of overseas-born population according to a report from DIMIA (2003), during which Chinese people were looked down, it was not satisfactory enough. In this phase the need for a more diverse population was increasing. It was not until 1973 that the White Australian Policy was abolished (DIMIA, 2003) and it was not long before the policy of multiculturalism was introduced in 1978, after which Chinese migration started to fluctuate and made contributions to the society. This paper will discuss issues in the period before the policy of multiculturalism was introduced as well as the period after that. Firstly, it will focus on society's attitudes towards Chinese immigrants in terms of their social cultural and economic impact on the country. Secondly, governments' policies towards immigrants will be talked about.



AUSTRALIANS' ATTITUDES TOWARDS CHINESE

Chinese immigrants as well as other non-white immigrants were looked down and were not encouraged to come to Australia in the period immediately after World War II. This was because of the Immigration Restriction Act, which was introduced in 1901 and mainly aimed against Chinese (Chan, 2000). This kind of viewpoint didn't fade away even after World War II. Although Chinese were not treated as bad as they were in the gold rush period, they were still viewed as an inferior group. London (1970) argues that Chinese were perceived as a threat to Australia's cultural heritage and development because of their generally lower standard of living as a threat to labour employer relations. Goot (1978) also points out that the antipathy to Chinese migrants was generated by some considerations, like concerns about the costs of immigration and the competition for jobs. This kind of attitude could be perceived from Queensland Parliament's revoke of a legislation under which any house where Asian women lived could be viewed as a house of prostitution in 1966 (London, 1970). This was really a down point after World War II. However, some positive attitudes existed despite the fact that the overall attitude was negative. London (1970) has the opinion that Chinese later were gradually accepted by the cities’ resident in Melbourne and Sydney and Australians’ sympathetic support of China accelerated the assimilation process. This was the trend of the shift of Australians’ attitudes towards Chinese in that time period as well as the Integration period.

According to a review report from DIMIA (2003) – Report of the Review of Settlement Services for Migrants and Humanitarian Engrant, the situation didn’t change much until the introduction of multiculturalism by Galbally report in 1978. The result of assimilation and integration was not satisfactory in spite of the fact that Australia had paid a considerable amount of effort to policy making to encourage immigration in order to increase the country’s population. The multiculturalism policy gave rise to a large-scale Chinese migration. As a result, Australia had a very high Chinese migration intake over the past two decades. Those Chinese immigrants not only made a culturally and linguistically diverse population together with other groups of immigrants (DIMIA, 2003), but also contributed to Australian society, which changed Australians' attitudes towards Chinese people dramatically. Their contributions mainly fell into three categories – social, cultural and economic aspects.

From a social perspective, Chinese immigration during this time period really gave Australia a new look. In the first place, the large number of arrivals changed the make-up of the population dramatically. The number of Chinese immigrants was over 92,000, ranking second among all the Asian counties in 1995 (Millbank, 2001). Millbank (2001) also states that in this time period – 1995 to 1996, recent surge from mainland China and Hong Kong resulted in the fact that Northeast Asian settlers outnumbered Southeast Asian settlers, which reflected the current trend of Chinese migration into Australia. This was important because immigrants' average ages were below the Australian average, which could to some extent solve the aging problem of Australian population. In the second place, the large-scale immigration also resulted in more investment that government put on education, and made the quality of education higher, especially for language training. Immigrants came from different counties, so English was a second language for most of them. Hence paying attention to language training was essential and beneficial because this cleared the main obstacles and hurdles for immigrants to contribute to the society. Last but not least, according to APMRN (2004), the large-scale Chinese migration as well as immigration of other groups made the government have laws against racial discrimination and incitement and have special agencies to enforce them. This is, to some extent, an advance of the discrimination of racism.

China is famous for its mysterious 5000-year history and the culture developed during the long time period, so under the light of the multiculturalism policy Chinese people brought their culture to Australia, which had great effects on the society. Firstly, Chinese migrants brought various Chinese food and products into Australia, which gave Australians more choices on food and a chance to experience this special culture around the world. There were Chinatowns in major cities in Australia, hence many Australians who were keen on Chinese food or history could go to Chinatown for lunch or dinner with their families, which would be very fantastic. Secondly, some Chinese festivals and customs were taken into practice in many places in Australia. For instance, many Australians ate dumplings on New Year's Day in Australia. In addition, plenty of Australians had the preference for Chinese tea culture; they drank tea and talked about tea with friends in leisure time and enjoyed it pretty much. Thirdly, Chinese culture contributed to the ever-increasingly cultural diversity greatly because of the large intake of Chinese immigrants during this period..

Chinese immigration over the past twenty years benefited Australia’s economy a great deal. It mainly affected Australia’s economy in two ways, the demand side and the supply side (DIEA Fact Sheet30, 1995). DIEA fact sheet 30 (1995) also states that in terms of the demand side, the first factor is migrants own demands. Their needs for food, housing and leisure activities stimulated factories and companies to invest more money and to produce more products, the economy benefited from this to some extent. More arrivals meant that more heath, education and welfare services were needed, hence these aspects advanced due to the immigration. With regard to the supply side, the most direct benefit Chinese immigrants brought to Australia was workforce, skills and money. Workforce shortage could, to some extent, be solved through immigration of younger people. Skeldon (2004) points out that the majority of Chinese migrants today are highly educated or have specialized skills selected through a special “points” system, so immigrants with high business skills also contributed much to the economy. In addition, new business can be introduced into Australia. Chinese immigrants contributed a great deal in this aspect because China was quite different from western countries in terms of dressing, eating habits and so on. So some Chinese food such as noodles and tea, and Chinese featured clothes were introduced into Australia and the demands for these kinds of products definitely helped the development of the economy. From another perspective, this also added productive diversity through knowledge of international business markets. (DIEA Fact Sheet 30, 1995).



GOVERNMENT'S POLICIES FOR CHINESE AND OTHER IMMIGRANTS

Australian government made a series of policies on migration throughout the post World War II period according to the times. It fell into two phases. The first phase was the period before multiculturalism, the second - the period after that. As mentioned at the beginning of this paper, immigration immediately after the war followed the Immigration Restriction Act introduced in 1901, which was widely known as White Australian Policy. The government then realized that only European immigrants were not enough - Australia still in a desperate need for a large population. Also a review report from DIMIA (2003) says that the Commonwealth Government established DIMIA in order to assist migration into Australia due to the concerns regarding Australia’s low birthrate and strong need for industrial labour. Hence the government put forward the assimilation policy, after which many non-British migrants came to Australia. The scale of Chinese migration in this period wasn't large because Australians still perferred Europeans instead of Asians. Although Australia witnessed a higher intake of migrants, the assimilation policy was limited. So the government shifted from the policy of assimilation to a policy of integration. And during this period, due to the removal of discrimination from within the immigration program, the White Australian Policy was abolished in 1973 and equal treatment for immigrants from different origin became an official standard (DIMIA, 2003). As a result of the process of this removal of discrimination, the shift towards multiculturalism on a policy level was finally seen in 1978, which according to Elliot (1984) was also because of an economic factor. Elliot points out that Australia had to develop and maintain trading relations with some neighbour countries. If Australia’s immigration policy was discriminatory against migrants from those countries, it would definitely not only have a negative effect on Australian economy, but also would have some more serious problems.

After the introduction of multiculturalism – the start of the second phase, the country went through a dramatic change, and the government paid a great deal of effort to policy making to benefit from and also to support these changes. Firstly, the definition of multiculturalism was being completed and changed according to the contemporary situation. Three principles were adopted 1989 – cultural identity, social justice and economic efficiency (DIMA, 1999). Secondly, DIMA (1999) also says that in 1986, Jupp argued that successful settlement by non-English speaking migrants needed not only the effort of the migrants, but also the services provided by the host society. The government thus had access and equity policy to help immigrants to adjust to the diverse society more easily and more quickly. This policy, according to Jupp's report in 1986, included two main aspects. The first one was to equip overseas-born families and idividuals the basic resources to enable them to function effectively on an equitable level in Australian society. The second was on an institutional level – let institutions which made decisions about making services and providing them implement them on an equitable basis. This kind of policy have been playing an important role in Chinese immigration, or we wouldn't see so many things reflecting Chinese culture around us here in Australia. Thirdly, the Australian government noticed that it should enourage more skilled and educated people to come to Australia to contribute to the society. So the Australian government put forward a series of laws to help highly skilled individuals and successful businessmen to have permanent residence in Australia. According to the fact sheet Assisting Skilled and Business people (DIC), applicants are classified into several categories, skilled independent, state/territory nominated independent, skilled – Australian sponsored, etc. Obviously, the Australian Government paid a considerable amount of attention to absorbing high-tech people to boost Australian economy. Last but never least, the Australian government also set up a policy a to meet the Chinese increasing interest in visiting Australia. Fact Sheet 58 (DIMIA) states that as Australia was the first western country approved by Chinese government a destination for tourists, Australia has paid some effort to make it easier. Although this is not about migration, some tourists could be would-be immigrants because of the beauty and power of Australia. So this could encourage Chinese people to migrate to Australa to some extent.



CONCLUSION

Whilst Chinese immigrants didn't have a good reputation at the beginning of the second World War, they have been doing their best to get adjusted to the society and their contributions to the society in many aspects really made a difference. It's very pleased to see that Chinese people were gradually accepted by the Australian society and the Australian government has been trying to incease the diversity and scale of the population – going on with the multicultural policy.

Having considered the fact that Australia is still short of industrial labour and workforce, it's believed that government will have more policies on immigration to support highly skilled and educated people to come to Australia, and more corresponding policies that can solve problems caused by the immigration. And it's also believed that Chinese people will play a more important role in Australia and make as many contributions as they can to the society to meet the government's original intention.



REFERENCES

DIEA, Fact Sheet 30, 1995.

Asia Pacific Migration Research Network (APMRN), Migration Issues in the Asia Pacific, ISSUES PAPER FROM AUSTRALIA, [online] Available:
http://www.unesco.org/most/apmrnwp5.htm

Assisting Skilled and Business People, (Fact Sheet) Department of Immigration and Citizenship, Australian Government, [online] Available:
http://www.immi.gov.au/media/fact-sheets/48assisting.htm

China - Approved Destination Status, (Fact Sheet) Department of Immigration and Citizenship, Australian Government, [online] Available:
http://www.immi.gov.au/media/fact-sheets/58china.htm

Chan, H. (2000) From Quong Tarts to Victor Changes: Being Chinese In Australia in the Twentieth Century. CSCSD Public Seminar at the Australian National University. 24 May 2000.

DIMA, New Agenda for Multicultural Australia,
DIMA, Canberra, 1999, p. 8.

DIMIA, Report of the Review of Settlement Services for Migrants and Humanitarian Entrants, May 2003.

Elliot, J. D. (1984). Immigration: The economic benefits. In F. Milne & P. Shergold (Eds.), The great immigration debate. Sydney: Federation of Ethnic Communities in Australia.

Goot. M, Immigrations and Immigration: Evidence and Argument From the Public, 1943 – 1987, Macquarie University.

London. H. I., 1970, Non-White Immigration and the “White Australian” Policy.

Millbank, A, Asian Immigration, Current Issues Brief 16 1996-97, Social Policy Group, [online] Available:
http://www.aph.gov.au/library/pubs/cib/1996-97/97cib16.htm

Skeldon, R, 2004 China: From Exceptional Place to Global Participant. [online], Available:
http://www.migrationinformation.org/Feature/display.cfm?D=9 – 41k

reminder

Always remember the expression in terms of exponentials and the identity equations when dealing with trigonometric and hyperbolic functions!

The hyperbolic identity equation:
Coshx squre minus sinhx squre equals 1.

Coshx = 1/2 times the sum of e to the x and e to the negative x.
Sinhx = 1/2 times the result of e to the x minus e to the negative x.

The trigonometric identity equation:
Cosx squre plus sinx squre is equal to 1.

Sinx = 1/2 times the result of e to the power of ix take away e to the power of -ix.
Cosx = minus i/2 times the sum of e to the ix and e to the -ix.

I won't forget them hopefully.

look-ahead carry

When we use parallel adders to do addition operations, the main problem would be that the propagation delay could become quite long when the number of bits is increasing. This is mainly because the result in the current position depends on the carry which has been calculated in the previous position. Although modern super deluxe CPUs seem really powerful when doing a simple addition, we gotta keep in mind that small delays would reault in astronomically big delays when doing complex calculations especially in electronics and computer science.

Fortunately engineers came up with the idea of look-ahead carry, which uses a certain combinational circuit to calculate all the carries within a constant time and then does the addition for each bit synchronously. Each carry could be represented in terms of the inputs of the least significant bit, so each carry could have a similar expression and these expresstions only need a two-level AND-OR gates to be implemented. Hence the time to be consumed to calculate all the carries will become the time which does the two-level basic AND-OR operations instead of taking a multiple full adder calculation time. As a result, the total time consumed has been reduced from a linearly increasing number to a constant number, which has increased the calculation speed dramatically.

This is what I learned from the subject digital systems, especially after I've done question 1 in assignment 8. The reason why I wanted to spend 15 minutes on writing this is that I have gained some wisdom from the idea of look-ahead carry. We know that the carry is calculated by the full adder for each bit, but the time to be used for a whole addition operation depends on the number of bits to be handled. If engineers had spent plenty of time only on how to modify the full adder to reduce the whole propagation deley, they wouldn't have got look-ahead carry. So we should try not to stick to the object which we are supposed to put emphasis on when tackling a certain problem. I reckon this is also the essence of brainstorming to some extent.

The project thing

This post is mainly for the project discussion. Welcome to put forward your opnions and questions here, buddies! Maybe someone passes by can help you hit the jackpot!

Ken, I reckon we'd better take a closer look at task one to three and try to get the preliminary stuff done by ourselves. Personally, I don't think this project is suitable for group work. However, we don't need to do that much if we split tasks properly.

As for further task allocation (I'm not refering to the ones in the assignment requirement sheet but the actual coding work), you can post it here or send me an email.

Best luck to us all with the stupid project.

[quote] Larger 5 & 6-variable Karnaugh maps

Larger Karnaugh maps reduce larger logic designs. How large is large enough? That depends on the number of inputs, fan-ins, to the logic circuit under consideration. One of the large programmable logic companies has an answer.

Altera's own data, extracted from its library of customer designs, supports the value of heterogeneity. By examining logic cones, mapping them onto LUT-based nodes and sorting them by the number of inputs that would be best at each node, Altera found that the distribution of fan-ins was nearly flat between two and six inputs, with a nice peak at five.

The answer is no more than six inputs for most all designs, and five inputs for the average logic design. The five variable Karnaugh map follows.

The older version of the five variable K-map, a Gray Code map or reflection map, is shown above. The top (and side for a 6-variable map) of the map is numbered in full Gray code. The Gray code reflects about the middle of the code. This style map is found in older texts. The newer preferred style is below.

The overlay version of the Karnaugh map, shown above, is simply two (four for a 6-variable map) identical maps except for the most significant bit of the 3-bit address across the top. If we look at the top of the map, we will see that the numbering is different from the previous Gray code map. If we ignore the most significant digit of the 3-digit numbers, the sequence 00, 01, 11, 10 is at the heading of both sub maps of the overlay map. The sequence of eight 3-digit numbers is not Gray code. Though the sequence of four of the least significant two bits is.

Let's put our 5-variable Karnaugh Map to use. Design a circuit which has a 5-bit binary input (A, B, C, D, E), with A being the MSB (Most Significant Bit). It must produce an output logic High for any prime number detected in the input data.

We show the solution above on the older Gray code (reflection) map for reference. The prime numbers are (1,2,3,5,7,11,13,17,19,23,29,31). Plot a 1 in each corresponding cell. Then, proceed with grouping of the cells. Finish by writing the simplified result. Note that 4-cell group A'B'E consists of two pairs of cell on both sides of the mirror line. The same is true of the 2-cell group AB'DE. It is a group of 2-cells by being reflected about the mirror line. When using this version of the K-map look for mirror images in the other half of the map.

Out = A'B'E + B'C'E + A'C'DE + A'CD'E + ABCE + AB'DE + A'B'C'D

Below we show the more common version of the 5-variable map, the overlay map.

If we compare the patterns in the two maps, some of the cells in the right half of the map are moved around since the addressing across the top of the map is different. We also need to take a different approach at spotting commonality between the two halves of the map. Overlay one half of the map atop the other half. Any overlap from the top map to the lower map is a potential group. The figure below shows that group AB'DE is composed of two stacked cells. Group A'B'E consists of two stacked pairs of cells.

For the A'B'E group of 4-cells ABCDE = 00xx1 for the group. That is A,B,E are the same 001 respectively for the group. And, CD=xx that is it varies, no commonality in CD=xx for the group of 4-cells. Since ABCDE = 00xx1, the group of 4-cells is covered by A'B'XXE = A'B'E.

The above 5-variable overlay map is shown stacked.

An example of a six variable Karnaugh map follows. We have mentally stacked the four sub maps to see the group of 4-cells corresponding to Out = C'F'

A magnitude comparator (used to illustrate a 6-variable K-map) compares two binary numbers, indicating if they are equal, greater than, or less than each other on three respective outputs. A three bit magnitude comparator has two inputs A₂A₁A₀ and B₂B₁B₀ An integrated circuit magnitude comparator (7485) would actually have four inputs, But, the Karnaugh map below needs to be kept to a reasonable size. We will only solve for the A>B output.

Below, a 6-variable Karnaugh map aids simplification of the logic for a 3-bit magnitude comparator. This is an overlay type of map. The binary address code across the top and down the left side of the map is not a full 3-bit Gray code. Though the 2-bit address codes of the four sub maps is Gray code. Find redundant expressions by stacking the four sub maps atop one another (shown above). There could be cells common to all four maps, though not in the example below. It does have cells common to pairs of sub maps.

The A>B output above is ABC>XYZ on the map below.

Where ever ABC is greater than XYZ, a 1 is plotted. In the first line ABC=000 cannot be greater than any of the values of XYZ. No 1s in this line. In the second line, ABC=001, only the first cell ABCXYZ= 001000 is ABC greater than XYZ. A single 1 is entered in the first cell of the second line. The fourth line, ABC=010, has a pair of 1s. The third line, ABC=011 has three 1s. Thus, the map is filled with 1s in any cells where ABC is greater than XXZ.

In grouping cells, form groups with adjacent sub maps if possible. All but one group of 16-cells involves cells from pairs of the sub maps. Look for the following groups:

• 1 group of 16-cells
• 2 groups of 8-cells
• 4 groups of 4-cells

The group of 16-cells, AX' occupies all of the lower right sub map; though, we don't circle it on the figure above.

One group of 8-cells is composed of a group of 4-cells in the upper sub map overlaying a similar group in the lower left map. The second group of 8-cells is composed of a similar group of 4-cells in the right sub map overlaying the same group of 4-cells in the lower left map.

The four groups of 4-cells are shown on the Karnaugh map above with the associated product terms. Along with the product terms for the two groups of 8-cells and the group of 16-cells, the final Sum-Of-Products reduction is shown, all seven terms. Counting the 1s in the map, there is a total of 16+6+6=28 ones. Before the K-map logic reduction there would have been 28 product terms in our SOP output, each with 6-inputs. The Karnaugh map yielded seven product terms of four or less inputs. This is really what Karnaugh maps are all about!

The wiring diagram is not shown. However, here is the parts list for the 3-bit magnitude comparator for ABC>XYZ using 4 TTL logic family parts:

• 1 ea 7410 triple 3-input NAND gate AX', ABY', BX'Y'
• 2 ea 7420 dual 4-input NAND gate ABCZ', ACY'Z', BCX'Z', CX'Y'Z'
• 1 ea 7430 8-input NAND gate for output of 7-P-terms

• REVIEW:
• Boolean algebra, Karnaugh maps, and CAD (Computer Aided Design) are methods of logic simplification. The goal of logic simplification is a minimal cost solution.
• A minimal cost solution is a valid logic reduction with the minimum number of gates with the minimum number of inputs.
• Venn diagrams allow us to visualize Boolean expressions, easing the transition to Karnaugh maps.
• Karnaugh map cells are organized in Gray code order so that we may visualize redundancy in Boolean expressions which results in simplification.
• The more common Sum-Of-Products (Sum of Minters) expressions are implemented as AND gates (products) feeding a single OR gate (sum).
• Sum-Of-Products expressions (AND-OR logic) are equivalent to a NAND-NAND implementation. All AND gates and OR gates are replaced by NAND gates.
• Less often used, Product-Of-Sums expressions are implemented as OR gates (sums) feeding into a single AND gate (product). Product-Of-Sums expressions are based on the 0s, maxterms, in a Karnaugh map.

[quote] Vinyl records versus CDs and DVDs

The answer lies in the difference between analog and digital recordings. A vinyl record is an analog recording, and CDs and DVDs are digital recordings. Take a look at the graph below. Original sound is analog by definition. A digital recording takes snapshots of the analog signal at a certain rate (for CDs it is 44,100 times per second) and measures each snapshot with a certain accuracy (for CDs it is 16-bit, which means the value must be one of 65,536 possible values).

Comparison of a raw analog audio signal to the CD audio and DVD audio output

This means that, by definition, a digital recording is not capturing the complete sound wave. It is approximating it with a series of steps. Some sounds that have very quick transitions, such as a drum beat or a trumpet's tone, will be distorted because they change too quickly for the sample rate.

In your home stereo the CD or DVD player takes this digital recording and converts it to an analog signal, which is fed to your amplifier. The amplifier then raises the voltage of the signal to a level powerful enough to drive your speaker.

A vinyl record has a groove carved into it that mirrors the original sound's waveform. This means that no information is lost. The output of a record player is analog. It can be fed directly to your amplifier with no conversion.

This means that the waveforms from a vinyl recording can be much more accurate, and that can be heard in the richness of the sound. But there is a downside, any specks of dust or damage to the disc can be heard as noise or static. During quiet spots in songs this noise may be heard over the music. Digital recordings don't degrade over time, and if the digital recording contains silence, then there will be no noise.

From the graph above you can see that CD quality audio does not do a very good job of replicating the original signal. The main ways to improve the quality of a digital recording are to increase the sampling rate and to increase the accuracy of the sampling.

The recording industry has a new standard for DVD audio discs that will greatly improve the sound quality. The table below lists the sampling rate and the accuracy for CD recordings, and the maximum sampling rate and accuracy for DVD recordings. DVDs can hold 74 minutes of music at their highest quality level. CDs can also hold 74 minutes of music. By lowering either the sampling rate or the accuracy, DVDs can hold more music. For instance a DVD can hold almost 7 hours of CD quality audio.

	CD Audio	DVD Audio
Sampling Rate	44.1 kHz	192 kHz
Samples per second	44,100	192,000
Sampling Accuracy	16-bit	24-bit
Number of Possible Output Levels	65,536	16,777,216

DVD audio discs and players are rare right now, but they will become more common, and the difference in sound quality should be noticeable. To take advantage of higher quality DVD audio discs, however, you will need a DVD player with a 192kHz/24-bit digital to analog converter. Most DVD players only have a 96kHz/24-bit digital to analog converter. So if you are planning to take full advantage of DVD audio be sure to look for a 192kHz/24-bit DAC.

Quoted from Howstuffworks

转: VIM简单用法

感觉有点用处故转贴在此。 文章较乱，略为整理以便阅读。

用VIM编写C/C++程序Vi是Unix下最常用的文本编辑器。VIM（Vi IMproved）则是它的增强版。有人常常拿VIM和emacs比较，VIM尽管不象emacs那样有那么多的功能，但是比emacs更方便、好用。用过emacs的人肯定会为emacs的一些快捷键感到烦恼，有时候用真希望自己有八只手。VIM的学习曲线也不象emacs那么长，只要看看VIM自带的vitutor，大约只要20分钟就能掌握VIM的用法。对于Unix下的C/C++的程序员，我推荐你们使用VIM+Ctags的组合来写程序。其中原因听我慢慢道来。（下面对VIM的介绍主要是针对5.6以后的版本）


一、VIM支持语法制导和自动缩进

VIM会根据文件的后缀名，如：*.c、*.cpp、*.cc，等，自动设置语法制导（Syntax Highlighting）。C/C++中的一些保留字，如：if、for、include，等等，就会有不同的颜色，这样就会减少程序员犯错的可能，阅读程序的时候相对来说也轻松很多。用下面这些命令在VIM中查看有关语法制导的帮助：“:h syntax”、“:h syn-qstart”、“:h syntax-printing”。VIM也支持根据GNU的风格自动缩进，这样程序员编写出来的代码就更易阅读，而且也有利于培养好的编程风格。用下面这些命令在VIM中查看有关自动缩进的帮助：“:h cindent”、“:h cinoptions”、“:h cinoptions-values”、“:h cinkeys”、“:h cinwords”。


二、使用Ctags

VIM中已经带了Ctags这个程序。尽管ctags也可以支持其它编辑器，但是它正式支持的只有VIM。Ctags可以帮助程序员很容易地浏览源代码。用下面的命令可以在源代码的根目录下创建“tags”文件：[/home/brimmer/src]$ ctags -R“-R”表示递归创建，也就包括源代码根目录下的所有子目录下的源程序。“tags”文件中包括这些对象的列表：
l 用#define定义的宏
l 枚举型变量的值
l 函数的定义、原型和声明
l 名字空间（namespace）
l 类型定义（typedefs）
l 变量（包括定义和声明）
l 类（class）、结构（struct）、枚举类型（enum）和联合（union）
l 类、结构和联合中成员变量或函数

VIM用这个“tags”文件来定位上面这些做了标记的对象，下面介绍一下定位这些对象的方法：

1) 用命令行。在运行vim的时候加上“-t”参数，例如：[/home/brimmer/src]$ vim -t foo_bar这个命令将打开定义“foo_bar”（变量或函数或其它）的文件，并把光标定位到这一行。

2) 在vim编辑器内用“:ta”命令，例如：:ta foo_bar

3) 最方便的方法是把光标移到变量名或函数名上，然后按下“Ctrl-]”。用“Ctrl-o”退回原来的地方。
注意：运行vim的时候，必须在“tags”文件所在的目录下运行。否则，运行vim的时候还要用“:set tags=”命令设定“tags”文件的路径，这样vim才能找到“tags”文件。


三、快速改正错误在

VIM编辑器的环境下用“:make”就可以编译程序，当然其前提是在当前目录下有Makefile文件。运行完“:make”之后，如果程序中有错误，就会显示出来。这时候，光标会自动指向第一个出现错误的地方，而且你还可以看到错误的提示。然后，你就可以改正错误，而不用手工找到出错的那一行。记住下面几个有用的命令：
l “:cl”列出错误
l “:cn”让光标指向下一个错误
l “:cp”让光标指向上一个错误
l “:cnew”从头开始

你甚至可以让VIM识别出其它编译器而不是gcc的错误提示。这对一些开发嵌入式系统的程序员这很有用，因为他们很可能用的不是gcc而是其它编译器。通过设置“errorformat”的值，可以让VIM识别出编译器的出错提示。因为不同的编译器的出错提示是不同的，所以如果用的不是gcc就要重新设置。
“errorformat”的值是一个字符串，它的格式和C语言的scanf的字符串格式相识。
gcc的“errorformat”的值为：%f:%l:\%m。其中“%f”表示文件名，“%l”表示行号，“%m”表示出错信息。
用“:h errorformat”查看详细的帮助信息。
用“:h quickfix”、“:h make”、“:h makeprg”、“:h errorfile”查看其它的信息。


四、有用的快捷键

下面的这些快捷键对程序员很有帮助：

1）在函数中移动光标
[[ 转到上一个位于第一列的“{”
]] 转到下一个位于第一列的“{”
{ 转到上一个空行
} 转到下一个空行
gd 转到当前光标所指的局部变量的定义
* 转到当前光标所指的单词下一次出现的地方
# 转到当前光标所指的单词上一次出现的地方

2）括号的匹配
% 用来进行小括号、中括号和大括号的匹配。这要看当前光标指向的是什么符号了。


五、其它

VIM的配置文件是“.vimrc”，用这个文件可以配置VIM。VIM的图形界面的版本叫gvim。VIM也有用于Windows平台的版本。

VIM的资源
VIM的主页：http://www.vim.org/。

版权说明
这篇文章的版权属于作者brimmer（brimmer@linuxaid.com.cn）和http://www.linuxaid.com.cn/。如果要转载请加上版权提示。
Brimmer的主页：www.linuxaid.com.cn/engineer/brimmer。HTML格式和Word格式的文档可以在主页上找到。