diff --git a/writing/computational thinking/face/face.docx b/writing/computational thinking/face/face.docx new file mode 100644 index 0000000..aea71ea Binary files /dev/null and b/writing/computational thinking/face/face.docx differ diff --git a/writing/computational thinking/gametheory/gametheory - Copy.txt b/writing/computational thinking/gametheory/gametheory - Copy.txt new file mode 100644 index 0000000..fa22528 --- /dev/null +++ b/writing/computational thinking/gametheory/gametheory - Copy.txt @@ -0,0 +1,46 @@ +Game theory is the science that studies the optimal way to play games of strategy, such as chess, bridge, or tic-tac-toe [LINK TO OUR PREVIOUS COLUMN ON TICTACTOE]. Interestingly, many phenomena can be modeled as a game: social interactions, as we will show in this column, but also market strategies for corporations, political campaigns and even biological adaptation. Here is a simple example. + +Imagine two people meet at bar and order a beer each, whose price is 5 francs per glass. When it's time to pay, each person can either be honest and pay, or try to run away without paying. There are now four possibilities: when both people are honest, they pay 5 francs each and all is well. If one of them is honest and the other runs away, the dishonest person spends nothing and the honest person is stuck with a 10 franc bill. Finally, if both try to run away at the same time, they are obviously caught and each will have to pay for their drink plus a 2 franc fine, that is, 7 francs each. What is the best course of action that they can follow? + +Perhaps counter-intuitively it turns out that, if self-interest is the main goal, a person would always gain by trying to run away. The game-theoretical analysis of the situation is quite simple: if the other person is honest, staying will cost 5 francs but running will cost nothing; if the other person is dishonest, staying will cost 10 francs but running will only cost 7$. In both cases, running away is a less expensive option than honesty! + +The analysis however also shows that two mutually honest beer drinkers will always spend 5 francs each, while two equally dishonest ones will always spend more. So the "game" has two points of equilibrium and the course of action of the players will depend on their "default" strategy. In fact, human cooperation is not based on pure profit maximization but on more intangible principles such as trust, respect and the so-called "greater good," which is built on a long-term accountability of people's actions. + +Now, remember when you learned checkers or chess as a kid: you probably memorized the rules of the game very quickly but it took a long time and a lot of observation to interiorize the best way to actually play. The same is true as well for social interactions that can be modeled as a game; so, how do people learn the best strategy to play the "game of life"? Every day we observe the world, not just in the context of our experiences but also through the much larger lens of newspapers, newscasts and online news. One of the long-standing problems of journalism, however, is the almost exclusive focus on the bad side of things: "good news is no news," they say. While this is not a recent phenomenon, it is only recently that we are always "connected" to our sources of information, thanks to the internet and our mobile devices. Such steady exposure to negative news, even if it doesn't affect us personally, can trick our brain into believing that trust and cooperation are not that common; in other words, they can trick us into choosing the strategy where we expect dishonesty from others -- and end up paying more, metaphorically speaking. + +As game theory shows us precisely, with the wrong assumptions we can be a victim of our own rationality and end up stuck in an equilibrium point that is not optimal, neither for ourselves nor for society. The lesson, in the words of Monty Python: "always look on the bright side of life!" + + + +The first lesson that we can learn from this example is that, if people pursue their interest exclusively, we need steep fines to curb dishonest behavior. Suppose the penalty for trying to run without paying was 100 francs instead of 2. In this case adopting a dishonest behavior involves the risk of a huge cost, and dishonesty would no longer be the most advantageous strategy in all cases. + +But of course what we also learn is that in practice human cooperation is not based on pure profit maximization but on more intangible principles such as trust, respect and the so-called "greater good," which is built on a long-term accountability of people's actions. Reliable cooperation, as shown by the game-theoretical analysis above, has the greatest payoff: two honest beer drinkers will always spend 5 francs each, while two dishonest ones will always spend more. + +In the end, game theory shows us that in many social interactions there are two possible points of equilibrium + +The interesting thing about game theory is that it provides a precise mathematical description of the strategy behind a game; + +in general, +The greater lesson is that, if we can count on the honesty of others, the optimal strategy for life changes for the better. How can we + + + +The funny thing about games such as chess, checker, bridge and so on, is that it takes a very short time to learn the basic rules (children can do it very quickly). Good strategies, however, are usually absorbed via observation, trial and error and take a long time to develop. Interestingly, many of the interpersonal, political and economical interactions that define our society can be modeled as "games", where opponents try to maximize their gain at the expense of the other players. Companies compete for market shares by playing games of price adjustments, politicians compete for votes by playing with people's expectations, and so on. Game theory tries to describe these behaviors in terms of mathematical models in order to discover the best move for each player. + + +learning games as kids: learn rules, infer strategy + +strategy emerges naturally as a partly unconscious statistical expectation: N attempts are successful AND looking at other people play and basing expectations on their behavior + +game theory and applications + +is our society getting better or getting worse? + +prisoner's dilemma + + + +Although game theory helps us explain this and way more complex situations, people do not learn how to behave via an analytical study of payoff tables; conversely, we absorb the subtle rules of cooperation by constant exposure. Today, however, the greatest source of exposure for children and adults alike is the news streams that comes from TV and internet. Those are highly biased sources that focus mostly on bad news; as they say, "good news is no news". + +Maybe we do live in the best times that ever occurred and perhaps we should rely on game theory more and less on the ever-shorter and ever more depressing news cycle to realize that, in fact, the implicit strategy of this game of life that we're playing are + diff --git a/writing/computational thinking/gametheory/gametheory.docx b/writing/computational thinking/gametheory/gametheory.docx new file mode 100644 index 0000000..c21d72f Binary files /dev/null and b/writing/computational thinking/gametheory/gametheory.docx differ diff --git a/writing/computational thinking/gametheory/gametheory.txt b/writing/computational thinking/gametheory/gametheory.txt new file mode 100644 index 0000000..fa22528 --- /dev/null +++ b/writing/computational thinking/gametheory/gametheory.txt @@ -0,0 +1,46 @@ +Game theory is the science that studies the optimal way to play games of strategy, such as chess, bridge, or tic-tac-toe [LINK TO OUR PREVIOUS COLUMN ON TICTACTOE]. Interestingly, many phenomena can be modeled as a game: social interactions, as we will show in this column, but also market strategies for corporations, political campaigns and even biological adaptation. Here is a simple example. + +Imagine two people meet at bar and order a beer each, whose price is 5 francs per glass. When it's time to pay, each person can either be honest and pay, or try to run away without paying. There are now four possibilities: when both people are honest, they pay 5 francs each and all is well. If one of them is honest and the other runs away, the dishonest person spends nothing and the honest person is stuck with a 10 franc bill. Finally, if both try to run away at the same time, they are obviously caught and each will have to pay for their drink plus a 2 franc fine, that is, 7 francs each. What is the best course of action that they can follow? + +Perhaps counter-intuitively it turns out that, if self-interest is the main goal, a person would always gain by trying to run away. The game-theoretical analysis of the situation is quite simple: if the other person is honest, staying will cost 5 francs but running will cost nothing; if the other person is dishonest, staying will cost 10 francs but running will only cost 7$. In both cases, running away is a less expensive option than honesty! + +The analysis however also shows that two mutually honest beer drinkers will always spend 5 francs each, while two equally dishonest ones will always spend more. So the "game" has two points of equilibrium and the course of action of the players will depend on their "default" strategy. In fact, human cooperation is not based on pure profit maximization but on more intangible principles such as trust, respect and the so-called "greater good," which is built on a long-term accountability of people's actions. + +Now, remember when you learned checkers or chess as a kid: you probably memorized the rules of the game very quickly but it took a long time and a lot of observation to interiorize the best way to actually play. The same is true as well for social interactions that can be modeled as a game; so, how do people learn the best strategy to play the "game of life"? Every day we observe the world, not just in the context of our experiences but also through the much larger lens of newspapers, newscasts and online news. One of the long-standing problems of journalism, however, is the almost exclusive focus on the bad side of things: "good news is no news," they say. While this is not a recent phenomenon, it is only recently that we are always "connected" to our sources of information, thanks to the internet and our mobile devices. Such steady exposure to negative news, even if it doesn't affect us personally, can trick our brain into believing that trust and cooperation are not that common; in other words, they can trick us into choosing the strategy where we expect dishonesty from others -- and end up paying more, metaphorically speaking. + +As game theory shows us precisely, with the wrong assumptions we can be a victim of our own rationality and end up stuck in an equilibrium point that is not optimal, neither for ourselves nor for society. The lesson, in the words of Monty Python: "always look on the bright side of life!" + + + +The first lesson that we can learn from this example is that, if people pursue their interest exclusively, we need steep fines to curb dishonest behavior. Suppose the penalty for trying to run without paying was 100 francs instead of 2. In this case adopting a dishonest behavior involves the risk of a huge cost, and dishonesty would no longer be the most advantageous strategy in all cases. + +But of course what we also learn is that in practice human cooperation is not based on pure profit maximization but on more intangible principles such as trust, respect and the so-called "greater good," which is built on a long-term accountability of people's actions. Reliable cooperation, as shown by the game-theoretical analysis above, has the greatest payoff: two honest beer drinkers will always spend 5 francs each, while two dishonest ones will always spend more. + +In the end, game theory shows us that in many social interactions there are two possible points of equilibrium + +The interesting thing about game theory is that it provides a precise mathematical description of the strategy behind a game; + +in general, +The greater lesson is that, if we can count on the honesty of others, the optimal strategy for life changes for the better. How can we + + + +The funny thing about games such as chess, checker, bridge and so on, is that it takes a very short time to learn the basic rules (children can do it very quickly). Good strategies, however, are usually absorbed via observation, trial and error and take a long time to develop. Interestingly, many of the interpersonal, political and economical interactions that define our society can be modeled as "games", where opponents try to maximize their gain at the expense of the other players. Companies compete for market shares by playing games of price adjustments, politicians compete for votes by playing with people's expectations, and so on. Game theory tries to describe these behaviors in terms of mathematical models in order to discover the best move for each player. + + +learning games as kids: learn rules, infer strategy + +strategy emerges naturally as a partly unconscious statistical expectation: N attempts are successful AND looking at other people play and basing expectations on their behavior + +game theory and applications + +is our society getting better or getting worse? + +prisoner's dilemma + + + +Although game theory helps us explain this and way more complex situations, people do not learn how to behave via an analytical study of payoff tables; conversely, we absorb the subtle rules of cooperation by constant exposure. Today, however, the greatest source of exposure for children and adults alike is the news streams that comes from TV and internet. Those are highly biased sources that focus mostly on bad news; as they say, "good news is no news". + +Maybe we do live in the best times that ever occurred and perhaps we should rely on game theory more and less on the ever-shorter and ever more depressing news cycle to realize that, in fact, the implicit strategy of this game of life that we're playing are + diff --git a/writing/computational thinking/halting/halting.txt b/writing/computational thinking/halting/halting.txt new file mode 100644 index 0000000..b2e36c1 --- /dev/null +++ b/writing/computational thinking/halting/halting.txt @@ -0,0 +1,11 @@ +WHEN CAN SOMETHING BE COMPUTED? + +The other day I was in the middle of writing a long email when, out of the blue, my computer crashed and I lost all of my work. I know I don't need to tell you how frustrating this is, because everyone has experienced these kinds of software "bugs" at one point or another. And yet: given that information technology is so advanced, and that no day goes by without some newspaper headline declaring computers on a par with human intelligence, how is it possible that even simple programs like an email editor are still vulnerable to errors? Can't we write a smart "quality assurance" algorithm that checks whether a program is liable to crash? + +The question is much more important than the occasional inconvenience with my email software: consider a complex system such as an airplane guidance system. In these cases, a software error can have catastrophic consequences. Will we ever have the ultimate automatic checker for all of our software? Well, the answer is unfortunately no, as shown by Alan Turing in 1936 when he proved the so-called "Halting Problem". Turing was one of the founding fathers of computer science and one of the pioneering figures in computational thinking. + +The crux of Turing's argument exploits the circularity of what we are trying to do: writing software to analyze... software. We encounter these kinds of problems in everyday language as well; consider for instance the phrase "this sentence is false". This is a classic self-referential paradox: clearly, if the sentence is false, then the sentence is true -- and vice versa. Since the phrase is grammatically correct, there is no simple way out of the impasse other than admitting that, when sentences talk about themselves, sometimes meaningfulness is not assured. + +The same is true for computer programs, except that, in that case, the argument can be made very precise mathematically. In fact, if you claim to have written a checker program that can determine the correctness of any other program, Turing showed exactly how to build a program that will stump your checker. + +This proof of impossibility is primarily theoretical and, in practice, we can build quality-assurance programs that greatly help the work of software engineers. But the fundamental lesson is one of non-complacency: no matter how clever we are, we should remember that we can never be completely sure that a little bug hasn't crept in our ever-smarter computing machines! \ No newline at end of file diff --git a/writing/computational thinking/long/longitude.docx b/writing/computational thinking/long/longitude.docx new file mode 100644 index 0000000..1c02c65 Binary files /dev/null and b/writing/computational thinking/long/longitude.docx differ diff --git a/writing/computational thinking/pkc/pkc.txt b/writing/computational thinking/pkc/pkc.txt new file mode 100644 index 0000000..b093271 --- /dev/null +++ b/writing/computational thinking/pkc/pkc.txt @@ -0,0 +1,16 @@ +PUBLIC-KEY CRYPTOGRAPHY + +When I was a young student at Stanford, I had the privilege of attending a class by Martin Hellman, one of the inventors of public-key cryptography. At the time I wasn't fully aware of how important his work on cybersecurity was, but later I learned that when he was about to divulge his results, he had received death threats to discourage him from sharing his work with the world. + +To understand why, consider that the problem of secrecy is as old as mankind itself and the ability to safely exchange secret messages has always been regarded as a powerful military asset. From Roman times (Julius Caesar was said to have invented a secret cypher himself) to WWII (as popularized by a recent movie about Alan Turing and the Enigma machine), enemies have always tried to outsmart each other with ever more complex encryption schemes. All these classic methods, however, shared a fundamental weakness: they required that sender and receiver exchange a secret key beforehand. But how can you securely share this key if a physical handover is not possible or is too dangerous? And what if the key falls in enemy hands? + +All of this changed in the 70s with Hellman's public-key cryptography: now parties can communicate securely without the need of a shared secret key. To understand how this is possible, think of those keypad-operated safes that you find in many hotel rooms these days. I can set a 5-digit combination and, when I type the combination, the safe locks; I type it again, and the safe opens. Now imagine a slight modification: the safe now requires two distinct 5-digit codes; let's call the first the _private_ code (which I will reveal to no-one) and a _public_ code, which I will share freely with whole world, for instance on my business card. The modified safe works like so: if someone locks it using the public code, the safe can only be open by typing the secret code and, importantly, vice-versa. + +You can use this safe as a secure mailbox: you leave a message for me and lock it with the public code; now you know that only I can open it, since only I have the secret code. [PERHAPS CUT THIS - BUT IT'S NICE TO KNOW IMHO : ] Alternatively, I can use the safe to send an authenticated message to you: I put the message in the safe, lock it with the secret code and deliver the safe to you. If you manage to open it with the public code, you can be sure that it was really me who wrote the message because only I know the secret code. + +Of course we are in the digital world so, instead of using physical safes, we exchange computer files; we can use either code to encrypt a data file and make it unreadable (the equivalent of locking the safe) and only the other key will be able to restore it. + +[ PROBABLY NOT NECESSARY ] Computationally, this is achieved using so-called "one way functions", that is, mathematical operations that are easy to perform in one direction but very hard in the opposite. For example, it's very easy to compute the products of two prime numbers but very hard to find the prime factors decomposition of a number if the factors are very large. + +You can see how PKC is a game-changer in the world of spies, military intelligence and secret agents, and why Hellman feared for his life when he made his discovery public. But PKC has a lot of peaceful applications as well; for instance, it is the fundamental ingredient of the now ubiquitous _blockchain_ concept, which powers virtual currencies such as Bitcoin. + diff --git a/writing/computational thinking/recursion/Recursive algorithms.docx b/writing/computational thinking/recursion/Recursive algorithms.docx new file mode 100644 index 0000000..9a25d37 Binary files /dev/null and b/writing/computational thinking/recursion/Recursive algorithms.docx differ diff --git a/writing/computational thinking/recursion/rec1.txt b/writing/computational thinking/recursion/rec1.txt new file mode 100644 index 0000000..619e712 --- /dev/null +++ b/writing/computational thinking/recursion/rec1.txt @@ -0,0 +1,9 @@ +As kids, we are taught a lot of algorithmic procedures, if you think about it: how to tie our shoelaces, how to read and write, how to play board games, how to look up a number in a phone book. All these algorithms are of the linear kind, much like cooking recipes: they describe a set of actions to be perfomed sequentially, with the occasional if/then/else decision thrown in. There is however a very different and very powerful class of algorithms, called recursive algorithms, that, unless we learn to program a computer, we may never be exposed to. Recursion is a problem-solving technique that works by breaking down a complex question into smaller and smaller pieces until their solution becomes amost trivial; the solution to the original problem can then reconstituted from the small pieces up. + +Recursion, although less intuitive than linear procedures, could be a part of our daily life, if we so chose. Assume that, as a kid, you are taught the following "proper behavior" for when you're standing in a line: if someone behind you asks how many people are waiting, you proceed as follows: + - if you're the first person in line, you answer "one" + - otherwise, you ask the person in front of you how many people are waiting and your answer will be their answer plus one +If everyone in line adheres to these two simple rules, it's easy to see that no matter how long the line, the question from the newcomer will propagate to the top of the line and then the answers will propagate back until they reach the end. The amount of work performed by each person in line is minimal (either an easy immediate answer or a delayed, equally easy answer) and the relatively more demanding problem of counting a long line has been evenly split among everyone involved. + +"Divide et impera" is a Latin motto, sometimes attributed to Julius Caesar, that could be translated as "dominate by subdividing"; it mirrors the widespread belief that political power can be better wielded by dividing its subjects into small isolated groups. Much more peacefully, recursion will apply a divide et impera strategy to turn a demanding computational problem into a much more manageable one. For instance, nowadays, the availability of digital content on our personal devices relies on efficient data compression methods that can squeeze all this multimedia information over radio waves or compact memory cards. This efficiency originates from the power of recursion. At the heart of virtually every compression scheme is a powerful mathematical manipulation called the Fourier Transform. Computation of the transform used to be very costly in terms of computer power but, in the 1960s, a recursive algorithm was discovered (called the Fast Fourier Transform, or FFT). The efficiency of the FFT is perhaps the fundamental ingredient of the so-called digital revolution. To give you an example, computing the standard Fourier Transform of a one-megapixel photograph would require one thousand billion mathematical operations; using the FFT, the same result can be achieved with just 20 million operations! That's a saving of five orders of magnitude: not even Caesar could have anticipated such a resounding tactical success! + diff --git a/writing/computational thinking/shazam/shazam.docx b/writing/computational thinking/shazam/shazam.docx new file mode 100644 index 0000000..16cf3ed Binary files /dev/null and b/writing/computational thinking/shazam/shazam.docx differ diff --git a/writing/computational thinking/shazam/shazam.txt b/writing/computational thinking/shazam/shazam.txt new file mode 100644 index 0000000..48dccac --- /dev/null +++ b/writing/computational thinking/shazam/shazam.txt @@ -0,0 +1,37 @@ +My music collection has become very diverse of late: whenever I hear a tune that I like, either on the radio or in some public space, I can just take out my smartphone, let it "listen" to the music for a while and, presto, the name of the song and the artist appear on my screen -- together with a link to buy the digital file, of course! How do music recognition algorithms such as Shazam work? Well, it turs out that they behave like a clever librarian in a Babel of musical records. + +When you let Shazam listen through the microphone, the app takes the incoming sound and chops it up in a sequence of short audio slices about one second long each. The information in each slice is made more compact using time-frequency analysis, a set of mathematical techniques that we have already mentioned in our first column on MP3 compression. Each slice yields a so-called audio "fingerprint" so that, if you let the app listen for, say, 10 seconds, a sequence of 10 fingerprints is generated. The sequence is then sent to Shazam's remote servers for analysis. + +Bear in mind that, to be really useful, Shazam's central database must contain the fingerprints of virtually every song ever published all over the world; this is of course an enormous amount of data, probably on the order of a billion records, so that finding the match for an incoming sequence of fingerprints becomes the proverbial needle in a haystack problem. + +Locating a specific item in an ocean of possibilities is a challenge that librarians know very well: how can they find a specific book amongst thousands of volumes? In the limit, one could go through the entire inventory one book at a time, but that would obviosuly be painfully slow. Even a simple trick such as storing books alphabetically greatly reduces the search time on average. For even more efficiency, libriaries use a more sophisticate method known as the Universal Decimal Classification system (UDC). This is an algorithm (run by humans instead of computers) that maps the subject matter of a book into a decimal number; the rules are a bit complicated but, for example, the number 636.8 indicates a book about cats, while 531.5 indicates a book about gravity -- you may have seen those numbers on the spine of a borrowed book. The important thing is that there exists a precise procedure (the algorithm) that can be used to find the UDC number for any given book. Numbers are much easier to look up than titles and summaries, and they can be easily ordered; UDC tags therefore provide a quick and reliable way to organize and retrieve books in a large library. + +In computer science a method like UDC, that is, an algorithm that converts complex information into a number, is called a "hashing" function. The name stems from the analogy with the action of chopping raw food into a more manageable form; indeed, had it been named in Switzerland, the method could have been called "rosti," our national name for hashed potatoes! Shazam manages to navigate its enormous database by performing a clever hashing on the incoming fingerprints; the resulting number is used to quickly locate a small set of candidate songs that "hash down" to the same number and this reduces the time it takes to find a song to just a few milliseconds. + +Hashing is in fact the technology behind many of the extremely fast services that we enjoy on the internet: given the amount of data online, every time you perform a search you can be sure some hashing function is at work behind the scene. + + + + + + + + + +The UDC system is a method that, in computer science, is called "hashing": complex information is chopped up into a simple, manageable number. + +Clever hashing algorithms are in fact the + +In a different world, hashing could have been called "rosti-ing" + + +My music collection has become very diverse of late: whenever I hear a tune that I like, either on the radio or in some public space, I can just take out my smartphone, let it "listen" to the music for a while and, presto, the name of the song and the artist appear on my screen -- together with a link to buy the digital file, of course! This is a far cry from the old days, when one would hear something nice on the radio and then be left with the unanswerable question: what was that? But how do music recognition algorithms such as Shazam work? Well, it turs out that they work really like a clever librarian in a Babel of musical records. + +The first step, when you launch the Shazam app, takes place inside your smartphone, and it consists of a time-frequency decomposition of the sound captured by the microphone. Although the words may sound intimidating, the underlying principle is relatively easy to explain if we think of standard musical notation [NB it would be nice to have an image here]: in a score, the notes (i.e. the black dots) represent the melody as a sequence of pitches (i.e. frequencies) over time. So, initially, the Shazam app builds a compact "score" from the incoming sound; this pre-processed data, also known as the "fingerprint," is then sent to a remote server farm for identification. [NB do we have a column on fourier to refer to?] + +The Shazam database hosted in the server farm contains the fingerprints of basically every song ever published worldwide, that is, more that ten million tracks; this is of course an immense amount of data, so that identifying an incoming fingerprint becomes the proverbial needle in a haystack problem. And yet, the app returns a response very quickly! + +Now, if you ever borrowed a book from a public library you will have noticed a label on the spine with a multi-digit number; for instance, in the Universal Decimal Classification system (UDC), the number 636.8 indicates a book about cats, while 531.5 indicates a book about gravity. Numbers are much easier to look up than titles and summaries and they can be easily ordered; UDC tags therefore provide a quick and reliable way to organize and retrieve books in a large library. The procedure to assign a UDC number to a book is a true algorithm (although it is performed not by computers but by librarians) and it is described in the UDC manual. Such procedures are called "hashing" in computer science because they chop up a complex amount of information into a simple, manageable number. + +Shazam manages to navigate its enormous database by performing a similar clever hashing on the incoming fingerprints; the resulting hash is used to quickly select a small set of candidate songs that "hash down" to the same number and this reduces the time it takes to find a song to just a few milliseconds. + diff --git a/writing/computational thinking/siri/siri.docx b/writing/computational thinking/siri/siri.docx new file mode 100644 index 0000000..13036f4 Binary files /dev/null and b/writing/computational thinking/siri/siri.docx differ diff --git a/writing/computational thinking/siri/speech1.txt b/writing/computational thinking/siri/speech1.txt new file mode 100644 index 0000000..8ed8c36 --- /dev/null +++ b/writing/computational thinking/siri/speech1.txt @@ -0,0 +1,16 @@ +I'm sorry Dave, I'm afraid I can't do that + +I'm sorry I didn't quite catch that. + + +the cht figure + +principle of least effort: selectively turning on attention when interested in the subject +"If entropy is too high (i.e. there are too many highly unpredictable messages), then the effort to decode the messages becomes too onerous. The receiver will at best only partially decode the messages and, at worst, not decode them at all. Under this scenario, the amount of entropy has exceeded the receiver’s capacity to decode the messages." + +brain power consumption: 12W irrespective of mental "activity" +body: 60-80W +laptop: ~25W + + +McGurk effet (lots of videos on the internet) \ No newline at end of file diff --git a/writing/computational thinking/siri/speech2.txt b/writing/computational thinking/siri/speech2.txt new file mode 100644 index 0000000..2b9c348 --- /dev/null +++ b/writing/computational thinking/siri/speech2.txt @@ -0,0 +1,40 @@ + + +Even before the advent of computers, there have been countless machines capable of recording and transmitting verbal or visual information. +What these machines were lacking (and, to some extent, what computers are lacking as well) is the ability to extract a "concept" out of this merely factual representation; extract a description from pixels or words from sound recordig. This extraction of meaning is often labeled the "gestalt effect", after the ... and is one of the most amazing, complex functions of the human brain. + +what is amazing is that this all happens in the background, with little or no conscious effort. + +Perception is a phenomenal guessing game. Senses provide some clues and the xxx layers in the brain formulate a series of hypotheses +what's incredible in all this is the reliability and the speed of the process + +example with THE CHT and with sentence without vowels +mcgurk effect to make things even more complicated +redundancy of language: 1.2 bits per letter + +two-stage: feature (phone) extraction + contextual language model. Both formidably difficult tasks +phones are time-frequency entities (categorical perception - foreign language examples - possibly driven by own pronounciation) + +phones exhibit enormous variability: pronunciation, inflection, speed, noise, coarticulation + +failures and successes of the superstructure +cocktail effect +foreign language +selective attention + +"does it make sense?" syntactically, grammatically, semantically, contextually and, finally, is it compatible with a model of the world that each one of us built based on knowledge, experience. YOu can verify the importance of the latter part if you listen to a speech about a complicated subject you know nothing about.... + + +How does siri work +context: search term completion in google, or automatic detection of spelling error "did you mean..." + + +natural language processing. Difference between a grammar book and the way we talk (much in the same vein of the difference between traffic rules and the way we drive) + +humor, insinuations, implicit concepts, pedestrian orders, ellipsis + +acoustic front end: phones +speech to text: phones to syllables, syllables to words, words to sentences <- statistical language models +understanding queries: natural language processing (HAL) + +think green Specifically, in a research paper co-authored by Mars: “the computational resources required for a single query is in excess of 100 times more than that of traditional web search.” \ No newline at end of file diff --git a/writing/computational thinking/siri/speech3.txt b/writing/computational thinking/siri/speech3.txt new file mode 100644 index 0000000..4682b93 --- /dev/null +++ b/writing/computational thinking/siri/speech3.txt @@ -0,0 +1,38 @@ +The year 2018 will mark the 50th anniversary of "2001: a Space Odyssey", one of the most remarkable and influential movies in the history of film. Written and produced in the heyday of the space race (but completed well before the fist moon landing), the movie is an extraordinarily optimistic projection, just a few decades in the future, of the burgeoning technological innovations of the early sixties: in the plot, by 1991 an orbital space station complete with a Hilton hotel serves as a byway station for commercial passengers traveling to inhabited colonies on the moon; and, by 2001, a nuclear-powered manned spaceship is successfully en route towards Jupiter -- a spaceship whose de facto captain is a preternaturally powerful computer named HAL. Needless to say, HAL doesn't have a keyboard and all exchanges between the computer and the astronauts are in the form of natural conversations. + +Surprisingly, in spite of the objective naivete of some of its predictions, one of the movie's most enduring achievements is that it never feels technologically "cringeworthy" in the way of many lesser science-fiction productions. Although no cell phones are portrayed in the story, hand-held tablets do make an appearance, used by the astronauts to watch and read the news during their meal; and, of course, there is a computer who listens and talks: while it may have taken a little bit more than a decade with respect to the movie's timeline, it's fair to say that we all have a little HAL in our pocket these days. And yet, it's also fair to say, a conversation with Siri & co it's still not the seamless experience that we would like it to be -- or that the portrayal of HAL's led us to expect. Why is speech recognition such a difficult problem and how does one "teach" Siri not just to understand but to grasp the _meaning_ of what we say, so that a meaningful response can be offered? + +As always, when trying to design an algorithm that mimics a human capability, the first step must be backwards: let's distance ourselves from what we take for granted and try to think "computationall" at our incredible ability to understand sponken language. In and of itself, speech is just a sequence of basic sounds "pieces," produced by the vocal tract; these minimal sound bites (technically called "phones") can be roughly classified into two categories. The first encompasses the voiced sounds, that is, the vowels; these are the sounds you can sing with, since they are produced by a vibration of the vocal cords and they possess a recognizable pitch. The other sounds are called "unvoiced" and they constitute a menagerie of noises, hisses, and clicking sounds that are produced by complex articulation movements of the mouth, tongue and nose as air is pushed out of the lungs. The fundamentally different nature of these two categories requires completely different analytical approaches: voiced phones will need to be analyzed in the frequency domain, in order to extract their pitch, while unvoiced phones are best examined in the time domain. In humans, this time-frequency analysis is performed by the inner ear; in a machine, it is performed by a combination of signal processing devices called filters. In both cases, the goal is to convert the incoming speech sound into a series of tentative hypotheses on the underlying sequence of phones. The keyword here is "tentative" since exact identification of each phone is made prodigiously difficult by the enormous variability in pronunciation, accent, volume and noise level that occur in natural speech. + +In and of itself, speech is just a sequence of basic sound "pieces" produced by the vocal tract; spoken words are composed of sequences of sounds much in the same way as written words are sequences of letters. The first step in understanding a spoken sentence is to correctly recognize the incoming sequence of sound pieces and, in humans this is performed automatically by the inner ear; it's a tricky process, since some basic sounds such as the vowels are analized on the basis of their pitch (like musical notes) while consonants are more like noise and clikcs and they are recognized based on their changes in time. Algorithmically, + +possess a clear pitch (you can sing to them) they will need be examined by a frequency analysis. Noisy, hissy or clicking sounds such as the consonants, will be classified on the basis of their changes in time. In order to emulate this sophisticated behavior of the ear, an algorithm will have to implement a complex form of signal processing called time-frequency analysis. + +some of these basic sounds + + +these minimal sound bites (technically called "phones") can be roughly classified into two categories. The first encompasses the voiced sounds, that is, the vowels; these are the sounds you can sing with, since they are produced by a vibration of the vocal cords and they possess a recognizable pitch. The other sounds are called "unvoiced" and they constitute a menagerie of noises, hisses, and clicking sounds that are produced by complex articulation movements of the mouth, tongue and nose as air is pushed out of the lungs. The fundamentally different nature of these two categories requires completely different analytical approaches: voiced phones will need to be analyzed in the frequency domain, in order to extract their pitch, while unvoiced phones are best examined in the time domain. In humans, this time-frequency analysis is performed by the inner ear; in a machine, it is performed by a combination of signal processing devices called filters. In both cases, the goal is to convert the incoming speech sound into a series of tentative hypotheses on the underlying sequence of phones. The keyword here is "tentative" since exact identification of each phone is made prodigiously difficult by the enormous variability in pronunciation, accent, volume and noise level that occur in natural speech. + +In general, human perception is an exceedingly sophisticated guessing game: the senses provide some noisy, imprecise clues that the cognitive layers in the brain use to formulate a series of hypotheses; learned structures (such as grammar rules or law of physics) help pruning most of the implausibilities (AS IN WRONG CHESS MOVES) and finally our experience of the world allow us to select the right guess. What's incredible in all this is the reliability and the speed of the whole process. Consider for instance the figure below; you will have had no trouble reading the words "THE CAT" although in the drawing the letter A and H are exact copies of the same scribble. In other words, your brain successfully overrode the stimulus + +increasing difficulty: +phones to word hypotheses -> markov model +words to sentence hypotheses -> grammar and language +sentence to meaning -> world model (medical conference) + +our reliance on the deep support system is painfully evident when trying to understand a foreign language that we don't knownwhile the inner ear keeps working as usual, the corrective layers are useless + +up to a decade ago, speech recognition systems were stuck in this "foreign laungyage" paradigm because language and world models were too complex to implement + +2 3 word prob -> we can do big tables + +world model -> big data! collection + + + + +roughly speaking, we can classify these minimal sound bits (also known as "phones") into two categories: voiced sounds (basically, the vowels) and unvoiced sounds (the consonants). Voiced sounds are characterized by their frequency content: these are the sounds you can sing to + + + + \ No newline at end of file diff --git a/writing/computational thinking/siri/speech4.txt b/writing/computational thinking/siri/speech4.txt new file mode 100644 index 0000000..f5799fe --- /dev/null +++ b/writing/computational thinking/siri/speech4.txt @@ -0,0 +1,9 @@ +The year 2018 will mark the 50th anniversary of "2001: a Space Odyssey", one of the most remarkable and influential movies in the history of film. Written and produced in the heyday of the space race (but completed well before the fist moon landing), the movie is an extraordinarily optimistic projection, just a few decades in the future, of the burgeoning technological innovations of the early sixties: in the plot, by 1991 an orbital space station complete with a Hilton hotel serves as a byway station for commercial passengers traveling to inhabited colonies on the moon; and, by 2001, a nuclear-powered manned spaceship is successfully en route towards Jupiter -- a spaceship whose de facto captain is an all-powerful computer named HAL. Remarkably, HAL doesn't have a keyboard and all exchanges between the computer and the astronauts are in the form of natural conversations. A little more than a decade after 2001, applications like Apple's Siri started to put something that resembles a little HAL in our pockets; and yet, it's also fair to say, a conversation with Siri is still not the seamless experience that HAL provides in the movie. Why is speech recognition such a difficult problem and how does one "teach" an algorithm like Siri not just to recognize words but to grasp the _meaning_ of what we say, so that a meaningful response can be offered? + +As always, when trying to design an algorithm that mimics a human capability, the first step must be backwards: let's distance ourselves from what we take for granted and try to think "computationally" at our incredible ability to understand spoken language. In and of itself, speech is a sequence of basic sound "atoms" produced by the vocal tract; spoken words are composed of sequences of sounds much in the same way as written words are sequences of letters. The first step in understanding a spoken sentence is to correctly recognize the incoming sequence of sound pieces and, in humans, this is performed automatically by the inner ear; it's a tricky process, since some basic sounds such as the vowels are analized on the basis of their pitch (like musical notes) while consonants are more like noise and clikcs and they are recognized based on their changes in time. Mathematically, the inner ear is performing a sophisticated type of processing called time-frequency analysis, converting the incoming speech into a series of tentative hypotheses on the underlying sequence of atomic sounds. The keyword here is "tentative" since exact identification of each atom is made prodigiously difficult by the enormous variability in pronunciation, accent, volume and noise level that occur in natural speech. When you talk to Siri, this preprocessing is performed inside your cell phone: the phone analyzes the sound atoms and then sends its guesses to some big computer cluster at Apple, where the interesting part begins. + +In general, human perception is an exceedingly sophisticated guessing game: using the imprecise clues provided by the senses, the cognitive layers in the brain quickly formulate competing hypotheses that are then pruned according to rules (such as grammar) and experience; imagine a very advanced game of tic-tac-toe if you will[link to past column]. Consider for instance the figure below; you will have had no trouble reading the words "THE CAT" although, in the drawing, the letter A and H are exact copies of each other. Speech understanding follows the same pattern: word hypotheses are accepted or rejected in spite of imprecise hearing because of your prior language knowledge (you can experience the failure of this process when you listen to a foreign language that you don't know); tentative words are joined into tentative sentences by a similar mechanism that takes grammar and context into account (think of the difference between listening to a technical speech and an informal conversation); and, finally, the accepted meaning is selected based on a sophisticated model of the world, where certain things make sense and others simply don't. + +In a computer, the models for words sentences and meaning are represented by huge probability tables: what are the chances that a certain sound atom follows another one? What is the likelihood that two words occur in the same sentence? What is the probability that a sentence occurs in a particular context? And, finally, what is the probabiity of a correct answer given a question? The algorithm computes all these odds and then chooses the most probable. But there are two formidable difficulties with this approach: in order to have meaningful probability tables, one needs an enormous amount of training material and it's only recently, with the advent of large "big data" repositories that this has become practical. Secondly, in order to store these tables and go through all the necessary probability estimations in real time, one needs extremely large and fast computers; this is why, when you talk to Siri, you need an active internet connection: the real "understanding" takes place remotely, inside Apple's powerful servers, where a probabilistic model of the world is constantly evolving, fueled by the billion queries from users worldwide. + + diff --git a/writing/computational thinking/siri/thecat.jpg b/writing/computational thinking/siri/thecat.jpg new file mode 100644 index 0000000..6b0c774 Binary files /dev/null and b/writing/computational thinking/siri/thecat.jpg differ diff --git a/writing/computational thinking/slam/SLAM.docx b/writing/computational thinking/slam/SLAM.docx new file mode 100644 index 0000000..90fc159 Binary files /dev/null and b/writing/computational thinking/slam/SLAM.docx differ diff --git a/writing/computational thinking/slam/slam.txt b/writing/computational thinking/slam/slam.txt new file mode 100644 index 0000000..974a80c --- /dev/null +++ b/writing/computational thinking/slam/slam.txt @@ -0,0 +1,11 @@ +Before GPS-based navigation system became ubiquitous, if you had to drive to someone's house for the first time you would call them up and get directions to their place in the form of a series of rather vague statements: "after the gas station, turn left at the third intersection; join the main road and then look for a red building on your right, ..." Getting to a destination this way often included some painful backtracking and almost certainly an even more painful argument with your spouse. But, behind the scene (pun intended), a set of very high-level cognitive processes were hard at work to create a mental map of the environment and, at the same time, manage to determine the current position within that map. + +The computational name for these mental processes is called SLAM (Simultaneous Localization and Mapping) and the existence of efficient SLAM algorithms is what makes it possible to build autonomous robots such as the Mars rover or, closer to us, self-driving cars. + +Not all animals navigate their world via internal high-level maps, by the way: try to wave a flying insect out of a window and, most likely, you will end up looking in frustration at the critter's inability to realize that freedom is just a few centimeters away. Yet insects are fully capable of spatial activities such as finding food. It turns out that they do so by a combination of pre-defined exploration patterns and local decision mechanisms based on physical feedback. Interestingly, these strategies are at the heart of the first successful domestic robot ever sold: the Roomba. Place the autonomous vacuum cleaner in a room and you will observe a complex motion pattern, usually starting as a spiral until a wall is bumped against, and then followed by bouts of edge hugging and random zig-zagging. The goal is to cover every point on the floor (the Roomba is a cleaning device, after all) and, although the trajectory is nowhere as efficient as a human's, the insect-inspired biomimicry approach works well and is very economical to implement. + +Self-driving cars, however, need to be able to efficiently navigate a complex terrain full of constantly changing features and therefore we need a SLAM algorithm. To understand how that works, let's pretend you are driving sans GPS, as in the old days, and that your instructions read: "after getting on the main road, drive for about two kilometers and turn left after the red building". You have two imprecise pieces of information (distance and landmark) that you have to map your trajectory to; your strategy will be to perform a series of actions that minimize the error with respect to the instruction. If, for instance, right after joining the main road you immediately see a red building, you will not turn left because that would imply that the distance information is completely wrong. On the other hand, as you get closer to the two-kilometer mark, any red building would be interpreted as the moment to turn and that would reset your uncertainty on your position. In a self-driving car, imprecise positional information is provided by the GPS and by the accelerometers, while visual landmarks are detected by cameras and LIDARs (laser-based ranging devices): the latter are used to improve the precision of the position, while the position is used to choose which landmarks to look for next. This circular refinement is, in a nuthsell, the mode of opeeration of an extremely versatile algorithm called the Kalman filter, which is at the heart of most SLAM methods. + +The first successful self-driving car was designed by a team within Stanford University's Artificial Intelligence Lab, led by Sebastian Thrun (the code that ran the car is actually available online). The design was in response to a public challenge by DARPA, the research branch of the United States Department of Defense. Interestingly, iRobot too, the manufacturer of Roomba, initially developed its technical expertise working for DARPA. Whatever your feeling about it, it seems that our robotic future will have an original debt towards the military... + + diff --git a/writing/sp4comm.multipub/60-ztrans/90-examples.tex b/writing/sp4comm.multipub/60-ztrans/90-examples.tex index bdcb4c7..3141b24 100644 --- a/writing/sp4comm.multipub/60-ztrans/90-examples.tex +++ b/writing/sp4comm.multipub/60-ztrans/90-examples.tex @@ -1,82 +1,81 @@ \section{Examples} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{example}{Transform of infinite-energy sequences}\label{ex:zt:inferg} -We have seen that the DTFT does not converge in the standard sense for infinite-energy sequences such as the unit step; there are many interesting cases in which the input to a filter is not finite-energy, however, and if we still want to use the convolution theorem we need to resort to Dirac delta formalism, which is often tricky. The \ztrans , on the other hand, converges without problems form many sequences that the DTFT cannot handle normally. Consider for example a first-difference filter defined by the CCDE\index{first-difference filter} +\begin{example}[Transform of infinite-energy sequences]\label{ex:zt:inferg} +We have seen that the DTFT does not converge in the standard sense for infinite-energy sequences such as the unit step; there are many interesting cases in which the input to a filter is not finite-energy, however, and if we still want to use the convolution theorem we need to resort to the Dirac delta formalism, which is often tricky. The \ztrans , on the other hand, converges without problems form many sequences that the DTFT cannot handle normally. Consider for example a first-difference filter defined by the CCDE\index{first-difference filter} \[ y[n] = x[n] - x[n-1] \] whose transfer function is simply $H(z) = 1 - z^{-1}$. It is immediate to see that if we apply this filter to the unit step, the result is the discrete-time delta. In the $z$ domain we can easily compute the transform of the unit step as \[ U(z) = \sum_{n=0}^{\infty} z^{-n} = \frac{1}{(1 - z^{-1})}, \qquad \mbox{ROC: } |z| > 1. \] to obtain the output of the filter as \[ H(z)U(z) = 1. \] In general, we can use the \ztrans\ without problem for all infinite-energy, one-sided sequences that grow no more than exponentially. This can be shown using the ratio test for the \ztrans\ sum; remember that the test ensures the absolute convergence of a series with terms $c_n$ if \[ \lim_{n\rightarrow \infty} \bigg|\frac{c_{n+1}}{c_n}\bigg| < 1. \] Consider a causal sequence of the form \[ x[n] = n^\alpha r^n u[n]; \] using the ratio test for the convergence of the transform, we have \[ \lim_{n\rightarrow \infty} \bigg|\frac{(n+1)^\alpha r^{n+1}z^{-n-1}}{n^\alpha r^n z^{-n}}\bigg| = \frac{|r|}{|z|} \, \lim_{n\rightarrow \infty} \bigg|\frac{n+1}{n}\bigg|^\alpha = \frac{|r|}{|z|} \] so that the series converges absolutely as long as $|z| > |r|$. \end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{example}{One-sided transforms} +\begin{example}[One-sided transforms] As we just showed, the \ztrans\ handles one-sided, infinite-energy sequences quite well. Two-sided infinite sequences, on the other hand, are more delicate because the values for $z$ that ``bring down'' the causal portion of the sum (due to the negative powers of $z$) will ``amplify'' the anticausal portion. For instance, the region of convergence for the transform of $\mathbf{x} = 1$ is the empty set. A similar problem occurs with sinusoidal sequences (of which the constant signal $\mathbf{x} = 1$ is a particular example). In these cases, we simply ``kill'' the anticausal part of the signal and derive the transform for a causal version, in all effects taking a \textit{one-sided} \ztrans .\index{one-sided transform} Take for instance the one-sided cosine\index{ztransform@$z$-transform!of periodic signals}: \[ x[n] = \cos(\omega_0 n) \, u[n] \] its \ztrans\ can be derived as \begin{align*} X(z) &= \sum_{n = -\infty}^{\infty} z^{-n} \cos(\omega_0 n) \, u[n] \\ &= \sum_{n = 0}^{\infty} z^{-n} \cos(\omega_0 n) \\ &= \frac{1}{2}\sum_{n = 0}^{\infty} e^{j\omega_0 n}z^{-n} + \frac{1}{2}\sum_{n = 0}^{\infty} e^{-j\omega_0 n}z^{-n} \\ &= \frac{1}{2} \left( \frac{1}{1-e^{j\omega_0} \,z^{-1}} + \frac{1}{1-e^{-j\omega_0}\, z^{-1}} \right) \\ &= \frac{1 - \cos(\omega_0) z^{-1}}{1 - 2\cos(\omega_0)z^{-1} + z^{-2}} \end{align*} Similar results can be obtained for signals such as $x[n] = \sin(\omega_0 n) \, u[n]$ or $x[n] = \alpha^n \cos(\omega_0 n) \, u[n]$. \end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{example}{The impossibility ideal filters}\label{ex:zt:idealimpossible} -The \ztrans\ of a length-$N$ FIR impulse response can be expressed as a polynomial $P(z)$ of degree $N-1$. The fundamental theorem of algebra states that such a polynomial has \textit{at most} $N-1$ roots;\index{roots!of complex polynomial} as a consequence, the frequency response of an FIR filter can never be identically zero over a frequency interval, no matter how small, since, if it were, its polynomial \ztrans\ would have an infinite number of roots on the unit circle. +\begin{example}[The impossibility of ideal filters]\label{ex:zt:idealimpossible} +The \ztrans\ of a length-$N$ FIR impulse response can be expressed as a polynomial $P(z)$ of degree $N-1$. The fundamental theorem of algebra states that any non null polynomial of degree $N-1$ has \textit{at most} $N-1$ roots;\index{roots!of complex polynomial} as a consequence, the frequency response of an FIR filter can never be identically zero over a frequency interval, no matter how small, since, if it were, its polynomial \ztrans\ would have an infinite number of roots on the unit circle (and therefore it would coincide with the null polynomial). -Similarly, by considering the polynomial $P(z)-C$, it follows that the frequency response of an FIR can never be \textit{constant} over an interval, which proves the impossibility of achieving perfectly flat portions of the freqency response with an FIR filter. The argument can be extended to rational transfer functions, confirming the impossibility of a realizable -filter whose characteristic is piecewise flat. +Similarly, by considering the polynomial $P(z)-c$, with $c$ a scalar, we can show that the frequency response of an FIR can never be \textit{constant} over an interval, which proves the impossibility of achieving perfectly flat portions of the frequency response with an FIR filter. The argument can be extended to rational transfer functions, confirming the impossibility of a realizable filter whose characteristic is exactly flat over an interval. \end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Further Reading} The $z$-transform is closely linked to the solution of linear, constant coefficient difference equations. For a more complete treatment, see, for example, R.{} Vich, \textit{Z Transform Theory and Applications\/} (Springer, 1987), or\linebreak A.{} J.{} Jerri, \textit{Linear Difference Equations with Discrete Transforms Method\/}\linebreak (Kluwer, 1996). diff --git a/writing/sp4comm.multipub/60-ztrans/99-exercises.tex b/writing/sp4comm.multipub/60-ztrans/99-exercises.tex index 36df303..06080ef 100644 --- a/writing/sp4comm.multipub/60-ztrans/99-exercises.tex +++ b/writing/sp4comm.multipub/60-ztrans/99-exercises.tex @@ -1,593 +1,373 @@ \section{Exercises} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% -\begin{exercise}{Interleaving} +\begin{exercise}[Interleaving] Consider two two-sided sequences $\mathbf{h}$ and $\mathbf{g}$ and consider a third sequence $\mathbf{x}$ which is built by interleaving the values of $\mathbf{h}$ and $\mathbf{g}$ as: \[ \mathbf{x} = \bigl[ \ldots \,\,\, h[-2] \,\,\, g[-2] \,\,\, h[-1] \,\,\, g[-1] \,\,\, h[0] \,\,\, g[0] \,\,\, h[1] \,\,\, g[1] \,\,\, h[2] \,\,\, g[2] \,\,\, \ldots \bigr] \] with $x[0] = h[0]$. \begin{enumerate} \item Express the $z$-transform of $\mathbf{x}$ in terms of the $z$-transforms $H(z)$ and $G(z)$. \item Assume that the ROC for $H(z)$ is $0.64 < |z| < 4$ and that the ROC for $G(z)$ is $0.25 < |z| < 9$. What is the ROC of $X(z)$? \end{enumerate} \end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% -\begin{exercise}{ROC subtleties} +\begin{exercise}[ROC subtleties] Remember from classic calculus that, while the harmonic series is divergent, the harmonic series with alternating sign is convergent: \[ - \sum_{n=1}^{\infty} \frac{(-1)^n}{n} = \log\frac{1}{2}. + \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} = \ln\frac{1}{2}. \] \begin{enumerate} \item Using the sequence $\mathbf{x}$ defined by $x[n] = (1/n) u[n-1]$, show that we need to consider the \textit{absolute} convergence in determining the ROC if we want it to have circular symmetry. \item Compute the transfer function of a system whose impulse response is equal to $\mathbf{x}$. \end{enumerate} \end{exercise} }\fi \ifanswers{% \begin{solution}{} \begin{enumerate} \item Consider the \ztrans\ of $\mathbf{x}$ \[ X(z) = \sum_{n=1}^{\infty} \frac{z^{-n}}{n}; \] the transform converges in $z=-1$ but not absolutely, since $X(1) = \infty$; if we required simple convergence to establish if a point belongs to the ROC, in this case the ROC wouldn't be circularly symmetric. \item We have \[ X(z) = \sum_{n=1}^{\infty} \frac{z^{-n}}{n} = -\log z; \] this is a rare instance of an irrational transfer function (but which has no practical use). \end{enumerate} \end{solution} }\fi -\end{document} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% +\begin{exercise}[Properties of the z-transform] + Let $\mathbf{x}$ be a discrete-time sequence and $X(z)$ be its corresponding $z$-transform with appropriate ROC. + \begin{enumerate} + \item Prove that the following relation holds: + \[ + \mathcal{Z}\{nx[n]\} = -z\frac{d}{d z}\, X(z) + \] + \item Using (a), show that + \[ + \mathcal{Z}\{(n+1)\alpha^{n}u[n]\} = \frac{1}{(1-\alpha z^{-1})^2}\,,\quad \mbox{ROC: } |z|>|\alpha| + \] + \item Suppose that the above expression corresponds to the impulse response of an LTI system. What can you say about the causality of such a system? What about its stability? + \item Let $\alpha=0.8$: what is the spectral behavior of the corresponding filter? What if $\alpha=-0.8$? + \end{enumerate} +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% -\begin{solution}{} -\end{solution} - -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% +\begin{exercise}[Filter Stability] + Consider a causal discrete system represented by the following difference equation: + \[ + y[n]-3.25\,y[n-1]+0.75\,y[n-2]=x[n-1]+3x[n-2] + \] + \begin{enumerate} + \item Compute the transfer function and check the stability of this system both analytically and graphically. + \item If the input signal is $x[n] = \delta[n]-3\delta[n-1]$, compute the $z$-transform of the output signal and discuss the stability. + \item Take an arbitrary input signal that does not cancel the unstable pole of the transfer function and repeat (b). + \end{enumerate} +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% - -\begin{solution}{} -\end{solution} - -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% - +\begin{exercise}[Filter Stability] + Consider a causal LTI system with the following transfer function: + \[ + H(z) = \frac{3 + 4.5\,z^{-1}}{1+1.5\,z^{-1}} - \frac{2}{1-0.5\,z^{-1}} + \] + Sketch the pole-zero plot of the transfer function and specify its region of convergence. Is the system stable? +\end{exercise} + + + }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% - -\begin{solution}{} -\end{solution} - -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% +\begin{exercise}[Filter Stability] + Consider the transfer function of an anticausal LTI system + \[ + H(z) = (1-z^{-1}) - \frac{1}{1-0.5\,z^{-1}} + \] + Sketch the pole-zero plot of the transfer function and specify its region of convergence. Is the system stable? +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% - -\begin{solution}{} -\end{solution} -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% +\begin{exercise}[Pole-zero plot and magnitude response] + In the following pole-zero plots, in which the circle shows the unit circle, multiple zeros at the same location are indicated by the multiplicity number shown to the upper right of the zero. Sketch the magnitude of each frequency response and determine the type of filter (highpass, lowpass, bandpass). + + \begin{tabular}{cc} + \begin{dspPZPlot}[clabel=~,cunits=false]{1.4} + \dspPZ[type=zero,label=3]{-1,0} + \dspPZ[label=none]{0.73,0} + \dspPZ[label=none]{0.8,0.2} + \dspPZ[label=none]{0.8,-0.2} + \end{dspPZPlot} + & + \begin{dspPZPlot}[clabel=~,cunits=false]{1.4} + \dspPZ[type=zero,label=3]{1,0} + \dspPZ[label=none]{-0.3,0} + \dspPZ[label=none]{-0.36,0.55} + \dspPZ[label=none]{-0.36,-0.55} + \end{dspPZPlot} + \\ + \begin{dspPZPlot}[clabel=~,cunits=false]{1.4} + \dspPZ[type=zero,label=3]{0.342,0.93969} + \dspPZ[type=zero,label=3]{0.342,-0.93969} + \dspPZ[label=none]{0.73,0} + \dspPZ[label=none]{0.8,0.2} + \dspPZ[label=none]{0.8,-0.2} + \dspPZ[label=none]{-0.4,0} + \dspPZ[label=none]{-0.66,0.4} + \dspPZ[label=none]{-0.66,-0.4} + \end{dspPZPlot} + & + \end{tabular} +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% - -\begin{solution}{} -\end{solution} - -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% +\begin{exercise}[Z-transform and magnitude response] + Consider a causal LTI system described by the following transfer function: + \[ + H(z)=\frac{ \frac{1}{6}+\frac{1}{2}\,z^{-1}+\frac{1}{2}\,z^{-2} +\frac{1}{6}\,z^{-3}}{ 1+\frac{1}{3}\,z^{-2}} + \] + \begin{enumerate} + \item Sketch the magnitude response $H(e^{j\omega})$ from the \ztrans . You can use a numerical package to find the + poles and the zeros of the transfer function. What type of filter is $H(z)$? + \item Sketch the pole-zero plot. Is the system stable? + \end{enumerate} + Now consider a length-$128$ input signal $\mathbf{x}$ defined as: + \[ + x[n]= \begin{cases} + 0 & \mbox{for } 0 \leq n \leq 50 \\ + 1 & \mbox{for } 51 \leq n \leq 127 + \end{cases} + \] + \begin{enumerate} + \setcounter{enumi}{2} + \item Plot the magnitude of the DTFT $X(e^{j\omega})$. + \item Call $\mathbf{y}$ the signal obtained by filtering $\mathbf{x}$ with the system described by $H(z)$; plot the signal $\mathbf{y}$ and the magnitude of its DTFT. + \item Explain qualitatively the shape of $y[n]$. + \end{enumerate} +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% -\begin{solution}{} -\end{solution} -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% +\begin{exercise}[DFT and z-transform] + It is immediately obvious that the DTFT of a sequence is simply its $z$-transform evaluated on the unit circle, i.e.\ + for $z = e^{j\omega}$. Equivalently, for a finite-length signal $\mathbf{x}$, the DFT $\mathbf{X}$ is simply the $z$-transform of + the finite support extension of the signal evaluated at $z = e^{j\frac{2\pi}{N}k}$ for $k = 0, \ldots, N-1$: + \[ + X[k] = \left. \sum_{n=0}^{N-1}x[n]z^{-n} \right|_{z = e^{j\frac{2\pi}{N}k}} = \sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}nk} + \] + By taking advantage of this fact, derive a simple expression for the DFT of the time-reversed signal + \[ + \mathbf{x}_r = \bigl[\begin{matrix}x[N-1] & x[N-2] & \ldots & x[1] & x[0] \end{matrix} ]^T + \] +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% -\begin{solution}{} -\end{solution} -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% - -}\fi - -\ifanswers{% - -\begin{solution}{} -\end{solution} - -}\fi - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% +\begin{exercise}[A CCDE] + Consider an LTI system described by the following constant-coefficient difference equation: + \[ + y[n-1] + 0.25\,y[n-2] = x[n] + \] + \begin{enumerate} + \item Write the transfer function of the system. + \item Plot its poles and zeros, and show the ROC. + \item Compute the impulse response of the system. + \end{enumerate} +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% - -\begin{solution}{} -\end{solution} - -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% - -}\fi - -\ifanswers{% - -\begin{solution}{} -\end{solution} - -}\fi - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% +\begin{exercise}[Inverse transform] + Write out the discrete-time signal $\mathbf{x}$ whose $z$-transform is + \[ + X(z) = (1 + 2z) (1+3z^{-1}) + \] +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\ifexercises{% - - -}\fi - -\ifanswers{% -\begin{solution}{} -\end{solution} - -}\fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \ifexercises{% +\begin{exercise}[Signal transforms] + Consider a discrete-time signal $\mathbf{x}$ whose $z$-transform is + \[ + X(z) = 1 + z^{-1} + z^{-3} + z^{-4} + \] + \begin{enumerate} + \item Compute $X(e^{j\omega})$. Your final result should be in the form of a real function of $\omega$ times a pure phase term. + \item Sketch the magnitude of $X(e^{j\omega})$ as accurately as you can. + \end{enumerate} + Consider now the length-$4$ signal $\mathbf{y}$ defined by: + \[ + y[n] = x[n], \qquad \quad n = 0, 1, 2, 3 + \] + \begin{enumerate} + \setcounter{enumi}{2} + \item Compute the four DFT coefficients $Y[k]$, $k = 0, 1, 2, 3$. + \end{enumerate} +\end{exercise} }\fi \ifanswers{% \begin{solution}{} \end{solution} }\fi -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%% - - - - -%2%% -\smallskip -\begin{exercise}{Properties of the z-transform} -Let $x[n]$ be a discrete-time sequence and $X(z)$ be its -corresponding $z$-transform with appropriate ROC. -\begin{enumerate} -\item Prove that the following relation holds: -\[ -nx[n] \; \stackrel{Z}{\longleftrightarrow} \; -z\frac{d}{dz}\, X(z) -\] -\item Using (a), show that -\[ -(n+1)\alpha^{n}u[n]\; \stackrel{Z}{\longleftrightarrow} \; -\frac{1}{(1-\alpha z^{-1})^2}\,,\quad \qquad |z|>|\alpha| -\] -\item Suppose that the above expression corresponds to the impulse -response of an LTI system. What can you say about the -causality of such a system? What about its stability? -\item Let $\alpha=0.8$: what is the spectral behavior of the -corresponding filter? What if $\alpha=-0.8$? -\end{enumerate} -\end{exercise} - -%3%% -\begin{exercise}{Stability} -Consider a causal discrete system represented by the following -difference equation: -\[ -y[n]-3.25\,y[n-1]+0.75\,y[n-2]=x[n-1]+3x[n-2] - \] -\begin{enumerate} -\item Compute the transfer function and check the stability of -this system both analytically and graphically. -\item If the input -signal is $x[n]=\delta[n]-3\delta[n-1]$, compute the $z$-transform -of the output signal and discuss the stability. -\item Take an -arbitrary input signal that does not cancel the unstable pole of -the transfer function and repeat (b). -\end{enumerate} -\end{exercise} - -%4%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{exercise}{Pole-zero plot and stability -- I} -Consider a causal LTI system with the following transfer function: -\[ - H(z) = \frac{3 + 4.5\,z^{-1}}{1+1.5\,z^{-1}} - \frac{2}{1-0.5\,z^{-1}} -\] -Sketch the pole-zero plot of the transfer function and -specify its region of convergence. Is the system stable? -\end{exercise} - -\begin{exercise}{Pole-zero plot and stability -- II} -Consider the transfer function of an anticausal LTI system -\[ - H(z) = (1-z^{-1}) - \frac{1}{1-0.5\,z^{-1}} -\] -Sketch the pole-zero plot of the transfer function and -specify its region of convergence. Is the system stable? -\end{exercise} - -%5%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{exercise}{Pole-zero plot and magnitude response} -In the following pole-zero plots, multiple zeros at the same -location are indicated by the multiplicity number shown to -the upper right of the zero. -Sketch the magnitude of each frequency response and determine the -type of filter. - -\begin{figure}[H] -\begin{center}\small - \par\vspace{2ex}\par - \begin{psPZplot}[unit= ]{1.4} - \psPZplotPoint[type=zero,label=3,labelpos=45]{-1}{0} - \psPZplotPoint{0.73}{0} - \psPZplotPoint{0.8}{0.2} - \psPZplotPoint{0.8}{-0.2} - \end{psPZplot} -\qquad -% \par\vspace{2ex}\par - \begin{psPZplot}[unit= ]{1.4} - \psPZplotPoint[type=zero,label=3,labelpos=45]{1}{0} - \psPZplotPoint{-0.3}{0} - \psPZplotPoint{-0.36}{0.55} - \psPZplotPoint{-0.36}{-0.55} - \end{psPZplot} - \par\vspace{5ex}\par - \begin{psPZplot}[unit= ]{1.4} - \psPZplotPoint[type=zero,label=3,labelpos=45]{0.342}{0.93969} - \psPZplotPoint[type=zero,label=3,labelpos=-45]{0.342}{-0.93969} - \psPZplotPoint{0.73}{0} - \psPZplotPoint{0.8}{0.2} - \psPZplotPoint{0.8}{-0.2} - \psPZplotPoint{-0.4}{0} - \psPZplotPoint{-0.66}{0.4} - \psPZplotPoint{-0.66}{-0.4} - \end{psPZplot} -\end{center} -\end{figure} -\end{exercise} - -%7%% -%%%%%%%%%%% -%\vskip-4mm -\begin{exercise}{z-transform and magnitude response} -Consider a causal LTI system described by the following transfer function: -\[ -H(z)=\frac{\ds \frac{1}{6}+\frac{1}{2}\,z^{-1}+\frac{1}{2}\,z^{-2} -+\frac{1}{6}\,z^{-3}}{\ds 1+\frac{1}{3}\,z^{-2}} -\] -\begin{enumerate} - \item Sketch the magnitude response $H(e^{j\omega})$ from - the \ztrans . You can use a numerical package to find the - poles and the zeros of the transfer function. What type - of filter is $H(z)$? - \item Sketch the pole-zero plot. Is the system stable? -\end{enumerate} -Now fire up your favorite numerical package (or write some C -code) and consider the following length-$128$ input signal: -\[ -x[n]= -\begin{cases} -0 & \ n \in [\begin{matrix}1 &\ldots &50 \end{matrix} ] \\ -1 & \ n \in [\begin{matrix}51 & \ldots& 128\end{matrix}] -\end{cases} -\] -\begin{enumerate} - \setcounter{enumi}{2} - \item Plot the magnitude of its DTFT $\bigl| X[k] \bigr|$. - \item We want to filter $x[n]$ with $H(z)$ to obtain - $y[n]$: Compute and plot $y[n]$ using the Matlab function - {\tt filter}. Plot also the magnitude of its DTFT $ \bigl| - Y[k] \bigr|$. - \item Explain qualitatively the form of $y[n]$. -\end{enumerate} -\end{exercise} - - - -%7%% -\begin{exercise}{DFT and z-transform} -It is immediately obvious % to see -that the DTFT of a sequence $x[n]$ is -simply its $z$-transform evaluated on the unit circle, %\linebreak - i.e.\ -for $z = e^{j\omega}$. Equivalently, for a finite-length -signal $\mathbf{x}$, the DFT is simply the $z$-transform of -the finite support extension of the signal evaluated at\linebreak - $z = W_N^{-k}$ for $k = 0, \ldots, N-1$: -\[ - X[k] = \left. \sum_{n=0}^{N-1}x[n]z^{-n} \right|_{z = W_N^{-k}} -= \sum_{n=0}^{N-1}x[n]W_N^{nk} -\] -By taking advantage of this fact, derive a simple expression -for the DFT of the time-reversed signal -\[ - \mathbf{x}_r = \bigl[ -\begin{matrix}x[N-1] & x[N-2] & \ldots & x[1] & x[0] -\end{matrix} ]^T -\] -\end{exercise} - - - -%8%% -%%%%%%%%%%%%% -\begin{exercise}{A CCDE} -Consider an LTI system described by the following -constant-coefficient difference equation: -\[ - y[n-1] + 0.25\,y[n-2] = x[n] -\] -\begin{enumerate} -\item Write the transfer function of the system. -\item Plot its poles and zeros, and show the ROC. -\item Compute the impulse response of the system. -\end{enumerate} -\end{exercise} - - -%9%% -%%%%%%%%%%%%%%%%%%%%%%% -\begin{exercise}{Inverse transform} -Write out the discrete-time signal $x[n]$ whose $z$-transform is -\[ - X(z) = (1 + 2z) (1+3z^{-1}) -\] -\end{exercise} - - - -%10%% -%%%%%%%%%%%%%%%%%%%%%%% -\begin{exercise}{Signal transforms} -Consider a discrete-time signal $x[n]$ whose $z$-transform is -\[ - X (z) = 1 + z^{-1} + z^{-3} + z^{-4} -\] -\begin{enumerate} -\item Compute the DTFT of $x[n]$, $X(e^{j\omega})$. Your -final result should be in the form of a real function of -$\omega$ times a pure phase term. -\item Sketch the magnitude of $X(e^{j\omega})$ as accurately -as you can. -\end{enumerate} -Consider now the length-$4$ signal $y[n]$: -\[ - y[n] = x[n], \qquad \quad n = 0, 1, 2, 3 -\] -\begin{enumerate} -\setcounter{enumi}{2} -\item Compute, -for $y[n]$, the four DFT coefficients $Y[k]$, $k = 0, 1, 2, 3$. -\end{enumerate} -\end{exercise} - diff --git a/writing/sp4comm.multipub/sp4comm.tex b/writing/sp4comm.multipub/sp4comm.tex index 8328e1a..33b3bc4 100644 --- a/writing/sp4comm.multipub/sp4comm.tex +++ b/writing/sp4comm.multipub/sp4comm.tex @@ -1,155 +1,155 @@ %% Test book for multipub %% \documentclass[12pt,a4paper,fleqn]{book} % include multipub package and declare desired format (PRINT | EPUB | KINDLE) % (note: cannot use package and option formalism because it breaks LateXML) \input{../multipub/toolbox/tex/multipub} \multipub{PRINT} % packages included here must be common to all versions, i.e. they need % to have LateXML bindings available \usepackage{makeidx} \usepackage{amsmath, amssymb} \usepackage{graphicx} \usepackage{url} % now do target-specific includes and inits \begin{PRINT} \include{styles/printlayout} \include{styles/color} % \include{styles/grayscale} \end{PRINT} \begin{KINDLE} \include{styles/printlayout} \end{KINDLE} \begin{HTML} \include{styles/epublayout} \end{HTML} \begin{EPUB} \include{styles/epublayout} \end{EPUB} % Here we can define some macros common to all versions. This, for instance, % produces numberless sections that still appear in headers and TOC \newcommand{\codasection}[1]{% \section*{#1}% \markright{#1}% \addcontentsline{toc}{section}{#1}} \newcommand{\itempar}[1]{\par\vspace{1em}\noindent{\sffamily\bfseries #1}\hspace{1ex}} \newcommand{\circonv}{\mbox{\,$\bigcirc$\hspace{-1.8ex}\scriptsize{N} \,}} \newcommand{\Real}[1]{\mbox{Re\{$#1$\}}} \newcommand{\Imag}[1]{\mbox{Im\{$#1$\}}} \newcommand{\ztrans}{\mbox{$z$-transform}} \newcommand{\expt}[1]{\mbox{E$\left[ #1 \right]$}} \newcommand{\proba}[1]{\mbox{P[$#1$]}} \renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\DFT}[1]{\mbox{DFT\big\{$#1$\big\}}} \newcommand{\IDFT}[1]{\mbox{IDFT\big\{$#1$\big\}}} \newcommand{\rect}{\operatorname{rect}} \newcommand{\sinc}{\operatorname{sinc}} \newcommand{\de}{\, \mathrm{d}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \setcounter{secnumdepth}{3} \makeindex %% OUPUT SELECTOR \newif\ifexercises \newif\ifanswers %% choose one \exercisestrue\answersfalse % only exercises %\exercisesfalse\answerstrue % only solutions -\exercisestrue\answerstrue % both +%\exercisestrue\answerstrue % both \multipubbegin \begin{document} \title{Test Book for PDF and EPUB} \author{Paolo Prandoni} \date{} \maketitle \frontmatter \tableofcontents %\includefile{00-intro}{00-intro} \mainmatter %\includefile{20-signals}{10-signals} \begincoda %\includefile{20-signals}{90-examples} %\includefile{20-signals}{99-exercises} \endcoda %\includefile{30-vectors}{00-vectors} %\includefile{60-ztrans}{10-ztrans} \begincoda \includefile{60-ztrans}{90-examples} \includefile{60-ztrans}{99-exercises} \endcoda %\includefile{90-sampling}{00-intro} %\includefile{90-sampling}{10-interpolation} %\includefile{90-sampling}{20-sampling} %\includefile{90-sampling}{30-processing} \begincoda %\includefile{90-sampling}{90-examples} %\includefile{90-sampling}{99-exercises} \endcoda %\includefile{110-multirate}{10-multirate} \begincoda %\includefile{110-multirate}{90-examples} %\includefile{110-multirate}{99-exercises} \endcoda %\includefile{130-image}{20-jpg} %\includefile{130-image}{00-intro} %\includefile{130-image}{10-improc} %\includefile{130-image}{20-jpg} %\includefile{80-stochastic}{00-intro} %\includefile{80-stochastic}{10-spectral} %\includefile{80-stochastic}{20-adaptive} % vector space %\includefile{30-vectors}{00-vectors} % Fourier analysis %\includefile{40-fourier}{00-intro} %\includefile{40-fourier}{10-DFT} %\includefile{40-fourier}{20-DTFT} %\includefile{40-fourier}{30-tables} %\begincoda %\includefile{40-fourier}{100-realtrans} %\includefile{40-fourier}{110-wagonwheel} %\includefile{ch02}{chapter02} \backmatter \printindex \end{document} diff --git a/writing/sp4comm.multipub/styles/printlayout.tex b/writing/sp4comm.multipub/styles/printlayout.tex index ab58204..ea91c19 100644 --- a/writing/sp4comm.multipub/styles/printlayout.tex +++ b/writing/sp4comm.multipub/styles/printlayout.tex @@ -1,109 +1,121 @@ %% definitions of page layout for PRINT version %% The following macros affect the rendering of sections and other %% environments and they will have to be redefined for all other %% styles such as EPUB %% exercises, solutions, examples % \usepackage{amsthm} -\theoremstyle{definition} +\newtheorem*{solution}{\normalfont\normalsize\sffamily\bfseries Solution} + +\newtheoremstyle{dspbook}% % Name + {}% % Space above + {2em}% % Space below + {}% % Body font + {}% % Indent amount + {\bfseries}% % Theorem head font + {.}% % Punctuation after theorem head + {1em}% % Space after theorem head, ' ', or \newline + {\thmname{#1}\thmnumber{ #2}:\hspace{0.5ex}\thmnote{#3}}% % Theorem head spec (can be left empty, meaning `normal') +\theoremstyle{dspbook} +%\theoremstyle{definition} % to specify an inline title use \begin{exercise}\pstyle{title text} \newtheorem{exercise}{\normalfont\normalsize\sffamily\bfseries Exercise}[chapter] -\newtheorem*{solution}{\normalfont\normalsize\sffamily\bfseries Solution} \newtheorem{example}{\normalfont\normalsize\sffamily\bfseries Example}[chapter] \def\extitle#1{{\normalfont\normalsize\sffamily\bfseries #1.\ }} + %% this is used for end-of-chapter sections (further reading, appendices, etc) %% In the PRINT version we change the graphical appearance of section titles %% %% numbered sections: gray rounded box with black text (see later for \sectionbox) \def\normalbanner{\sectionbox{gray!80}{black}{\thesection\hspace{1em}}} %% unnumbered sections: darkgray rounded box with white text \def\codabanner{\sectionbox{darkgray}{white}{}} \def\begincoda{\titleformat{\section}{}{}{0pt}{\codabanner}} \def\endcoda{\titleformat{\section}{}{}{0pt}{\normalbanner}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% In print layout we can compile the pstricks figures directly: \usepackage{pstricks} \usepackage{pst-node,pstricks-add,pst-tree,pst-plot,pst-3dplot} \usepackage{dsptricks,dspfunctions,dspblocks} % figure default sizes for dspTricks \setlength{\dspWidth}{0.8\textwidth} \setlength{\dspHeight}{0.4\dspWidth} \def\dspWidthCol{0.4\textwidth} \def\dspHeightCol{0.2\dspWidth} \def\dspHeightShort{0.15\dspWidth} %% fonts \usepackage{avant} \usepackage{courier} \usepackage[utopia]{mathdesign} \usepackage{titlesec} \usepackage[parfill]{parskip} \usepackage[format=hang,font={small,it},labelfont=bf]{caption} %% postscript macros for section headings % #1: background color % #2: foreground color % #3: section heading (either \thesection or nothing) % #4: section title \def\sectionbox#1#2#3#4{% \psframebox*[cornersize=absolute,linearc=1mm,framesep=2mm,fillcolor=#1]{% \parbox{\dimexpr\textwidth-4mm}{% \centering\parbox{\dimexpr\textwidth-4em}{% \color{#2}\normalfont\Large\sffamily\bfseries#3#4}}}} %% titles \titleformat{\chapter}[display]{\normalfont\huge\sffamily\filcenter}% {\large\chaptertitlename\ \thechapter}{20pt}{\bfseries\huge} %% modified section headings for normal sections \titleformat{\section}{}{}{0pt}{\normalbanner} %% subsections & co. \titleformat{\subsection}{\normalfont\large\sffamily\bfseries}{\thesubsection}{1em}{} \titleformat{\subsubsection}{\normalfont\normalsize\sffamily\bfseries}{}{1em}{} \titleformat{\paragraph}[runin]{\normalfont\normalsize\sffamily\bfseries}{}{1em}{} %% headers % \usepackage{fancyhdr} \pagestyle{fancy} \renewcommand{\chaptermark}[1]{\markboth{{\thechapter \ -- \ #1}}{}} \renewcommand{\sectionmark}[1]{\markright{{\thesection \ -- \ #1}}} \fancyhead[LE,RO]{\sffamily\thepage} \fancyhead[RE]{\sffamily\slshape\leftmark} \fancyhead[LO]{\sffamily\slshape\rightmark} \fancyfoot{} \renewcommand{\headrulewidth}{0pt} \renewcommand{\footrulewidth}{0pt} %% Table of contents % \usepackage{tocloft} \renewcommand{\cfttoctitlefont}{\huge\bfseries\sffamily} \renewcommand{\cftchapfont}{\large\bfseries\sffamily} \renewcommand{\cftsecfont}{\sffamily} \renewcommand{\cftsubsecfont}{\sffamily} \renewcommand{\cftchappagefont} {\sffamily} \renewcommand{\cftsecpagefont}{\sffamily} \renewcommand{\cftsubsecpagefont}{\sffamily}