In timestamped Thu, 12
Jul 2007 12:05:51 +0100, Jonathan Bromley
<
[email protected]> posted:
|--------------------------------------------------------------------|
| |
|>can anybody just give me the code for sequence |
|> detector A1A13232... continously with out |
|> overlapping. i am trying different options i wnat |
|>some idea .... |
| |
|I could start to rant about lazy students and homework |
|problems, but I won't. Instead I'll note that these |
|idiotic sequence detector problems make my blood boil; |
|they are in most cases impractical, under-specified and" |
|--------------------------------------------------------------------|
In fairness, it may be good to expose students to under-specified
demands to force the students to realize that they need to check what is
really desired.
|--------------------------------------------------------------------|
|"incompetent attempts to find a useful example of a |
|state machine. They provide superb ammunition for |
|people who wish to criticise academic teaching of |
|digital design on the grounds that it is detached |
|from reality. They give lecturers a cheap way to |
|keep their students busy for a week, and to generate |
|some convincing-looking but meaningless scores for |
|the coursework assessment." |
| |
|--------------------------------------------------------------------|
Is it possible to have a correlation between scores and anything of
importance? E.g. in one of my second year computer science assmebly
language courses, I was much better than almost everyone else in the
class. Unlike most people, I did the eight weeks' or so of assembly
programming practice questions (which did not contribute to the
continuous assessment: that was marked with lab exams after the time
set aside for practice) in approximately just two days at the
beginning of the course. I ended up getting an extremely low mark for
the lab exam. Bad luck happens. In high school I was really fond of
physics and not particularly fond of biology. I was very aware of the
answers for questions in a physics exam so spent a long time lovingly
answering them, whereas I had to not particularly pleasantly work very
hard at biology so I got a low mark for physics and a high mark for
biology. Good luck happens (for biology). I have also gotten high
marks for things I am great at. As a former lab tutor involved in lab
exams, I know that I am not the only person this sort of thing has
happened to.
Anyhow, some of the state machine content I wrote for a document for
university (reproduced at the end of this post instead of attached)
was useful for discovering that the VHDL professor who is the tutor
for my Ph.D. did not know at the time what one-hot encoding is. Though
checking for one-hot encoding would in practice not be performed in a
HDL etc., it is not useless for the purpose of telling a beginner to
write something which is harder than ten seconds' work and much easier
than something could be sold.
|--------------------------------------------------------------------|
|"[..] |
| |
|Suppose you were to do what you should have done anyway: |
|pay attention to your classes and read your books. Then |
|you would know how to build an automaton that recognises |
|the sequence. But tell me: if the pattern then changed |
|to A2B23334 instead, what would you need to do? Yup, |
|you got it: redesign the whole automaton from scratch. |
|Terrific re-usability and generality, don't you think? |
| |
|More coffee, NOW, before I get really cross
|
|-- |
|Jonathan Bromley, Consultant |
| |
|DOULOS - Developing Design Know-how |
|VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services" |
|--------------------------------------------------------------------|
Not everything needs to be reusable. Anyhow, languages such as VHDL
which need an explicit keyword for generics are intrinisically less
amenable to ridiculous levels of unnecessary reusability as in ML and
such languages.
Regards,
Colin Paul Gloster
\documentclass[english,a4paper,10pt]{report}
\usepackage[english]{babel}
\usepackage{a4wide}
\begin{document}
\begin{center}
Moderately easy VHDL exercises which would be suitable to assign to
undergraduates as homework as a lab tutor (not that this is for real
undergraduates)
\end{center}
\section{One-hot encoding}
A one-hot encoding contains strictly only one digit whose value is
1. Write an entity which determines whether or not sixteen input bits
form a valid one-hot encoding.
\subsection{\arabic{subsection}}
Write an entity which receives a sequence of bits and which determines
whether or not the sequence is a one-hot encoding. The quantity of
bits in the sequence is an arbitrarily unknown length. The sequence is
received one bit at a time on a single input pin. That input pin is
ignored when another input pin (a flag) is low.
\subsection{\arabic{subsection}}
Rewrite the 16 bit entity which detects a one-hot encoding to use the
\texttt{GENERIC} keyword such that it can be instantiated to any
chosen length of a sequence.
\section{Area consumption}
\subsection{Data type used in a \texttt{case} statement of a finite
state machine}
Record your synthesis tools' reports of area consumption for different
reifications of an enumeration type in a finite state machine with
respect to changing the reifications by using the \texttt{attribute
ENUM\_ENCODING} of IEEE Std 1076.6-1999, \emph{IEEE Standard for VHDL
Register Transfer Level (RTL) Synthesis}\footnote{Warning: this does
not work in XST 6.2.03i despite \\
doc$\backslash$usenglish$\backslash$help$\backslash$iseguide$\backslash$html$\backslash$fd\_implement\_one\_hot\_encoded\_state\_machines\_using\_vhdl.htm
and despite the untrue claim in
doc$\backslash$usenglish$\backslash$help$\backslash$iseguide$\backslash$html$\backslash$cd\_fsm.html
\begin{quotation}``FSMs expressed in VHDL using enumerated type that
have an ENUM\_ENCODING attribute specified are not
recoded''\end{quotation}
so instead, some of this exercise can be done by
selecting Process $\rightarrow$ Properties $\rightarrow$ HDL Options
$\rightarrow$ FSM Encoding Algorithm $\rightarrow$ various
encodings. Lest you have not noticed already, neither compliance to a
standard nor truthful documentation is something which vendors
earnestly undertake to achieve in this industry.}. Apply binary; Gray;
one-hot; and almost one-hot (the same as one-hot but all zeroes is
also legal) encodings to the \texttt{type mc\_state\_type} of the
following state machine\footnote{Reproduced from Listing 10.6 of Pong
P. Chu, \emph{RTL Hardware Design Using VHDL: Coding for Efficiency,
Portability, and Scalability}, John Wiley, 2006.}. Does the area also
vary if the assignment of the bits of one kind of encoding scheme
(e.g. binary) is changed? E.g. does \texttt{"000 001 010 011
100 101"} consume the same area as \texttt{"010 000 001
100 101 011"}? Does the area vary whether you are synthesizing for
a Field Programmable Gate Array (FPGA) or a (so-called) Complex
Programmable Logic Device (CPLD)?
\begin{verbatim}
--=============================
-- Listing 10.6
--=============================
architecture look_ahead_buffer_arch of mem_ctrl is
type mc_state_type is
(idle, read1, read2, read3, read4, write);
signal state_reg, state_next: mc_state_type;
signal oe_next,we_next,oe_buf_reg,we_buf_reg: std_logic;
begin
-- state register
process(clk,reset)
begin
if (reset='1') then
state_reg <= idle;
elsif (clk'event and clk='1') then
state_reg <= state_next;
end if;
end process;
-- output buffer
process(clk,reset)
begin
if (reset='1') then
oe_buf_reg <= '0';
we_buf_reg <= '0';
elsif (clk'event and clk='1') then
oe_buf_reg <= oe_next;
we_buf_reg <= we_next;
end if;
end process;
-- next-state logic
process(state_reg,mem,rw,burst)
begin
case state_reg is
when idle =>
if mem='1' then
if rw='1' then
state_next <= read1;
else
state_next <= write;
end if;
else
state_next <= idle;
end if;
when write =>
state_next <= idle;
when read1 =>
if (burst='1') then
state_next <= read2;
else
state_next <= idle;
end if;
when read2 =>
state_next <= read3;
when read3 =>
state_next <= read4;
when read4 =>
state_next <= idle;
end case;
end process;
-- look-ahead output logic
process(state_next)
begin
we_next <= '0'; -- default value
oe_next <= '0'; -- default value
case state_next is
when idle =>
when write =>
we_next <= '1';
when read1 =>
oe_next <= '1';
when read2 =>
oe_next <= '1';
when read3 =>
oe_next <= '1';
when read4 =>
oe_next <= '1';
end case;
end process;
-- output
we <= we_buf_reg;
oe <= oe_buf_reg;
end look_ahead_buffer_arch;
\end{verbatim}
\subsection{Rival data types for whole numbers}
Record your synthesis tool's reported area consumption for the
provided code for\\
\texttt{Direct\_Digital\_Frequency\_Synthesizer}. Replace the given
description with descriptions which use different datatypes and
record your synthesis tool's reported area consumption for each
alternative. The given version utilizes
\texttt{IEEE.numeric\_std.unsigned} and
\texttt{IEEE.numeric\_std.signed}.
You must write a version in which \texttt{IEEE.numeric\_std.unsigned}
and \texttt{IEEE.numeric\_std.signed} are replaced with
\texttt{integer range}.
You must write a version in which \texttt{IEEE.numeric\_std.unsigned}
and \texttt{IEEE.numeric\_std.signed} are replaced with
\texttt{integer} (as opposed to \texttt{integer range}).
You must write a version in which \texttt{amplitude\_type} is declared
as \begin{verbatim}subtype amplitude_type is std_logic_vector(5 downto
0);\end{verbatim}
At least one version requires the lexical VHDL format of the entries
in \texttt{sine\_wave} to be different. You are required to write a
program (in which ever language(s) you wish) to provide these values
in a legal format where the entries supplied in the given
\texttt{IEEE\_numeric\_std} architecture of \texttt{ROM} are rejected
by a VHDL analyzer.
Are the areas reported by your synthesis tool correlated with the
quantity of binary digits shown in a signal in your simulation tool's
waveform viewer?
\begin{verbatim}
library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;
package user_defined_types is
subtype address_type is unsigned(7 downto 0);
subtype amplitude_type is signed(5 downto 0);
subtype frequency_control_type is unsigned(7 downto 0);
end user_defined_types;
use work.user_defined_types.all;
entity ROM is
port (
address : in address_type;
data_out : out amplitude_type);
end ROM;
library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;
architecture IEEE_numeric_std of ROM is
type table is array(0 to 2**address_type'length -1) of
amplitude_type;
constant sine_wave : table := (
To_signed(arg=> 0, size=>amplitude_type'length),
To_signed(arg=> 1, size=>amplitude_type'length),
To_signed(arg=> 2, size=>amplitude_type'length),
To_signed(arg=> 2, size=>amplitude_type'length),
To_signed(arg=> 3, size=>amplitude_type'length),
To_signed(arg=> 4, size=>amplitude_type'length),
To_signed(arg=> 5, size=>amplitude_type'length),
To_signed(arg=> 5, size=>amplitude_type'length),
To_signed(arg=> 6, size=>amplitude_type'length),
To_signed(arg=> 7, size=>amplitude_type'length),
To_signed(arg=> 8, size=>amplitude_type'length),
To_signed(arg=> 9, size=>amplitude_type'length),
To_signed(arg=> 9, size=>amplitude_type'length),
To_signed(arg=> 10, size=>amplitude_type'length),
To_signed(arg=> 11, size=>amplitude_type'length),
To_signed(arg=> 12, size=>amplitude_type'length),
To_signed(arg=> 12, size=>amplitude_type'length),
To_signed(arg=> 13, size=>amplitude_type'length),
To_signed(arg=> 14, size=>amplitude_type'length),
To_signed(arg=> 14, size=>amplitude_type'length),
To_signed(arg=> 15, size=>amplitude_type'length),
To_signed(arg=> 16, size=>amplitude_type'length),
To_signed(arg=> 16, size=>amplitude_type'length),
To_signed(arg=> 17, size=>amplitude_type'length),
To_signed(arg=> 18, size=>amplitude_type'length),
To_signed(arg=> 18, size=>amplitude_type'length),
To_signed(arg=> 19, size=>amplitude_type'length),
To_signed(arg=> 20, size=>amplitude_type'length),
To_signed(arg=> 20, size=>amplitude_type'length),
To_signed(arg=> 21, size=>amplitude_type'length),
To_signed(arg=> 21, size=>amplitude_type'length),
To_signed(arg=> 22, size=>amplitude_type'length),
To_signed(arg=> 23, size=>amplitude_type'length),
To_signed(arg=> 23, size=>amplitude_type'length),
To_signed(arg=> 24, size=>amplitude_type'length),
To_signed(arg=> 24, size=>amplitude_type'length),
To_signed(arg=> 25, size=>amplitude_type'length),
To_signed(arg=> 25, size=>amplitude_type'length),
To_signed(arg=> 26, size=>amplitude_type'length),
To_signed(arg=> 26, size=>amplitude_type'length),
To_signed(arg=> 27, size=>amplitude_type'length),
To_signed(arg=> 27, size=>amplitude_type'length),
To_signed(arg=> 27, size=>amplitude_type'length),
To_signed(arg=> 28, size=>amplitude_type'length),
To_signed(arg=> 28, size=>amplitude_type'length),
To_signed(arg=> 29, size=>amplitude_type'length),
To_signed(arg=> 29, size=>amplitude_type'length),
To_signed(arg=> 29, size=>amplitude_type'length),
To_signed(arg=> 30, size=>amplitude_type'length),
To_signed(arg=> 30, size=>amplitude_type'length),
To_signed(arg=> 30, size=>amplitude_type'length),
To_signed(arg=> 30, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 31, size=>amplitude_type'length),
To_signed(arg=> 30, size=>amplitude_type'length),
To_signed(arg=> 30, size=>amplitude_type'length),
To_signed(arg=> 30, size=>amplitude_type'length),
To_signed(arg=> 30, size=>amplitude_type'length),
To_signed(arg=> 29, size=>amplitude_type'length),
To_signed(arg=> 29, size=>amplitude_type'length),
To_signed(arg=> 29, size=>amplitude_type'length),
To_signed(arg=> 28, size=>amplitude_type'length),
To_signed(arg=> 28, size=>amplitude_type'length),
To_signed(arg=> 27, size=>amplitude_type'length),
To_signed(arg=> 27, size=>amplitude_type'length),
To_signed(arg=> 27, size=>amplitude_type'length),
To_signed(arg=> 26, size=>amplitude_type'length),
To_signed(arg=> 26, size=>amplitude_type'length),
To_signed(arg=> 25, size=>amplitude_type'length),
To_signed(arg=> 25, size=>amplitude_type'length),
To_signed(arg=> 24, size=>amplitude_type'length),
To_signed(arg=> 24, size=>amplitude_type'length),
To_signed(arg=> 23, size=>amplitude_type'length),
To_signed(arg=> 23, size=>amplitude_type'length),
To_signed(arg=> 22, size=>amplitude_type'length),
To_signed(arg=> 21, size=>amplitude_type'length),
To_signed(arg=> 21, size=>amplitude_type'length),
To_signed(arg=> 20, size=>amplitude_type'length),
To_signed(arg=> 20, size=>amplitude_type'length),
To_signed(arg=> 19, size=>amplitude_type'length),
To_signed(arg=> 18, size=>amplitude_type'length),
To_signed(arg=> 18, size=>amplitude_type'length),
To_signed(arg=> 17, size=>amplitude_type'length),
To_signed(arg=> 16, size=>amplitude_type'length),
To_signed(arg=> 16, size=>amplitude_type'length),
To_signed(arg=> 15, size=>amplitude_type'length),
To_signed(arg=> 14, size=>amplitude_type'length),
To_signed(arg=> 14, size=>amplitude_type'length),
To_signed(arg=> 13, size=>amplitude_type'length),
To_signed(arg=> 12, size=>amplitude_type'length),
To_signed(arg=> 12, size=>amplitude_type'length),
To_signed(arg=> 11, size=>amplitude_type'length),
To_signed(arg=> 10, size=>amplitude_type'length),
To_signed(arg=> 9, size=>amplitude_type'length),
To_signed(arg=> 9, size=>amplitude_type'length),
To_signed(arg=> 8, size=>amplitude_type'length),
To_signed(arg=> 7, size=>amplitude_type'length),
To_signed(arg=> 6, size=>amplitude_type'length),
To_signed(arg=> 5, size=>amplitude_type'length),
To_signed(arg=> 5, size=>amplitude_type'length),
To_signed(arg=> 4, size=>amplitude_type'length),
To_signed(arg=> 3, size=>amplitude_type'length),
To_signed(arg=> 2, size=>amplitude_type'length),
To_signed(arg=> 2, size=>amplitude_type'length),
To_signed(arg=> 1, size=>amplitude_type'length),
To_signed(arg=> 0, size=>amplitude_type'length),
To_signed(arg=> -1, size=>amplitude_type'length),
To_signed(arg=> -2, size=>amplitude_type'length),
To_signed(arg=> -2, size=>amplitude_type'length),
To_signed(arg=> -3, size=>amplitude_type'length),
To_signed(arg=> -4, size=>amplitude_type'length),
To_signed(arg=> -5, size=>amplitude_type'length),
To_signed(arg=> -5, size=>amplitude_type'length),
To_signed(arg=> -6, size=>amplitude_type'length),
To_signed(arg=> -7, size=>amplitude_type'length),
To_signed(arg=> -8, size=>amplitude_type'length),
To_signed(arg=> -9, size=>amplitude_type'length),
To_signed(arg=> -9, size=>amplitude_type'length),
To_signed(arg=> -10, size=>amplitude_type'length),
To_signed(arg=> -11, size=>amplitude_type'length),
To_signed(arg=> -12, size=>amplitude_type'length),
To_signed(arg=> -12, size=>amplitude_type'length),
To_signed(arg=> -13, size=>amplitude_type'length),
To_signed(arg=> -14, size=>amplitude_type'length),
To_signed(arg=> -14, size=>amplitude_type'length),
To_signed(arg=> -15, size=>amplitude_type'length),
To_signed(arg=> -16, size=>amplitude_type'length),
To_signed(arg=> -16, size=>amplitude_type'length),
To_signed(arg=> -17, size=>amplitude_type'length),
To_signed(arg=> -18, size=>amplitude_type'length),
To_signed(arg=> -18, size=>amplitude_type'length),
To_signed(arg=> -19, size=>amplitude_type'length),
To_signed(arg=> -20, size=>amplitude_type'length),
To_signed(arg=> -20, size=>amplitude_type'length),
To_signed(arg=> -21, size=>amplitude_type'length),
To_signed(arg=> -21, size=>amplitude_type'length),
To_signed(arg=> -22, size=>amplitude_type'length),
To_signed(arg=> -23, size=>amplitude_type'length),
To_signed(arg=> -23, size=>amplitude_type'length),
To_signed(arg=> -24, size=>amplitude_type'length),
To_signed(arg=> -24, size=>amplitude_type'length),
To_signed(arg=> -25, size=>amplitude_type'length),
To_signed(arg=> -25, size=>amplitude_type'length),
To_signed(arg=> -26, size=>amplitude_type'length),
To_signed(arg=> -26, size=>amplitude_type'length),
To_signed(arg=> -27, size=>amplitude_type'length),
To_signed(arg=> -27, size=>amplitude_type'length),
To_signed(arg=> -27, size=>amplitude_type'length),
To_signed(arg=> -28, size=>amplitude_type'length),
To_signed(arg=> -28, size=>amplitude_type'length),
To_signed(arg=> -29, size=>amplitude_type'length),
To_signed(arg=> -29, size=>amplitude_type'length),
To_signed(arg=> -29, size=>amplitude_type'length),
To_signed(arg=> -30, size=>amplitude_type'length),
To_signed(arg=> -30, size=>amplitude_type'length),
To_signed(arg=> -30, size=>amplitude_type'length),
To_signed(arg=> -30, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -32, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -31, size=>amplitude_type'length),
To_signed(arg=> -30, size=>amplitude_type'length),
To_signed(arg=> -30, size=>amplitude_type'length),
To_signed(arg=> -30, size=>amplitude_type'length),
To_signed(arg=> -30, size=>amplitude_type'length),
To_signed(arg=> -29, size=>amplitude_type'length),
To_signed(arg=> -29, size=>amplitude_type'length),
To_signed(arg=> -29, size=>amplitude_type'length),
To_signed(arg=> -28, size=>amplitude_type'length),
To_signed(arg=> -28, size=>amplitude_type'length),
To_signed(arg=> -27, size=>amplitude_type'length),
To_signed(arg=> -27, size=>amplitude_type'length),
To_signed(arg=> -27, size=>amplitude_type'length),
To_signed(arg=> -26, size=>amplitude_type'length),
To_signed(arg=> -26, size=>amplitude_type'length),
To_signed(arg=> -25, size=>amplitude_type'length),
To_signed(arg=> -25, size=>amplitude_type'length),
To_signed(arg=> -24, size=>amplitude_type'length),
To_signed(arg=> -24, size=>amplitude_type'length),
To_signed(arg=> -23, size=>amplitude_type'length),
To_signed(arg=> -23, size=>amplitude_type'length),
To_signed(arg=> -22, size=>amplitude_type'length),
To_signed(arg=> -21, size=>amplitude_type'length),
To_signed(arg=> -21, size=>amplitude_type'length),
To_signed(arg=> -20, size=>amplitude_type'length),
To_signed(arg=> -20, size=>amplitude_type'length),
To_signed(arg=> -19, size=>amplitude_type'length),
To_signed(arg=> -18, size=>amplitude_type'length),
To_signed(arg=> -18, size=>amplitude_type'length),
To_signed(arg=> -17, size=>amplitude_type'length),
To_signed(arg=> -16, size=>amplitude_type'length),
To_signed(arg=> -16, size=>amplitude_type'length),
To_signed(arg=> -15, size=>amplitude_type'length),
To_signed(arg=> -14, size=>amplitude_type'length),
To_signed(arg=> -14, size=>amplitude_type'length),
To_signed(arg=> -13, size=>amplitude_type'length),
To_signed(arg=> -12, size=>amplitude_type'length),
To_signed(arg=> -12, size=>amplitude_type'length),
To_signed(arg=> -11, size=>amplitude_type'length),
To_signed(arg=> -10, size=>amplitude_type'length),
To_signed(arg=> -9, size=>amplitude_type'length),
To_signed(arg=> -9, size=>amplitude_type'length),
To_signed(arg=> -8, size=>amplitude_type'length),
To_signed(arg=> -7, size=>amplitude_type'length),
To_signed(arg=> -6, size=>amplitude_type'length),
To_signed(arg=> -5, size=>amplitude_type'length),
To_signed(arg=> -5, size=>amplitude_type'length),
To_signed(arg=> -4, size=>amplitude_type'length),
To_signed(arg=> -3, size=>amplitude_type'length),
To_signed(arg=> -2, size=>amplitude_type'length),
To_signed(arg=> -2, size=>amplitude_type'length),
To_signed(arg=> -1, size=>amplitude_type'length)
);
begin
data_out<=sine_wave(to_integer(address));
end IEEE_numeric_std;
library IEEE;
use IEEE.std_logic_1164.all;
use work.user_defined_types.all;
entity Direct_Digital_Frequency_Synthesizer is
port (
frequency_control_word : in frequency_control_type;
amplitude : out amplitude_type;
clock : in std_logic;
reset : in std_logic
);
end Direct_Digital_Frequency_Synthesizer;
library IEEE;
use IEEE.numeric_std.all;
architecture IEEE_numeric_std of Direct_Digital_Frequency_Synthesizer
is
component ROM
port (
address : in address_type;
data_out : out amplitude_type);
end component;
signal horizontal_projection_of_the_point_on_the_locus :
address_type := (others=>'0');
signal slow_down : frequency_control_type := (others=>'0');
begin
look_up_table : ROM port map (
address => horizontal_projection_of_the_point_on_the_locus,
data_out => amplitude);
main : process(reset,clock)
begin
if reset = '1' then
horizontal_projection_of_the_point_on_the_locus <=
(others=>'0');
elsif rising_edge(clock) then
if slow_down = 0 then
horizontal_projection_of_the_point_on_the_locus <=
to_unsigned(arg=>1,
size=>horizontal_projection_of_the_point_on_the_locus'length) +
horizontal_projection_of_the_point_on_the_locus;
if 2**address_type'length-1 = to_integer(
horizontal_projection_of_the_point_on_the_locus) then
horizontal_projection_of_the_point_on_the_locus <=
(others=>'0');
end if;
slow_down <= frequency_control_word;
else
slow_down <= slow_down -1;
end if;
end if;
end process;
end IEEE_numeric_std;
\end{verbatim}
\section{A nuisance for a synthesis tool}
The following legal \texttt{if} statement is rejected by a synthesis
tool, but a trivial rearrangement amenable to being mechanically
applied by an automaton results in functionally equivalent code which
is accepted by the synthesis tool. Manually rearrange the code --- -->
--without changing its functionality--
----- to make it accepted by a
synthesis tool.
\begin{verbatim}
if reset = '1' then
null; --Some statement here.
elsif rising_edge(clock) and some_signal = '0' then
null; --Some statement here.
elsif rising_edge(clock) then
null; --Some statement here.
end if;
\end{verbatim}
\section{Bounce}
A signal from a button is subject to an unclean transition from the
unpressed state to the pressed state. This can be counteracted
(debounced) by sampling a second time with a long enough delay after
an initial possible detection so as to not check the status when it
has not stabilized. Experiment with a button and various
delays. E.g. is one millisecond too fast? Is half a second too slow?
\section{Linear Time Invariant system}
Write a Finite Impulse Response (F.I.R.) filter whose impulse response
is [1 0 0 1 0 2].
\section{Lossy image compression}
Take a Fourier transform and inverse fourier transform I.P. core
(e.g. from\\
\texttt{
WWW.Xilinx.com/ipcenter/catalog/logicore/docs/xfft.pdf}) and
compare the running time for compressing a copy of the Lenna image
with acceptable levels of degradation on an F.P.G.A. with the time
taken for the equivalent compression in MATLAB.
\section{Concurrency}
\subsection{Sorting}
Implement on a field programmable gate array, VHDL code which sorts
words into alphabetical order (the words to be sorted contain only
letters). You may hardcode the words to be sorted as a randomized list
in an array in your source code or you may accept the words as input
from a port delimited any way you choose. The sorting is not to be
performed into a single big list, but rather into many lists: each of
any one list's entries must begin with the same letter as any other
member of that list. Each letter of the alphabet you use (you may
restrict your code to ASCII letters or Italian letters or German
letters or another alphabet if you wish) should have only list whose
entries begin with that letter. Empirically report whether a version
of your code with just one sorting process runs at a very different
speed than a version of your code with (at least) one sorting process
per letter of the alphabet. Is the FPGA's timing relationship between
the one-process and the many-process versions reflected in the running
times of their simulations? Write multitasking software (in a language
of your choice with multitasking support of your choice (in the
language or in a library)) which performs the same sorting
algorithm. Which is fastest (if possible, time your software version
on a multiprocessor as well as a uniprocessor)?
\subsection{Jacobi's method and Gauss-Seidel method}
Implement these indirect methods for linear systems on a field
programmable gate array. For the same matrices, which tends to
converge sooner? Is the FPGA's timing relationship between the
inherently sequiential (i.e. Jacobi's) and the parallel
(i.e. Gauss-Seidel) versions reflected in the running times of their
simulations? Write multitasking software (in a language of your choice
with multitasking support of your choice (in the language or in a
library)) which implements the same methods. Which is fastest (if
possible, time your software version on a multiprocessor as well as a
uniprocessor)?
\section{Regular expressions}
Write a state machine whose accepted language is defined by
\begin{enumerate}
\item '0'$^{+}$
\item '1'$^{*}$'0'$^{+}$['1'$|$'0']$^{*}$
\item '1'
\end{enumerate}
\section{Computations which are used in three dimensional computer
graphics}
A four dimensional homogeneous matrix is formed by starting with a
three dimensional matrix and appending the vector
\begin{displaymath}\left[\begin{array}{c c c c} 0 &0 &0& 1
\end{array}\right] \end{displaymath} as the fourth row and appending
the vector \begin{displaymath}\left[\begin{array}{c} 0 \\
0\\
0\\
1 \end{array}\right] \end{displaymath} as the fourth column. I.e. a
3D matrix
\begin{displaymath}\left[\begin{array}{c c c} a_{11} &a_{12}
&a_{13}\\
a_{21} &a_{22} &a_{23}\\
a_{31} &a_{32} &a_{33}
\end{array}\right] \end{displaymath}
is replaced by the 4D matrix
\begin{displaymath}\left[\begin{array}{c c c c} a_{11} &a_{12}
&a_{13} &0\\
a_{21} &a_{22} &a_{23} &0\\
a_{31} &a_{32} &a_{33} &0\\
0 &0 &0& 1
\end{array}\right] \end{displaymath}
This removes translation in Cartesian geometry as a special case, as
it can now be performed by multiplying matrices, just as rotation and
magnification could already be done. This makes it trivial to have a
single transformation matrix which simultaneously holds numbers for
translations; rotations; and scaling to all be performed before the
next image buffer is displayed to the user.
Though your F.P.G.A. might not be connected to a visual display unit,
it can perform the same calculations needed for updating
graphics. This has led to the invention of ``Graphical Processing
Units'' (G.P.U.s). Write VHDL code which performs multiplications on
two three dimensional shapes (a cube and a very simple house (a cuboid
attached to a pyramid)) using four dimensional homogeneous
matrices. (G.P.U.s and/or software in commercial games may optimize
their data structures by taking advantage of the wastefullness of
storing the constant fourth row and fourth column of a 4D homogeneous
matrix, but you are not required to make such an improvement for this
exercise.)
\section{\arabic{section}}
Your F.P.G.A. is connected to a digital imaging device which provides
a 10bit grayscale image after a signal is asserted low for 200 ns. The
image is provided one entire pixel at a time in a single clock
tick. The image is provided in a row by row manner. An image consists
of 1024 rows and 1024 columns. The pixel value consisting of all ones
can be received from the camera but is an illegal value for your
customer's use so if it appears it must be replaced by the next
highest value. An output signal indicates whether or not an image is
being received by the F.P.G.A. Another output signal indicates whether
or not all processing for a currently held image is finished. A very
simple checksum is calculated as the summation of every number on the
main diagonal (however, none of the code to provide the image from the
F.P.G.A. to an external sink is required for this exercise). The
checksum must be continously output to a port. When the checksum has
not been fully computed, the checksum's output port must contain all
ones. An imput signal from the user may be used to abort any operation
at any time, in which case the checksum is considered to be not fully
computed.
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
