Rästitehtävät

Rästikierroksella voit korvata minkä tahansa kierroksista 0-2, joista sinulla on joko bumerangi tai palauttamaton työ. Rästitehtävillä et voi korottaa jo annettua arvosanaa tai muulla tavalla ansaita lisäpisteitä. Rästillä suoritetusta tehtävästä voi saada maksimissaan kunkin kierroksen kohdalla läpipääsyyn vaaditut minimipisteet.

Kierroksille 3-6 ei tarjota korvaavia tehtäviä, mutta voit edelleen palauttaa näitä tehtäviä rästitehtävän DL:ään mennessä. Käytännössä pistemäärä näin reilusti myöhästyneestä töistä on melko lähellä nollaa, mikäli työ on suoritettu riittävän laajuisena. Lauantain 11.1.2014 jälkeen palautettuja töitä ei arvostella.

Kaikille muille kuin kierroksen 6 töille on yhteinen palautuslaatikko Rubyricissä.

Tehtävänannot

Kierroksen 0. korvaava tehtävä - Tieto tietokoneessa

Osa 1 - Liittimet

Tehtävänäsi on tunnistaa yllä olevaan kuvaan merkityt liittimet (yhteensä 13). Kerro mitä numeroidut liittimet ovat ja mainitse jokaisen liittimen yhteydessä myös:

Osa 2 - Muisti

Selitä lyhyesti, mutta täsmällisesti, kuinka tietokoneen muisti toimii ja millaisia erilaisia osia siinä on. Miten tietokoneen muistissa oleva data on säilötty tietokoneen käyttöön? Muista käyttää asiallista lähdeviittaustekniikkaa, myös mahdollisten kuvien kohdalla.

Osa 3 - Oma oppiminen

Arvioi kuinka hyvin nyt ymmärrät miten tietokoneeseen voidaan syöttää dataa ja miten tietokoneen muistissa olevaa dataa voidaan käyttää. Millainen käsitys sinulla on tietokoneen sisältämän datan esitysmuodosta?

Pisteytys

Läpi kun kaikki osat on käsitelty riittävällä laajuudella. Pienet puutteet on sallittuja, mutta opiskelijalle tulisi muodostua käsitys sekä siitä, miten 1) tieto saadaan kulkemaan tietokoneen ja muiden laitteiden välillä että siitä, 2) kuinka tätä tietoa voidaan käyttää ja tallentaa tietokoneen muistiin. Vastauksen tulisi olla selkeä osoitus tästä ymmärryksestä. Palautuksessa vastaus .pdf-muodossa.

Kierroksen 1. korvaava tehtävä - Luokat ja oliot (UML)

Osa 1 - Kaavion piirtäminen

Laadi UML-kaavio Scalan Swing-pakkauksesta (http://www.scala-lang.org/api/current/index.html#scala.swing.package). Mutta älä missään nimessä piirrä pakkauksen rakennetta kokonaisuudessaan! Valitse kaavioosi vain tärkeimpiä komponentteja sekä muutama tärkeä piirreluokka. Valitse kuvailtavaksi sellaisia luokkia, jotta pääset mahdollisimman monipuolisesti harjoittelemaan UML-notaatiota (noin viisi elementtiä tulisi riittää). Kirjaa elementeille myös ominaisuuksia.

Työkalut piirtämiseen saat valita itse! Mieluiten ei käsin, mutta riittävän korkealaatuinen skannaus, jossa jäsentely on selkeää, on hyväksyttävä.

Osa 2 - UML-kaavioiden käyttö

Laadi lyhyt esseevastus (n. 700 sanaa), jossa käsitellään seuraavat asiat:

Huomaa, että vastuksesi on oltava järkevästi jäsennelty ja noudatettava asianmukaista viittaustekniikkaa. Apua voi katsoa esseeohjeesta

Pisteytys

Tehtävässä tärkeää on osoittaa ymmärrys UML:n käyttötarkoituksesta niin teoriassa kuin hiukan käytännössäkin. Piirtäminen on tässä vähemmällä fokuksella, mutta tuotetun kaavio on vastattava todellisuutta Swing-pakkauksesta. Hyvän kaavion avulla on myös helpompi esitellä notaatiota.

Tehtävä on läpi, kun molemmat osat on käsitelty riittävällä laajuudella. Jälleen pienet puutteet on sallittuja kunhan osaaminen osoitetaan. Pyri yhtenäiseen ja selkeään vastaukseen. Palautuksessa piirretty kaavio mukaan .png:nä ja teksti .pdf-muodossa.

Kierroksen 2. korvaava tehtävä - Hamming-koodaus

Tässä tehtävässä on tarkoituksena tehdä Hamming (7, 4) koodi, jonka avulla voidaan datasta havaita yhden bitin virhe ja korjata se. Hamming koodauksessa dataan lisätään melko vähän redundanssia ja siksi vain pieni määrä virheitä on mahdollista havaita. Tällainen koodi on hyödyllinen kun virheitä sattuu vain harvoin, esimerkiksi tietokoneen muistissa.

Osa 1 - Virheenkorjaava koodi

Hamming koodauksessa alkuperäinen data muutetaan sellaiseen muotoon, missä pariteettibitit, eli ne bitit, joiden sijainti datajoukon alusta numeroituna on jokin 2:n potenssi, ilmaisevat kattamansa alueen päällä olevien bittien (tai ykkösten) parillisuuden ja loput bitit ovat alkuperäisiä databittejä. Toisin sanoen bitit 1, 2, 4, 8, 16, 32, jne. ovat pariteettibittejä ja muut bitit databittejä. Kunkin pariteettibitin kattama alue on esitettynä alla olevassa taulukossa:

Bitin sijainti12345678910
Koodattu datap1p2d1p3d2d3d4p4d5d6
p1X X X X X
p2 XX XX X
p3 XXXX
p4 XXX

Jos esimerkiksi alkuperäinen data on "01101" on se Hamming koodattuna "010011011", missä sinisellä merkityt bitit on pariteettibittejä.

Koodauksen kannalta on siis oleellista tunnistaa, mitkä bitit ovat pariteettibittejä ja onko päällä olevia bittejä parillinen vai pariton määrä pariteettibitin kattavalla alueella.

Luo siis olio Hamming, jolla on seuraavat metodit:

/**
 * Encodes the given data with Hamming(7, 4) code.
 * 
 * @param data    data to be encoded with Hamming code
 * @return        the encoded data, containing the data bits and parity bits
 */
def encode(data:Buffer[Boolean]) : Buffer[Boolean] = {
  // your code
}
  
/**
 * Correction at most one bit errors. 
 * 
 * @param data    corrupted Hamming encoded data
 * @return        corrected Hamming encoded data
 */
def correctError(data:Buffer[Boolean]) : Buffer[Boolean] = {
  // your code
}
    
/**
 * Decodes Hamming encoded data set e.g. removes the parity bits.
 * 
 * @param data    encoded data
 * @return        decoded data
 */
def decode(data:Buffer[Boolean]) : Buffer[Boolean] = {
  // your code
}
  
/**
 * Checks if the integer given as parameter is power of two.
 * 
 * @param num     the number to be checked to be the power of two
 * @return        true when num is power of two otherwise false
 */
private def isPowerOfTwo(num:Int) : Boolean = {
  // your code
}

Huomioi, että tässä tarkoituksena on palauttaa aina enkoodauksen, virheen korjauksen ja dekoodauksen jälkeen uusi datan sisältävä Buffer-olio ja ehdottomasti jättää alkuperäinen data koskemattomaksi. Lisäksi listauksen viimeinen metodi kannattaa toteuttaa ensimmäisenä, sillä sitä on tarkoitus käyttää muiden metodien toteutuksessa apuna. Vastaavaa metodia käytettiin kierroksella 3 ja jos olet toteuttanut sen siellä (oikein), voit vapaasti käyttää tätä toteutusta tässäkin.

Helpoin tapa toteuttaa encode-metodi on ensin luoda uusi Buffer-olio, johon sijoitetaan aina pariteettibitin tullessa vastaan systemaattisesti joko true tai false oman harkintasi mukaan. Databittien kohdalle kopioidaan alkuperäisestä Buffer-oliosta seuraava bitti sellaisenaan. Tässä apuna kannattaa käyttää Buffer:ista generoitua iteraattoria, jolloin seuraavan databitin voi pyytää ainoastaan tarvittaessa ja uutta dataa on helppo rakentaa while-silmukan avulla. Kun uusi oikean mittainen Buffer on luotu, voidaan siirtyä laskemaan pariteettibittien arvoja. Tarpeettomien bittien huomiotta jättäminen muodostunee tässä hankalimmaksi kohdaksi, mutta siitä on helppo selvitä muutaman apumuuttujan avulla.

Hamming koodatussa datassa virheen havaitseminen on erittäin helppoa. Pariteettibittien paikkansapitävyys tarkistetaan, virheellisten sijainti otetaan talteen, sijainnin indeksit lasketaan yhteen, jolloin saadaan paikannettua virheellisen bitin sijainti. Aiheesta on hyvä demo eräässä YouTube-videossa: http://www.youtube.com/watch?v=osS9EaKNSI4

Tämän tehtävän puitteissa voit olettaa, että virheitä tulee aina täsmälleen yksi. Jolloin kun olet löytänyt kaikki pariteetteihin täsmäämättömät bitit ja ottanut ne talteen. Voit vain kopioida alkuperäisen datan uuteen Buffer-olioon ja kääntää vaurioituneen bitin.

decode-metodissa palautetaan data niin, että siitä on välistä poistettu pariteettibitit. Tämä kannattaa toteuttaa käymällä läpi metodille annettu data ja mikäli kyseessä on databitti lisätään se palautettavaan Buffer-olioon ja pariteettibitin kohdalla jätetään se huomiotta.

Osa 2 - Virheiden simulointi ja niistä selviäminen

Tehdyn koodauksen testaamista varten luomme objektin NoiseSimulator, joka perii App-piirreluokan. Objektilla on kolme yksityistä metodia ja yksi julkinen metodi, jotka on kuvailtu alla:

/**
 * Adds one error to the original Boolean buffer preserving other bits unchanged.
 * 
 * @param data    data to where an error is added e.g. one bit is flipped
 * @return        original data with one error
 */
private def addError(data:Buffer[Boolean]) : Buffer[Boolean] = {
  // your code
}
  
/**
 * Translates given Boolean buffer to String replacing trues with ones and falses with zeros.
 * 
 * @param data    data buffer to be translated to String
 * @return        String containing trues as ones and falses as zeros
 */
private def bufferToString(data:Buffer[Boolean]) : String = {
  // your code
}
  
/**
 * Generates and returns data in Buffer format containing Boolean values that are generated
 * randomly.
 * 
 * @param len     the length of data buffer to be generated
 * @return        data buffer of length len
 */
private def generateData(len:Int) : Buffer[Boolean] = {
  // your code
}
  
/**
 * Loops laps times generating data of length dataLen, encoding the
 * generated data, adding an error to it, correcting and finally decoding it.
 * 
 * The method should produce an output like this:
 * 
 * original | encoded | defected | corrected | decoded | matches the original
 *     0101 | 0100101 |  0101101 |   0100101 |    0101 | true
 *     0100 | 1001100 |  1011100 |   1001100 |    0100 | true
 *     1110 | 0010110 |  1010110 |   0010110 |    1110 | true
 *     
 * when laps is three and dataLen is four.
 * 
 * @param laps       indicates how many times test loop should be run for specified data length
 * @param dataLen    indicates the length of tested data set 
 */
def simulate(laps:Int, dataLen:Int) : Unit = {
  // your code
}

addError-metodi lisää yhden bittivirheen sille parametrina annettuun Buffer-olioon sisältämään dataan. Käytä metodin toteutuksessa apunasi Random-luokkaa. Huomaa, että tässäkin metodissa tarkoituksena on jättää alkuperäinen data koskemattomaksi ja palauttaa uusi Buffer-olio.

bufferToString-metodi palauttaa sille parametrina annetun Buffer-olion merkkijonokuvauksen. Saadessaan siis parametrikseen puskurin, jonka sisältö on (false, true, false, false, true) palauttaa metodi merkkijonon "01001".

generateData-metodi palauttaa satunnaisesti generoidun (jälleen Random-luokasta on apua) parametrin määrittelemän mittaisen datapuskurin.

simulate-metodin avulla varsinaisesti testataan aiemmin toteutetun Hamming koodauksen toimivuus. Yksi metodin ajokerta toteuttaa ensimmäisen parametrin määrän toistoja datalla, jonka pituus määritellään toisella parametrilla. Metodin suorituksen alussa testikierrokselle printataan muotoiltu otsikkorivi. Jokaisella metodin sisäisen silmukkarakenteen kierroksella generoidaan tarvitun mittainen datapätkä, enkoodataan se, aiheutetaan siihen virhe, korjataan virhe ja dekoodataan. Jokainen kohta tulostetaan yhdelle riville, missä viimeisimpänä kohtana on vielä tulostettuna true tai false riippuen siitä, vastaako alkuperäinen data lopputulosta. Kiinnitä huomiota tulosteen muotoiluun käyttämällä Consolen printf-metodia. Suorittamalla seuraavan pätkän koodia:

simulate(3, 4)
println()
simulate(3, 5)
println()
simulate(3, 6)
println()
simulate(3, 10)

voitaisiin tuottaa seuraava tuloste:

 original |   encoded |  defected | corrected | matches the original
     1101 |   1010101 |   1000101 |   1010101 | 1101
     0000 |   0000000 |   0001000 |   0000000 | 0000
     1110 |   0010110 |   0011110 |   0010110 | 1110

 original |   encoded |  defected | corrected | matches the original
    01010 | 010010100 | 010011100 | 010010100 | 01010
    01011 | 110010111 | 111010111 | 110010111 | 01011
    10110 | 011001100 | 011000100 | 011001100 | 10110

  original |    encoded |   defected |  corrected | matches the original
    001001 | 0001010101 | 0101010101 | 0001010101 | 001001
    101000 | 1011010000 | 1011010010 | 1011010000 | 101000
    101001 | 1111010101 | 1111011101 | 1111010101 | 101001

      original |        encoded |       defected |      corrected | matches the original
    0100001011 | 10011001001011 | 10011101001011 | 10011001001011 | 0100001011
    0100001001 | 00001000001001 | 00000000001001 | 00001000001001 | 0100001001
    1010101001 | 10100101101001 | 10110101101001 | 10100101101001 | 1010101001

Pisteytys

Riittävässä suorituksessa vähintään Hamming koodaus toimii asianmukaisesti, ja koodatun datan virheistä selviämistä on analysoitu. Tuotetun koodin tulee olla hyvin kommentoitua ja jäsennelty selkeästi. Pakkaa koodisi (.scala-tiedostot) paketiksi (.zip tai .jar) ja liitä se lopulliseen pakettiisi. Pakkaa koko ratkaisusi niin, että tarkastajan ei tarvitse ladata mitään muuta lisäksi ohjelman toimimiseksi. Laita siis palautettavaan pakettiin kaikki tekemäsi koodi, sekä käyttämäsi kuva- ja tekstitiedostot.

Lopuksi (HUOM! kaikille yhteinen)

Oikolue tekemäsi kirjalliset työt ja varmista, että niissä on käsitelty kaikki tarvittava ja käytetty viittaustekniikkaa oikein. Testaa vielä lopuksi kaikkien tekemiesi luokkien toiminta ja varmista, että kaikki toimii toivomallasi tavalla. Viimeistään tässä vaiheessa kommentoi koodisi ne pätkät, jotka saattavat olla vaikeaselkoisia. Tämän lisäksi lisää vielä pakettiisi readme.txt täytettynä, jonka pohjan voit kopioida alta.

# ME-C2120 Syksy 2013
#
# Rästikierros

Opiskelijanumero:
Tehtävään 0 käytetty aika tunteina (arvio):
Tehtävään 1 käytetty aika tunteina (arvio):
Tehtävään 2 käytetty aika tunteina (arvio):

# Mitkä kierroksen osiot toteutit merkitse ne sanalla 'tehty'.
# Voit merkitä myös tekemäsi, mutta toteuttamatta jääneet kohdat sanalla 'yritetty'.

O0 Tieto tietokoneessa                                   ei ole tehty
    Osa 1 - Liittimet                                    ei ole tehty
    Osa 2 - Muisti                                       ei ole tehty
    Osa 3 - Oma oppiminen                                ei ole tehty
O1 Luokat ja oliot                                       ei ole tehty
    Osa 1 - Kaavion piirtäminen                          ei ole tehty
    Osa 2 - UML-kaavion käyttö                           ei ole tehty
O2 Hamming-koodaus                                       ei ole tehty
    Osa 1 - Virheenkorjaava koodi                        ei ole tehty
    Osa 2 - Virheiden simulointi ja niistä selviäminen   ei ole tehty

# Teitkö annettuja bonustehtäviä tai jotain muita lisäominaisuuksia?
(Kerro mitä teit ja lisää mahdolliset käyttöohjeet, mikäli toiminnallisuus
poikkeaa suuresti vaaditusta kokoelmasta.)

# Jäikö tehtäviisi puutteita?
(Listaa kaikki tuntemasi ongelmasi. Mainitse, jos mahdollista, omat arviosi
näiden syyksi ja kuinka olet yrittänyt korjata ne.)

# Vapaat tehtävään liittyvät kommentit?
(Voit vapaasti kommentoida tehtävää.)

Palautus

Tehtävän palautus tehdään aikarajaan lauantaihin 11.01.2014 klo 18.00 mennessä Rubyric-järjestelmään. Aikaraja on ehdoton, ja lauantain 11.1.2014 jälkeen palautettuja töitä ei arvostella.

Pidä huolta, että tehtäväsi on palautettu oikeassa muodossa. Tekstin osalta .pdf, kuvien osalta .png ja koodin osalta .scala-tiedostot. Kannattaa kiinnittää huomiota myös koodin ja sisennyksen selkeyteen; jos koodista näkee selkeästi ajatuksenkulkusi, helpottaa se koodin toimivuuden ja vikatilanteiden vakavuuden arviointia. Kannattaa myös varmistaa, että palautettava koodi kääntyy ja että kyseessä on viimeisin versio toteutuksestasi. Pakkaa kaikki palauttamasi tiedostot samaan .zip-pakettiin, jossa jokainen tehtävä löytyy omasta kansiostaan nimettynä kierroksen ja opiskelijanumerosi mukaan. Nimeä palautuksesi muotoon "opnro.zip".

Arvostelu

Koska kyseessä on rästitehtävä, voi siitä saada korkeintaan alkuperäisten pisteiden minimipistemäärän. Eli kierroksen 0 osalta 10 pistettä, kierroksen 1 osalta 10 pistettä ja kierroksen 2 osalta 30 pistettä. Käytännössä tehtävä on joko hyväksytty tai vaatii täydennystä. Jos tehtäväpalautus on selvästi hyvin keskeneräinen, se voidaan palauttaa tekijälleen korjattavaksi (ns. bumerangi). Tehtävä on hyväksytty vasta, kun se on palautettu riittävän laajuisena ja syvällisenä.

Kunkin tehtävän osalta yksityiskohtaisemmat suoritusvaatimukset on esitelty tehtävien yhteydessä.