Virheiden havaitseminen ja korjaaminen koodausteorian avulla

Miikka Venäläinen

Published Jan 1, 2023• 0 citations

Abstract

Matematiikan ja tilastotieteen tutkinto-ohjelma Marraskuu 2023 Tässä tutkielmassa lähestytään koodausteoriaa matriisilaskennan kautta.Koodausteoria tutkii viestien koodaamista siten, että lähetyksen aikaiset kohinan aiheuttamat muutokset voitaisiin havaita ja korjata virheenkorjauskoodin avulla.Kohinasta aiheutuvaa koodisanan muutosta kutsutaan virheeksi.Virheenkorjauskoodin tärkeimmät käsitteet ja tulokset määritellään tutkielman toisessa luvussa.Kolmannessa ja neljännessa luvussa keskitytään ryhmäkoodin määrittelyyn ja Hamming-koodin muodostamiseen.Luvussa 2 esitellään nimitys 𝑛-bittĳono sellaisille bittĳonoille, joiden pituus on 𝑛.Lukĳalle tulee myös tutuksi koodaus-ja purkufunktioiden määritelmät.Tämän jälkeen määritellään Hamming-etäisyys, joka on funktio, ja myös metriikka, joka kertoo kahden 𝑛-bittĳonon toisistaan eroavien bittien lukumäärän.Hammingetäisyyden avulla määritellään koodin minimietäisyys, joka on minimi koodisanojen Hamming-etäisyyksien joukosta.Minimietäisyys on virheenkorjauskoodin tärkeä ominaisuus, sillä se määrittää voiko kohinasta aiheutuvaa virhettä havaita tai korjata.Aivan luvun lopussa osoitetaankin yhteys koodin minimietäisyyden ja purkumenetelmän virheentunnistus-ja virheenkorjauskyvyn välillä.Tulokseksi saadaan, että minimietäisyyden ollessa vähintään kolme, purkumenetelmä voi korjata yhden virheen tai havaita yhden ja kahden bitin virheet.Luvun 3 pääpaino on ryhmäkoodeissa ja niiden ominaisuuksissa.Ryhmäkoodit ovat erityislaatuisia koodeja, joiden kahden koodisanan summa on edelleen koodisana.Luvun ensimmäisessä alaluvussa määritellään bittien yhteenlaskutoimitus ja paino, ja osoitetaan painon ja Hamming-etäisyyden välinen yhteys.Toinen alaluku pitää sisällään vektori-ja matriisilaskentaa, joiden tulosten avulla osoitetaan, että ryhmäkoodeja voidaan tuottaa virittäjämatriiseilla, joka on nopea tapa luoda virheenkorjauskoodi.Yksi tällainen virittäjämatriisi on luvun lopussa määritelty kanoninen

Related papers

Kvanttilaskenta ja koherenssi resurssina

Niko-Pekka Sainio

Kvanttilaskennan eräs ongelma on kvanttisysteemien herkkyys ulkopuolisille vaikutuksille, eli dekoherenssille. Tämä tekee systeemin koherenssista resurssin, jota voidaan käyttää suorittamaan haluttuja toimintoja. Tutkielma alkaa johdannolla lineaarialgebraan ja kvanttimekaniikan perusteisiin, jotta kvanttilaskentaa voidaan mallintaa. Tätä seuraava osuus käsittelee kvanttilaskentaa ja alkaa esittelemällä kubitit, korostaen näiden ja klassisten bittien eroavaisuuksia. Lisäksi esitellään intuitiivinen tapa ajatella yksittäisiä kubitteja, Blochin pallo. Osio jatkuu esittelemällä kvanttiportit jälleen korostaen näiden eroavaisuuksia klassisisiin portteihin. Tämän jälkeen käsitellään kvanttilaskennan erittäin oleellinen eroavaisuus klassisen laskennan välillä, nimittäin mittaus, joka muuttaa alla olevan kvanttisysteemin tilaa ja täten vaikuttaa kvanttilaskennan tulokseen, mikäli mittaus tehdään kesken laskennan. Osuus päätetään esittelemällä yleisesti käytetty tapa mallintaa kvanttilaskentaa, kvanttipiirit. Kolmannessa osiossa kehitellään kvanttilaskennalle universaalien kvanttiporttien käsite. Tarkastelu aloitetaan kaksitasoisilla matriiseilla, jotka myöhemmin samaistetaan kvanttiportteihin. Osiossa myös kehitellään Blochin pallosta intuitiota kvanttiportteja vastaaviin kiertoihin. Tämän jälkeen esitetään tapa luoda mikä tahansa yhden kubitin portti kahdella kierrolla. Seuraavaksi osoitetaan, että tällaisella porttijoukolla ja kontrolloidulla NOT-portilla voidaan luoda mikä tahansa kvanttiportti. Lopuksi muodostetaan universaali porttijoukko. Lopuksi käydään koherenssin resurssiteoriaa. Ensiksi käydään vaaditut valmistelut kvanttioperaattoreista ja kvanttisysteemin entropiasta, jota varten esitellään von Neumannin entropia. Tämän jälkeen erotellaan kvanttisysteemin epäkoherentit tilat ja operaatiot koherenteista tiloista ja operaatioista sekä osoitetaan, että epäkoherenteilla operaatioilla ja yhdellä maksimaalisesti koherentilla kubitilla voidaan luoda mikä tahansa kvanttiportti. Lopuksi todistetaan, että systeemin tiheysmatriisin ja tiheysmatriisin diagonaalin välinen suhteellinen entropia on koherenssimitta.

Jan 1, 20240 citations

Kvanttisalaus : Turvaprotokollat ja käytännön sovellukset

Taisto Tammilehto

Tämän kandidaattitutkielman tavoitteena on antaa yleiskatsaus kvanttisalauksesta. Tutkielmasta tekee merkittävän suomenkielisen kirjallisuuden puute kvanttimekaniikan sovelluksista, kvanttilaskennasta ja etenkin kvanttisalauksesta. Kvanttilaskennan yleistyessä klassiset salausmenetelmät joutuvat kohtaamaan uudenlaisia hyökkäysriskejä. Tutkielma osoittaa lukijalle miksi klassiset kryptografiset menetelmät eivät ole tehokkaita kvanttilaskennallisia menetelmiä vastaan. Tutkielmassa korostuu kvanttisalauksen tärkeys yhteiskunnassa tulevaisuuden tietoturvan takaamiseksi. Tämä kirjallisuuskatsaus tutkii kvanttisalausta yleisestä näkökulmasta ja pyrkii antamaan lukijalle kattavan kuvauksen kvanttisalauksesta syventymättä aiheen matemaattiseen perustaan. Kvanttisalaus on kansainvälisesti laajasti tutkittu aihe, josta on olemassa runsas englanninkielinen kirjallisuus. Tässä tutkielmassa kootaan yhteen kvanttisalausta käsittelevää kirjallisuutta ja vertaillaan kahta eri turvaprotokollaa. Tutkielmassa osoitetaan, kuinka kvanttimekaniikka on kytköksissä kvanttilaskentaan ja kvanttisalaukseen. Kvanttisalaukseen syvennytään tarkastelemalla kvanttikanavien toteutusta kvanttisalausjärjestelmässä. Turvaprotokollia vertaillaan keskenään ja lopuksi tarkastellaan BB84-turvaprotokollan implementointia kvanttisalausjärjestelmässä. Kvanttisalauksen toteutusta tutkimalla tämä kirjallisuuskatsaus antaa selkeän kuvan kvantti-salausjärjestelmistä ja niiden käytännön sovelluksista. Kvanttilaskentaa on tutkittu pitkään ja useat läpimurrot kuten Shorin ja Groverin algoritmit julkaistiin jo 1900-luvun loppupuolella. Kirjallisuuskatsauksessa tutkitaan tämän vuoksi niin vanhoja kuin uusiakin julkaisuja. Tutkielman tulokset osoittavat kvanttisalauksen olevan lupaava teknologia, joka voi mullistaa kryptografian alan tulevaisuudessa. Kvanttitietokoneiden mahdollinen vaikutus nykyiseen kryptografiseen infrastruktuuriin on vakava huolenaihe, joka ansaitsee laajaa huomiota. Viimeaikaiset hyökkäykset kuten psykoterapiakeskus Vastaamoon ja Helsingin kaupunkiin kohdistuneet tietomurrot osoittavat, että vihamielisistä tekijöistä ei ole puutetta. Tutkielman tulokset ilmaisevat tarvetta luoda selkeä suunnitelma nykyisen yhteiskunnan tietoturvajärjestelmien vahvistamiseksi kvanttilaskennan mahdollistamia hyökkäyksiä vastaan

Jan 1, 20240 citations

Opettajien ja opettajaopiskelijoiden kvantti-ilmiöitä ja -olioita kuvaavat mallit : tapaustutkimus

Mervi A. Asikainen

TiivistelmäTutkimuksen avulla selvitettiin, mitä malleja opettajat ja opettajaopiskelijat käyttävät selittäessään kvantti-ilmiöitä ja -olioita Joensuun fysiikan ja matematiikan laitoksen fysiikan opettajalinjan syventäviin opintoihin kuuluvan Modernia fysiikkaa opettajille -kurssin aikana.Käsiteltyjä kvantti-ilmiöitä ovat mustan kappaleen säteily sekä valosähköinen ja Comptonin ilmiö; kvanttiolioista tarkastellaan elektronia ja fotonia.Lisäksi tutkittiin, miten osallistujat kokevat kurssin ja käytetyn tavanomaisista yliopistofysiikan opetusmenetelmistä poikkeavan, osallistujien ennakkotietoa hyödyntäville tehtäville rakentuvan opetuksen lähestymistavan.Modernia fysiikka opettajille -kurssi toteutettiin tutkimuksen aikana kahdesti.Ensimmäiselle kurssille osallistuneista kahdeksasta opiskelijasta seitsemän opiskeli fysiikkaa ja yksi matematiikkaa pääaineenaan.Kurssi toteutettiin kontaktiopetuksena, jossa luentoja ja harjoituksia oli kuusi viikkotuntia yhdeksän viikon ajan.Toisen kurssin osallistujat olivat fysiikan pätevöittämiskoulutuksessa opiskelevia työssä olevia aineenopettajia.Opetus järjestettiin monimuoto-opetuksena, joka koostui kuukausittaisesta neljän tunnin lähiopetuksesta sekä etäopiskelusta.Kaikkineen kurssi kesti yhdeksän kuukautta.Tutkija toimi molempien kurssien opettajana.Tutkimustehtävän vastaukset muodostettiin tapaustutkimuksen tutkimustraditiota hyödyntävästi.Olihan tutkimuksen tavoitteena aineenopettajien ja opettajaopiskelijoiden kvanttifysiikan oppimisprosessien syvällinen ymmärtäminen.Tutkimuksessa raportoidaan kahden tapausopiskelijan ja kahden tapausopettajan oppimisprosessit.Näitä lähtökohdiltaan erilaisia tapausoppijoita haastateltiin 4-5 kertaa kurssin aikana, minkä lisäksi he osallistuivat esi-ja lopputesteihin.Aineiston analysointia varten audio-ja videonauhoitetut haastattelut digitoitiin ja litteroitiin.Oppijoiden esille tuomien käsitysten ja mallien analysointi suoritettiin fysiikan näkökulmasta käsin.Muodostetut tulokset osoittavat, että tutkimuksen kohteena olleet henkilöt eivät käyttäneet jäsentyneesti ja johdonmukaisesti tieteellisiä malleja.Usein oppijoiden kvantti-ilmiöiden ja -olioiden kuvaamiseen käyttämät mallit muodostuivat useiden erillisten mallien ominaisuuksista: mallit olivat niin sanottuja hybridimalleja.Erityisesti ongelmana vaikutti olevan klassisten ja kvanttimallien sekoittuminen, joten oppijoiden esittämien mallien voidaan sanoa olevan eriytymättömiä.Mallin soveltamisen vaikeudet saattoivat johtua mallin ja todellisuuden välisen suhteen ymmärtämisen ongelmista, ja myös mallista kohteeseen siirtyvien ominaisuuksien hahmottaminen osoittautui erääksi kvanttifysiikan oppimisen ongelmakohdaksi.Lisäksi oppijan aiemman klassisen ja kvanttifysiikan tiedon epäkoherenssi vaikeutti uuden tiedon omaksumista.Toimimattomista malleista tai periaatteista luopuminen näyttää olevan oppijalle vaativa prosessi, joka vaatii oppijalta omien mallien metatason tarkastelua.Aineenopettajien ja opettajaopiskelijoiden suhtautuminen kurssiin ja sen menetelmiin oli pääosin myönteistä.Opettajilta tehtävien varaan rakentuva opetus sai sekä kiitosta että moitetta: opetusmenetelmän koettiin positiivisessa mielessä pakottavan perehtymään opiskeltaviin aiheisiin, mutta se koettiin myös työlääksi.Sekä opettajat että opiskelijat korostivat omakohtaisen pohtimisen tärkeyttä kurssin aiheiden oppimisessa.Opettajaopiskelijat arvostivat myös opetuksen vaihtelevuutta.Tulokset osoittavat, että fysiikan opettajaopinnoissa ja täydennyskoulutuksessa on todellinen kvanttifysiikan erikoiskurssin tarve.Tutkimukseen osallistuneiden opettajaopiskelijoiden ja aineenopettajien kvantti-ilmiöiden ja -käsitteiden hallinta oli vaatimatonta tasoa aiempien, perinteisten kvanttifysiikan kurssien jälkeen, mutta se parani selvästi kurssilla.Tutkimuksen tulokset myös muistuttavat oppijoiden ennakkotiedon huomioimisen tärkeydestä opetuksessa.Fysiikan opintojensa loppuvaiheessa olevilla opiskelijoilla kuten myös kokeneilla opettajilla voi esiintyä tieteellisen näkemyksen vastaisia käsityksiä.Myös heidän aiempi sisältöä koskeva tietonsa voi olla puutteellista.Tutkimuksen mukaan myös vaikeana pidetyn kvanttifysiikan opetuksessa on mahdollista päästä hyviin oppimistuloksiin lähtemällä liikkeelle oppijoiden ennakkotiedoista, tukemalla oppijoiden metakognitiivisten taitojen kehittymistä ja huomioimalla fysiikan malliluonne.Mainittuja tekijöitä voidaan pitää myös yleisinä laadukkaan fysiikan opetuksen kulmakivinä.

Dec 18, 20061 citation

Gaussiset- ja ei-gaussiset tilat kvanttimekaanisessa faasiavaruudessa

Sulin, Milo

Tutkielman aluksi kerrataan kvanttiteorian perusteet. Tämän jälkeen annetaan yksinkertaiset esimerkit diskreeteistä ja ääretönulotteisista systeemeistä ja niiden matematiikasta. Ääretönulotteisille systeemeille muodostetaan jatkuva faasiavaruusformalismi käyttäen Lien algebrojen ja ryhmien teoriaa. Määritellään gaussiset tilat ja tarkastellaan niiden vahvuuksia ja heikkouksia faasiavaruusformalismin sekä kvanttiinformaation sovelluksien kannalta. Johdetaan Wignerin funktio usealle esimerkille sekä käydään läpi Williamsonin ja Blochin-Messiahin matriisihajotelmat ja niiden merkitys gaussisiin tiloihin ja -operaatioihin liittyen. Määritellään ei-gaussiset tilat ja esitellään joitain niiden karakterisointiin käytettyjä mittoja ja tilojen kvanttiresursseja. Esimerkkien kautta tarkastellaan miten fotoneja lisäämällä tai poistamalla gaussisesta tilasta voidaan saavutaa Wignerin funktion negatiivisuutta omaava ei-gaussinen tila. Lisättyjen ja poistettujen fotonien tiloja tutkitaan tarkemmin käyttäen apuna Wickin todennäköisyyslausetta ja graa_teoriaa. Selvitetään miten näiden tilojen operaattorimomenttien laskeminen voidaan antaa graa_n hafnianin muodossa. Tunnistetaan yhteys hafnianin laskemiseen liittyvän uniikkien termien määrän osaongelman ja graa_en nimeämisiin liittyvien ongelmien välillä. Lopuksi tehdään yhteenveto käsitellyistä aiheista ja pohditaan miten esiin tulleet asiat ja käytetty matematiikka voisivat vaikuttaa jatkossa kvanttialgoritmien kehitykseen.

Oct 1, 20250 citations

Avoimet kvanttisysteemit

Meero Orte

Tutkielmassa käsitellään avoimia kvanttisysteemejä ja niiden kehitystä, lisäksi tutkielman lopussa simuloidaan tiettyä kvanttisysteemiä. Avoimien kvanttisysteemeiden vuorovaikuttaessa ympäristön kanssa, kvanttisysteemi kokee dekoherenssia, menettäen informaatiota ympäristöönsä. Dekoherenssi on keskeinen osa avoimen kvanttisysteemin kehittymistä. Avoimen kvanttisysteemin kehitystä ei voida kuvata unitaarioperaattoreilla, toisin kuin suljetulle systeemille. Kehitystä saadaan, kuitenkin mallinnettua masteryhtälöiden avulla. Kehitys voi olla Markovista, milloin kvanttisysteemi vain vuotaa informaatiota ympäristöönsä. On myös mahdollista, että ympäristö vuotaa informaatiota takaisin kvanttisysteemin, milloin kvanttisysteemin kehityksessä täytyy huomioida ympäristön muisti. Todellisuudessa kaikki kvanttisysteemit ovat avoimia, sillä mitään systeemiä ei voida eristää täysin ympäristöstään. On myös hyvä huomata, että masteryhtälöt ovat approksimaatioita systeemin kehityksestä, jotka pohjautuvat yksinkertaistuksiin ja oletuksiin.

Mar 9, 20260 citations

Siirtyminen kvanttitietokoneiden aikakauteen organisaatioissa

Olli Vanhanen

Informaatioteknologian ja viestinnän tiedekunta Joulukuu 2024 Kvanttitietokoneet ovat siirtymässä teoriasta käytäntöön.Kvanttitietokoneiden mukana tuleva laskentateho on kuitenkin riittävän voimakas murtamaan nykyisin käytössä olevat kryptografiset salausalgoritmit.Tarve kehittää ja standardisoida uudenlaiset kvanttitietokoneen kestävät salausalgoritmit tietotekniikan alalle, on merkittävä.Näiden uusien kvanttiturvallisten salausalgoritmien laajamittainen käyttöönotto eri tahoilla ja eri käyttötarkoituksiin on myös välttämätöntä.Organisaatioille uusiin kvanttikestäviin salausalgoritmeihin siirtyminen tulee vaatimaan merkittäviä resursseja, ja keskeistä on, miten kvanttiturvallinen siirtymä voidaan toteuttaa mahdollisimman tehokkaasti.Tämän kandidaatintyön tavoitteena on tuoda esiin kvanttitietokoneiden aiheuttama tietoturvauhka ja tarkastella tarvittavia ratkaisuja sekä niiden käyttöönottoa organisaatioissa.Työ on toteutettu kirjallisuuskatsauksena ja aiheen uutuuden myötä lähdeaineistona on käytetty mahdollisimman tuoreita julkaisuja.Työssä tarkastellaan kvanttiturvallisten salausalgoritmien ominaisuuksia ja haasteita niiden käyttöönotossa olemassa olevissa tietoturvajärjestelmissä.Lisäksi työssä käsitellään erilaisia siirtymästrategioita, joilla organisaatiot voivat sujuvasti päivittää tietoturvajärjestelmänsä kestämään kvanttitietokoneet.Työssä tutkitaan myös erilaisten valtiollisten tahojen käynnistämää kvanttiturvallisten algoritmien standardisointiprosessia, sen etenemistä sekä tuloksia.Erityisesti tarkastellaan NIST:in (National Institute of Standards and Technology) johtamaa kansainvälistä standardointiprosessia, joka pyrkii tunnistamaan ja validoimaan turvallisimmat ja tehokkaimmat kvanttiturvalliset salausalgoritmit.Prosessi sisältää algoritmien monivaiheiset arviointikierrokset, joissa testataan niiden kestävyyttä, suorituskykyä ja skaalautuvuutta erilaisissa tietoturvaympäristöissä.Työssä pohditaan myös kvanttiturvalliseen siirtymään liittyviä teknisiä ja organisatorisia haasteita, kuten uusien algoritmien yhteensopivuutta olemassa olevien järjestelmien kanssa, sekä niiden käyttöönoton aiheuttamia taloudellisia ja resurssivaatimuksia organisaatioille.Työssä tutkitaan myös keinoja varautua jatkuvasti kehittyvään tietoturvaympäristöön ja tarkastellaan menetelmiä, joiden avulla organisaatiot voivat ketterästi päivittää käyttämiään salausalgoritmeja uusien haavoittuvuuksien ilmetessä.Erityishuomiota kiinnitetään

Jan 1, 20240 citations