Ram'z

AVR [C version]

2011-02-13T23:29:00.029+07:00

ก็เห็นว่ามีคนงงๆ เกี่ยวกะ AVR อ่ะนะ เราก็ไม่ได้เก่งอะไรมาก
แล้วก็ไม่รู้จะช่วยยังไงด้วย

เริ่มจาก ทำความเข้าใจกับเรื่องต่างๆก่อน นะ

เขียน C ไม่เป็นทำไงดีวะ ? ก็เห็นหลายๆคนก็เขียน c ไม่เป็นอ่ะนะ
เลยจะมา เปรียบเทียบ C กะ Java(ที่เคยเขียนกัน) ว่ามันเหมือน รึ ต่างกันยังไง
- main
[c version]

int main(void){ // ที่จริง int, void ที่ตั้งค่าของ main เราก็ไม่ค่อยรู้หรอก ก๊อปๆมาเฉบๆ =.=
// do it
return 0;
}

[java version]

public class test{
public static void main(String[] args){
//do it
}
}

- switch case, if, while, for ใช้เหมือนกันเลย (รวมทั้งการประกาศตัวแปรด้วย)
- การเขียน Method (หรือ function)
[c version]

[ตัวที่ return] [ชือ function] ( [parameter] ){
//.....
return [ค่าที่คืน];
}

[java version]

public [ตัวที่ return] [ชือ function] ( [parameter] ){
//.....
return [ค่าที่คืน];
}

จะเห็นว่า มันแทบไม่ต่างกันเลยนะ.... :D

ประกาศตัวแปรใน AVR? บางคนอาจเห็น code ที่ว่า
int a, unsigned int b, char c, unsigned char d;
ก็อาจงงว่า ทำไมต้องเป็นงี้, unsigned มันคือบ้าอะไร
ผมขอตอบตรงๆว่า "ผมก็ใช้มั่วครับ =_= " แต่จะอธิบายคร่าวๆในแต่ละตัวแปรละกัน
ใน AVR นี้ ขอแนะนำให้ใช้ unsigned char นะ(ความรู้สึก) เพราะ char มั้นเป็นค่าแบบ 8 bit
และ unsigned หมายความว่าจะเป็นเฉพาะค่าบวก
เพราะฉะนั้น unsigned char จะเก็บค่าได้ตั้งแต่ 0-255 (เท่าที่เข้าใจนะ - -a)

Include? เหมือน import ใน java แหละ... ถ้าเราจะใช้อะไรก็ต้อง import เข้ามา
จริงๆ เราก็ไม่เคยจำหรอก ก๊อปๆ code เก่ามาอีกทีอ่ะ
- avr/io.h // จะมีตัวแปรต่างๆ ของ AVR อยู่,เอาไว้ตั้งค่าต่างๆ
- util/delay.h // สามารถใช้ _delay_ms(int ms); ได้....
- avr/interrupt.h // ใช้พวก interrupt

Input&Output? ขอสรุปง่ายๆ นะ
การตั้งค่า port ต่างๆของ avr นั้นจะตั้งค่าอยู่ที่ DDRx [x : B,C,D แล้วแต่เราจะใช้]
โดย DDR แต่ละตัวจะมีจำนวน bit ต่างกันไป
DDRB, DDRD จะมีจำนวน 8 บิท [7..0]
DDRC จะมี 7 บิท [6..0]
แล้วก็ ถ้าสมมติเราจะ set ให้ PORTB5 เป็น Output สามารถตั้งค่าดังนี้

DDRB |= (_BV(5)); // หมายถึง Shift left มา 5 บิท

ถ้าจะตั้งเป็น input ก็ตั้งดังนี้ (ไปดูในส่วนของ Switch ด้วยนะ)

DDRB &= ~(_BV(5)); // หมายถึง กลับบิท(Shift left มา 5 บิท)

Switch? ทำความเข้าใจกะ Switch ก่อนว่า ตอนต่อน่ะ มันจะเป็น Switch เปิด-ปิด
ถ้าเกิดกด Switch มันจะให้ค่า 0 ออกมา(ต่อลง Ground)
ฉะนั้น เราก็ต้อง Pull-up วงจร ซึ่ง AVR มัน Pull-up ให้อยู่แล้ว
(โดย set MCUCR ให้ bit ของ PUD ให้เป็น 0, ดูได้จาก datasheet หน้า 86)
แล้วก็ไปตั้งให้ PULL-UP เป็นค่า 1 ใน bit ที่ต้องการ
สมมติ จะ Pull-up PB0 ก็

DDRB &= ~(_BV(PB0)); // input PB0
PORTB |= _BV(PB0) // Pull-up PB0

ส่วนการนำ Switch ไปใช้งานก็ทำได้ดังนี้

if((PINB&0x01) == 0){ // เช็คว่าเป็น 0 รึยัง ???
_delay_ms(2); // delay ระหว่างการกดให้มันรอซักหน่อย...
........ // ทำอะไรก็ทำ... :P
}

Timer&Clock? มาเข้าใจก่อนว่า AVR ที่เรากำลังใช้อยู่นี้มันสามารถสร้าง Clock ที่ความถี่ 16MHz หรือใน 1 วิจะสร้าง clock ได้ 16 ล้านลูก... โดยเราสามารถลดจำนวน clock ที่ผลิตออกมาได้โดยการ prescale
(ดูได้ที่ datasheet หน้า 104 ตาราง prescale)
ถ้าเราต้องการให้มัน prescale ที่ 1024

TCCR0B |= _BV(CS02) | _BV(CS00); // 1024-prescaler

มันจะเปลี่ยนให้ AVR ปรับ Clock เป็นความถี่ 16MHz/1024 = 15625 Hz
แล้วก็ใน AVR จะมี Register ของ Timer อยู่คือ TCNT0( 8 bit )
ซึ่งทุกๆ clock TCNT0 จะนับค่าเพิ่มขึ้น 1 ไปเรื่อยๆ จนถึงค่า 255 แล้วปรับเป็น 0 ใหม่

Interrupt? เอาแบบสรุปๆ รวดเร็วเลยนะ...
การตั้งค่า Interrupt มีหลากหลายแบบ
เช่น Compare A, Compare B, Overflow
แต่ที่ใช้กันในการทำแลปคือ Interrupt Overflow Flag
ซึ่งตั้งค่าดังนี้ (ลองไปดู datasheet เกี่ยวกับ register timer เอาเด้อ... )

TIMSK0 |= _BV(TOIE0)// Timer Overflow Interrupt Enable
sei(); //Enable Interrupt

ซึ่งการ Interrupt ทุกๆครั้งที่ TCNT0 นั้นเกิดการ Overflow(เกินค่า TOP ของ Counter)
จะเกิด Overflow flag ขึ้นและไปทำงานที่ ISR(TIMER0_OVF_vect)

ISR(TIMER0_OVF_vect) {
// สมมติว่า AVR ให้ clock ที่ 15625 Hz และ Counter นี้จะ Interrupt ทุกๆ 256 clock
// แสดงว่า Function นี้จะทำงาน 15625/256 ~ 61 Hz
}

PWM? ไปอ่านอันเก่าเอาเด้อ... =___= Click

ปล. ถ้าว่าง(มาก) + ไม่เบื่อล่าแย้... จะมาอธิบาย แต่ละ Lab ให้ละกัน =..=
ปล2. _BV(int bit) มันคือ shift left นะ.... ในBlog นี้ใช้ < < แล้วมันเจ๊ง = ="

Disjoint Set [data structure]

2011-02-10T00:42:00.000+07:00

Disjoint Set ? ในการคำนวณที่มี set ของ element ให้มานั้น เราสามารถใช้ประโยชน์ในการแยกกลุ่มของ element ต่างๆออกได้เป็นกลุ่มๆ ที่ไม่มี element ที่เกี่ยวข้องกันเลย หรือเรียกว่า disjoint-set ในระบบโครงสร้างแบบ Disjoint-set data structure นั้นจะแบ่ง element ต่างๆออกเป็นกลุ่มๆที่ไม่มีความเกี่ยวข้องกันเลย และจะมี Function หลักที่จัดการโครงสร้างข้อมูลดังนี้

Find: สำหรับวิเคราะห์ว่า element ต่างๆที่เราหานั้น อยู่ใน set เดียวกันหรือไม่
Union: รวม set สองอันให้เป็น set เดียวกัน

เนื่องจากการทำงานที่มีการทำงานทั้งสองแบบที่กล่าวมานั้น ทำให้โครงสร้างแบบ disjoint-set สามารถที่จะเรียกการใช้งาน union-find data structure หรือ merge-find set ได้ นอกจากนี้ยังมีการทำงานอย่างอื่นอีกคือ MakeSet จะเป็นการกำหนด set ให้ element (มี element คือตัวมันเองเพียง element เดียว) ด้วยการทำงานทั้ง 3 อย่างนี้ เราสามารถที่จะใช้ในการแก้ปัญหา Partitioning problem ได้
ในบางครั้งเพื่อที่จะกำหนดฟังก์ชันการทำงานต่างๆเหล่านี้ เพื่อให้มีความแม่นยำมากขึ้น จำเป็นต้องแสดง set โดยละเอียด

Disjoint-set: Linked-Lists
วิธีที่จะแสดงโครงสร้างข้อมูลแบบ disjoint-set อย่างง่ายๆคือการสร้าง Linked list ในแต่ละ set โดย element ที่เป็น Head ของ list จะเป็นตัวแทนในการแสดง set ในกลุ่มนั้นๆ ซึ่งการกำหนด set เริ่มต้นในแต่ละ element ทำได้โดย MakeSet ขึ้นมาเพื่อสร้าง List ที่มี 1 element นอกจากนี้ก็จะมี Union จะทำการรวม element ใน แต่ละ set ให้เป็น set เดียวกัน ซึ่งในการ Union จะใช้เวลาเป็นค่าคงตัว แต่ในการ Find นั้นมีข้อเสียซึ่งใช้เวลาในการทำงาน Ω(n) หรือ เป็นเชิงเส้น อย่างไรก็ตาม Union จะทำการปรับค่าของแต่ละ element ใน set ให้มี head เป็นที่เดียวกันก็ต้องใช้เวลา Ω(n)

Disjoint-set: Forests(Tree structure)
Disjoint-set forests เป็นโครงสร้างของ disjoint-set ที่แสดงความสัมพันธ์ของ set ด้วย Tree data structure ซึ่งในแต่ละ node ของ tree นั้นจะถูกอ้างอิงไปยัง parent ของแต่ละ node โดยวิธีนี้ได้ถกอธิบายโดย Bernard A. Galler และ Michael J. Fischer ในปี ค.ศ. 1964
Disjoint-set forests จะแสดงแต่ละ set ของแต่ละกลุ่มด้วย root ของแต่ละ tree โดยเราสามารถหา( Find )ได้ว่า Element ที่เรากำลังพิจารณานั้นอยู่ใน set ใดโดยดู Parent ของแต่ละ tree นอกจากนี้ การUnion ก็สามารถทำได้โดยรวมเอา root ของแต่ละ set ให้รวมเป็น tree ต้นเดียวกัน ดังนั้นเราสามารถสร้าง Structure นี้ได้ดังนี้

function MakeSet(x)
x.parent := x

function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)

function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

ในรูปแบบที่กล่าวมานั้นยังเป็นการทำงานที่ไม่ดีพอ เนื่องจาก tree นั้นมีโอกาสสูงที่จะมีความสูงของต้นไม้มากเกินจำเป็นทำให้การค้นหา set นั้นใช้เวลานาน อย่างไรก็ตามเราสามารถเพิ่มประสิทธิภาพได้สองวิธี วิธีแรกจะใช้การ Union โดยใช้ Rank ซึ่งจะทำให้ tree นั้นมีความสูงน้อยลง(เตี้ยลง) และ เป็น tree ขนาดใหญ่ขึ้น(กว้างขึ้น) ซึ่งส่งผลต่อการประมวลผลจะทำให้เร็วขึ้นเนื่องจากความสูงของ tree นั้นมีผลต่อการประมวลผลต่างๆ ซึ่งการทำงานจะ Union tree มีมีความน้อย ไปต่อท้าย tree ที่มีความสูงมากกว่าซึ่งจะทำให้เวลาในการประมวลผลไม่เพิ่มขึ้น และ tree นั้นจะมีความสูงเพิ่มขึ้นก็ต่อเมื่อ tree สองต้นนั้นมีความสูงเท่ากัน ในวิธีนี้เราจะใช้ Rank แทนความสูงของต้นไม้ โดยจะกำหนดให้ ต้นไม้ที่มีเพียง 1 element จะมี Rank = 0 และความสูงของต้นไม้ที่มี rank = r เท่ากัน เมื่อถูก union จะมี rank = r+1 ซึ่งผลจากวิธีนี้จะทำให้เวลาในการทำงานของ MakeSet,Union,Find ใล้เวลาในการทำงานเป็น O(logn) จากที่กล่าวมาจะสามารถสร้าง Pseudocode ของ MakeSet และ Union ได้ดังนี้

function MakeSet(x)
x.parent := x
x.rank := 0

   function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else if xRoot != yRoot // Unless x and y are already in same set, merge them
         xRoot.parent := yRoot
         if xRoot.rank == yRoot.rank
             yRoot.rank := yRoot.rank + 1

ส่วนวิธีที่สองที่จะปรับปรุงความสามารถให้ดีขึ้นนั้น จะเรียกว่า "path compression" หรืออธิบายคร่าวๆว่าจะเปลี่ยนเส้นทางการเชื่อมของ child ใน tree ของ set นั้นๆให้ชี้ Parent มาที่ root โดยตรงเลย ซึ่งจะทำให้ระยะทางที่ Find จะทำงานนั้นใช้เวลาที่สั้นลง โดยเราสามารถปรับปรุง Find ได้ดังนี้

function Find(x)
     if x.parent == x
        return x
     else
        x.parent := Find(x.parent)
        return x.parent

จากทั้งสองวิธีที่กล่าวมานั้นสามารถทำให้การทำงานมีประสิทธิภาพมากขึ้น โดยเวลาในการทำงานนั้นจะมีประสิทธิภาพเพิ่มมากขึ้น เมื่อมีการใช้งานที่มากขึ้น ดังนั้นเวลาที่ใช้ดำเนินงานจะเข้าใกล้ค่าคงที่ขนาดเล็กมาก

Applications

โครงสร้างข้อมูลแบบ Disjoint-Set จะจำลองการแบ่งกลุ่มของงานออกเป็น set อย่างเช่นการตรวจสอบ Connected Component ของ undirected graph โดยในการจำลองปัญหานี้จะสามารถกำหนดได้ว่าจุดสองจุดใดๆจะเป็น component เดียวกัน หรือสามารถเช็คได้ว่า ถ้าหากเชื่อมจุดสองจุดนั้นจะทำให้เกิด cycle ขึ้น โดย Union-Find algorithm นี้ นอกจากนี้โครงสร้างนี้ได้ถูกใช้ใน Kruskal's algorithm เพื่อใช้ในการหา minimum spanning tree ของ graph

Reference

Wikipedia - Disjoint-set
Implementation of Linked-list representation in C++, by Bo Tian
Implementation of Disjoint-set Forests in C++, by Bo Tian
C++ implementation, part of the Boost C++ libraries
Java applet: A Graphical Union-Find Implementation, by Rory L. P. McGuire
Wait-free Parallel Algorithms for the Union-Find Problem, a 1994 paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union-Find that never needs to block
Python implementation

การใช้ PWM version มั่ว...

2011-02-09T21:58:00.000+07:00

เพื่อที่จะดูเป็นทางการ กระผมขอเปิดบทความแรกด้วยการโพสอะไรที่มันดูมีสาระหน่อยละกันฮับ เอาเป็นเรื่องการเขียน PWM ของบอร์ด AVR ที่กำลังเรียนอยู่ในวิชา Verilog ละกัน

[PWM-ยกตัวอย่างแบบ fast pwm mode นะ]
ขออธิบายเท่าที่เราเข้าใจนะ... เพราะไม่รู้จิง+จารย์ไม่ได้สอนในห้อง(เลยยยยย)

?pwm คือ... อะไรไม่รู้ที่สามารถควบคุมการนับ TCNT0(Counter ของ timer) ได้ [กำหนดค่าสูงสุดของการนับ ปกติเปน 255 แล้ว interrupt เป็น 0]
และสามารถสร้าง square wave ได้จากไอ่ TCNT0 อ่ะแหละ... มันเป็นไง เด๋วบอกอีกที :P

fast pwm ?
มันคือ mode ที่นับ Counter(TCNT0) ตั้งแต่ 0 ถึง TOP(ปกติ max:255) อ่ะ แล้วกลับมาที่ 0 ใหม่เพื่อนับไปเรื่อยๆ ในแต่ละ Clock
ถ้าเราตั้งโหมดให้กำหนด TOP ได้ (กำหนดโดย OCR0A) เราจะสามารถที่จะควบคุมปริมาณจำนวน square wave ที่เกิดขึ้นได้ในเวลาที่กำหนด

Square Wave มาจากไหน ?
-ขอเริ่มจากการกำหนด ค่า OCR0A และ OCR0B ซึ่ง... OCR0A คือ TOP ของ TCNT0 ที่เป็น counter ที่จะนับ และ OCR0B เรียกง่ายๆ มันจะเป็นตัวกำหนด % Duty-Cycle ของ wave ที่เราต้องการ [ในที่นี้ต้องการ 50% duty-cycle ดังนั้น OCR0B = OCR0A/2]
-ส่วน Wave ที่แสดงออกมานั้นจะออกทาง OC0A(PD6) หรือไม่ก็ OC0B(PD5) แล้วแต่เรากำหนด(เด๋วจะกำหนดให้ดู) ซึ่งมันจะทำงานประมาณว่า พอ Counter นับไปถึง OCR0B แล้วมันจะสลับค่า Wave ไปอีกค่าหนึ่ง(ตามที่ตั้งค่าไว้)
และจะสลับไปเป็นอีกค่าเมื่อ Counter นับถึง OCR0A หรือ TOP นั่นเอง แล้วกลับมานับ 0 ใหม่
ซึ่งการทำงานตรงนี้จะให้ Square Wave มาให้เราได้

ต้องการบรรเลง NOTE ต่างๆจะทำอย่างไร ?
- เนื่องจากปกติ avr จะสร้าง clock ความถี่ 16MHz หรือ สร้าง คลื่นมา 16ล้าน ลูกถูกป่ะ, แล้วหลังจากเรา prescale ด้วย 1024 แล้วมันจะให้ clock ทั้งหมด 15625 ลูกภายใน 1 วินาที(16MHz/1024 = 15625 Hz)
คราวนี้(สมมติ)เราต้องการสร้าง wave จำนวน 261.63 Hz ซึ่งหมายถึง ใน 1 วิต้องมี Wave ทั้งหมด ~ 261 ลูก แสดงว่า Counter นั้นจะต้องวิ่งนับทั้งหมด 15625/261.63 clock ~ 59 clock
จะได้ว่าเราจะต้องกำหนด TOP(OCR0A) ให้เป็น 59 เพื่อจะทำให้ใน 1 วินั้นมี Wave ~ 261 ลูก

หมาวยเหตุ: ปกติ Interrupt นั้นจะต้องนับ Counter ถึง 255 มันถึงจะทำ ISR(TIMER0_OVF_vect) แต่ในที่นี้ Counter พอนับถึง TOP มันก็ Interrupt เน้ออออ

Example Code : Click
PWM Reference : Click