pdf مطالب زیر را به دو زبان فارسی و انگلیسی از نشانی زیر دریافت نمایید:

http://download3-8.files-upload.com/2007-07/21/16/FPGA.pdf

چكيده :‌ در اين مقاله سعي شده است توضيحي به اجمال در مورد ساختار کلّي FPGA ارائه شود. نخست به تاريخچه مختصري از FPGA اشاره گرديده است، و سپس در مورد ساختار داخلي FPGA و نحوه پيکربندي قالب‌هاي منطقيِ آن و ترانزيستورها مطالبي به صورت مختصر بيان شده است. برنامه‌ريزي در FPGA براي طراحان امري مهم به شمار مي‌آيد؛ بنابراين در مورد طراحي و برنامه‌نويسي براي شبيه‌سازي ديجيتال FPGA با کمک طراحي رايانه‌اي اشاره‌اي هر چند ناچيز آمده است. نکات مهم در طراحي و حتّي ساخت سخت‌افزار FPGA و نيز مقايسه اي کوتاه در مورد شباهت‌ها و تفاوت‌هاي FPGA با ديگر سامانه‌هاي منطقي ، اضافه گرديده است.

كلمات كليدي: FPGA، منطقي ، ترانزيستور، سخت‌افزار، شبيه‌سازي، طراحي رايانه‌اي، ديجيتال، سامانه .

Abstract
In this paper, I tried to present a short description about the general structure of FPGA (Field-
Programmable Array Logic). First, a short discussion about the history of FPGA; then a short explanation about
the internal structure FPGA and configuration methods of its logic blocks and transistors is described. The act of
programming in the FPGA is an important aspect for the experts and designers; so I explained a little about the
digital simulation of FPGA via computer aided design (CAD) softwares. Some essential aspects of designing and
also manufacturing the FPGA hardware is added to this article with some the similarities and differences
between FPGA and other digital systems.

فناوری راشمور

فناوری راشمور

فناوری راشمور روشی برای بازیابی اطلاعات با استفاده از شاخص‌هایی برای بهینه‌سازی در نحوه دستیابی اطلاعات است. در این روش شاخص‌ها را تا یک‌ششم اندازه اصلی‌شان کوچک می‌کنند که این امر باعث می‌شود که شاخص‌ها فضای کمتری را از حافظه اشغال کنند. علی‌الخصوص روش راشمور برای رایانه‌ها و یا سامانه‌هایی با حافظه‌ی اصلی پایین و اطلاعات بالا کارایی بسیار خوبی را از خود به نمایش می‌گذارد.

برای نخستین بار فناوری راشمور در نسخه‌های اوّلیه پایگاه‌های داده‌ای مایــــکروسافت ویژوال فاکس‌پرو مورد استفاده قرار گرفت. این روش برای پایگاه‌های داده‌ای با حالت‌های مختلفی از جمله اشتراک بین چند داده ، اندیس‌های مشترک و منفی و نیز شمارش تعداد اطلاعات موجود با خصوصیات ارائه‌شده مناسب است.‌‌ راشمور در پایگاه‌های داده‌ای مانند dbf و mdb که با موتور جت (Jet Engine) مدیریت می‌شوند به خوبی قابل استفاده است ولی در ODBC قابل استفاده نیست.

Foxpro simple inserting and deleting

نحوه ذخیره و بازیابی اطلاعات در فاکس پرو

در فایرفاکس اگر بخواهیم یک رکورد جدید بنویسیم این پایگاه د اده رکورد ها را با طول ثابت در نظر می گیرد و فیلد ها را به ترتیب زیر می ریزد:
نخست یک کارکتر خالی می گذارد و سپس فیلدها را قرار می دهد به ترتیبی که کارکتر های رشته ای را به صورت چپ گرا نوشته و اگر کمتر از طول ثابتش باشد سمت راستش را با فضای خالی پر می کند و اگر داده ها عددی باشد آنها را به صورت راست گرا می نویسد و سمت چپش را خالی می گذارد.
مثلاً ما رکوردی را به صورت زیر داریم:
ID(char[10])=ali
Number(numeric)=3
که در فایل داده ای به صورت زیر نوشته می شود:
.ali...........3
که نقطه ها را نمایانگر فضای خالی نشان دادیم.
اگر بخواهیم این رکورد را پاک کنیم کارکتر اولی را به صورت ستاره یا نمادی در می آورد که نشان می دهد که این رکورد حذف شده است:
*ali...........3

Generating Functions

الف- آشنایی با توابع مولد

در مورد روابط چندجمله ای بازگشتی به دست آوردن رابطه ای صریح برای n امین جمله ی حاصل از رابطه در اغلب موارد کاری مشکل به نظر می رسد. به فرض این که ما یک تعداد ضریب a_0,a₁,…,a_n,… که در روابط بازگشتی تعریف شده اند داریم اما هیچ رابطه ی موثقی برای جمله ی n ام آن پیدا نکرده ایم.a_n می تواند یک عدد و یا یک الگوریتم حاصل از ورودی n باشد.تابع مولد این رشته به صورت سری توانی زیر تعریف می شود:

g_(x)=∑_{n=0 to ∞} a_n x­^n =a₀+a₁x+...+a_nx^n+…

نخست با ذکر یک مثال که به نوعی نشان دهنده چگونگی عملکرد توابع مولد است این مبحث را ادامه می دهیم:

مثال 1 # چه تعداد عدد صحیح برای تساوی c₁+c₂+c₃+c₄=25 ; c_i≥0 ; 1≤i≤4 وجود دارد؟

این سوال قابل تعمیم به بسیاری از مسایل واقعی است. به عنوان مثال " 25 شکلات چگونه بین 4 کودک تقسیم می شود ؟".برای هر کودک امکان به دست آوردن 0 تا 25 شکلات وجود دارد یا :

x^0+x ^1+…+x^24+x^25

بنابر این جواب این مساله مجموع ضرایب حاصل از جملات دارایx^25 درf_(x) است یعنی:

f_(x)=(1+x+..+x^25)^4

جواب حتی از راه ضرایب x^25 در تابع مولد آن است:

g_(x)=(1+x+…+x^25+x^26+…)^4

ب- روش های محاسبه

تعریف1# فرض کنید a₀,a₁,… یک رشته از اعداد حقیقی باشند. تابع مولد رشته مزبور به صورت زیر است:

F_(x)=a₀+a₁x+a₂x^2+...=∑_{i=1 to ∞} a_ix^i

مثال 2 # برای هر عددZ>0 n εداریم:

(1+x)^n = (n,0)+(n,1)x+…+(n,n) x^n

بنابراین (1+x)^n تابع مولد رشته ی (n,0),(n,1),..,(n,n),… است.

مثال 3#

الف) برای nεZ>0 داریم:

(1-x^(n+1))=(1-x)(1+x+x^2+…+x^n)

بنابراین : 1-x)) / (1-x^(n+1))

که این تابع مولد رشته ی 1و1و...و1و0و0و0و0و...است.

ب) با تعمیم الف داریم: 1=(1-x)/(1+x+x^2+…) بنابراین 1/(1-x) تابه مولد رشته ی 1و1و1و....و1 است.این سری برای مقادیر |x|<1 همگراست.

ج) اگر از رابطه 1/(1-x) = 1+x+x^2+… مشتق بگیریم داریم:

(1/(1-x))'=(1+x+x^2+…)'=>1/(1-x)^2 =1+2x+3x^2+…

که 1/(1-x)^2 تابع مولد 1و2و3و....وn است.

د) با ادامه مشتق بگیریم می توانیم تابع مولد دیگری نیز به دست بیاوریم:

(x/(1-x)^2)'=(x+2x^2+3x^3+..) => (x+1)/(1-x)^3 =1+4x+9x^2+…

که (x+1)/(1-x)^3 1^2,2^2,3^2,… و(x+1)/(1-x)^3 x 0^2,1^2,2^2,3^2,… را تولید می کنند.

برای n , r εZ>0که n≥r>0 داریم: (n,r)= n! /(r! (n-r)!) =[n(n-1)(n-2)…(n-r+1)] / r! اگر n عضوی از اعداد مثبت صحیح نباشد می توان از از رابطه فوق باز استفاده کرد : (-n,r) = [(-n)(-n-1)(-n-2)…(-n-r+1)] /r! = ((-1)^r) [n(n+1)..(n+r-1)] / r!] =( (-1)^r)(n+r-1,r) ودر ضمن برای هر عدد طبیعی مانند n (n,0) = 1 ; تعریف می شود. برای هرaε R و Z>0 n ,m ε داریم: 1)(1+x)^n =(n,0)+(n,1)x+(n,2)x^2+…+(n,n)x^n 2)(1+a x) ^n=(n,0)+(n,1)ax+(n,2)(ax)^2+..+(n,n)(ax)^n 3)(1+x^m)^n=(n,0)+(n,1)x^m+(n,2)x^2m+…+(n,n)x^mn 4)1/(1-x)^n= 1+x+x^2+…=∑i=0 to ∞ x^i 5)(1-x^(n+1))/(1-x) =1+x+x^2+…+x^n 6)1/(1+x)^n=(-n,0)+(-n,1)x+…=∑i=0 to ∞ (-n,i) x^i =∑i=0 to ∞ (-1^i)[(n+i-1,i) x^i] 7)1/(1-x)^n =(-n,0)+(-n,1)(-x)+…=∑i=0 to ∞ (-n,i) (–x)^i =∑i=0 to ∞ (n+i-1,i) x^i] 8)if f(x)=∑i=0 to ∞ ai x^i , ,g(x)=∑i=0 to ∞ bi x^i , h(x)=f(x)g(x) => h(x)= ∑i=0 to ∞ci x^i => for any k≥0 ck=a.bk+a1.bk-1+…+ak-1.b1+ak.b0

جدول ( 1)

مثال 4 # ضریب x^15 را در f_(x)=(x^2+x^3+…)^4 به دست آورید.

(x^2+x^3+x^3+…)^4 = (x^8)[1+x^2+x^3+…]^4

و چون 1+x+x^2+x^3+…=1 /(1-x) آنگاه ( x^8) / [1-x]^4 در حالی که x^8 در تمامی جملات / [1-x]^41 برای 0≤r≤n ضرب میشود بایستی ضرایب x^7 را در 1 / [1-x]^4 به دست آوریم(8+7=15) در نتیجه:

((-1)^7)(-4,7)= ((-1)^7) ((-1)^7)(4+7-1,7)=(10,7)=120

مثال5 # درستی رابطه_{i=0 to n} (n,i)^2 (2n,n)=∑ را برای nεZ>0 بدست آورید.

از آنجایی که [(1+x)^n]^2=[1+x]^2n با قیاس ضرایب ( به مانند توانهای x) ضریب x^n باید در (1+x)^2n و[(1+x)^n]^2 برابر باشند:

[(1+x)^n]^2=[(n,0)+(n,1)x+…+(n,n)x^n]^2

که در ضریب x^n در آن از مجموع ضرایب x^n به دست می آید:

(n,0).(n,n)+(n,1).(n,n-1)+…+(n,n)(n,0)

که با وجود رابطه (n,n-r)=(n,r) برای 0≤r≤n به این می رسیم که(n,0)^2 +(n,1)^2+…+(n,n)^2=∑_{i=0 to n} :

مثال 6 # با استفاده از توابع مولد تعداد مجموعه های چهارتایی حاصل از مجموعه S={ 1,2,…,14,15} که هیچ عدد صحیح متوالی وجود ندارد ,حساب کنید.

الف) یک مجموعه مثل 1,3,7,10 که می نویسیم 1≤1<3<7<10≤15 دیده می شود که اختلاف عدد های پشت سر هم به صورت زیر است:

1-1=0 ; 3-1=2 ; 7-3=4 ; 10-7=3 ; 15-10=5

و این اعداد در مجموع برابر با 14 است. مجموعه دیگری مثل 2و5و11و15 که: 1≤2<5<11<15≤15 که مجموع اختلاف های پشت سر هم در مجموع برابر 14 می شود.در دو نمونه مذکور بایستی c₁+c₂+c₃+c₄=14;c₅,c₁≥0;c­₃,c₄,c₂ که جواب همان ضرایب x^14 است:

F_(x)=(1+x+x^2+…).[(x^2+x^3+…)^3].(1+x+x^2+…)=x^6.(1-x)^(-5)

با توجه به ضریب x^6 بایستی ضرایب x^8 را در (1-x)^(-5) به دست آوریم: (-5,8)(-1)^8 = (5+8-1) = (12,8) = 495

ب ) راه دیگر برای نگاه به این مساله به صورت زیر است. برای مجموعه 1,3,7,10 از نامساوی 0<1<3<7<10<16 استفاده می کنیم که اختلاف ها برابر با 0 و 1 و 3 و2 و 5 است .0 از آنجایی که هیچ عددی مابین 0 و 1 نیست و 1 از آنجایی که عدد صحیح 2 بین 1 و3 است و3 عدد از آنجایی که سه عدد 4 و5 و 6 بین 3 و7 و 5عدد از آنجایی که 5 عدد صحیح 11 و 12 و13 و14 و15 بین 10 و 16 است.که مجموع 0 و 1 و2 و 3 و5 برابر 11 است.برای مجموعه دیگری مثل 2و5و11و15 نامساوی 0<2<5<11<15<16 در نظر می گیریم که نتایج 1 و2 و5 و3 و0 مجموع 11 می شود.این نتایج از راه حل c₁+c₂+c₃+c₄=11;c₅,c₁≥0;c­₃,c₄,c₂≥1 که جواب همان مجموع ضرایب x^11 است.

g_(x)=(1+x+x^2+…)(x+x^2+x^3+…)^3(1+x+x^2+…) = x^3 .[(1-x)^(-5)]

که با توجه به x^3 باید به دنبال مجموع ضرایب x^8 در[(1-x)^(-5)] برابر است: (-5,8).(-1)^8=495 که همانند جواب در قسمت الف است.

پ – کاربرد توابع مولد در افراز اعداد صحیح

در نظریه اعداد با افراز اعداد صحیح و مثبت به عوامل صحیح و مثبت برخورد داریم. از این افراز به p_(n) یاد می شود.

P(1)=1

P(2)=2=1+1

P(3)=3=2+1=1+1+1 =>The order is not important

ما می خواهیم بدون نوشتن همه افراز ها به p_(n) دسترسی داشته باشیم. باید ابزاری باشد که به ما این امکان را دهد.

اگر n ε Z >0 و برای شماره اول از 0 یا 1 یا 2 یا ... می توان استفاده کرد .سری حاصل 1+x+x^2+… حساب این اعداد را در بردارد .1+x^2+x^4+x^6+… برای دومین عدد در افراز p_(n) است.برای مثال برای به دست آوردن p(10) ما باید ضریب x^10 در f_(x) به دست آوریم:

f_(x)=(1+x+x^2+…).(1+x^2+x^4+…)…….(1+x^10+x^20+…)=[1/(1-x)].[(1/(1-x^2)]=П_{i=1 to 10}1/(1-x^i)

اگر عمل ضرب بالاتر از i=10 تعمیم پیدا کند ما p(x)=П_{i=0 to ∞} 1/1-x^i که p(0) و p(1) و p(2) و.... را تولید میکند وما p(0)=1 را تعریف می کنیم.

به دلیل دشواری کار محاسبه p_(n) استفاده از توابع مولد در این مورد کارایی بسیاری دارد.

مثال 7 # تابع مولد را برای p_d(n) (تعداد افراز های مثبت وصحیح n به اعداد متفاوت ) بیابید.

1)1+1+1+1+1+1+1

2)1+1+1+1+2

3)1+1+1+3

4)1+1+4

5)1+1+2+2

6)1+5

7)1+2+3

8)2+2+2

9)2+4

10)3+3

11)6

افراز های شماره 6 و7 و 9 و 11 دارای اعدادی متفاوت اند پس p_d(6)=4.در محاسبه p_d(n) برای هر kεZ>0 دو گزینه موجود می بلشد : یا kبه عنوان یکی از افرازهای n است یا نیست که این دو گزینه در مجموع برابر 1+x^k است پس می توان نوشت:

p_d(6)=(1+x).(1+x^2)(1+x^3)….=П_{i=1 to ∞}(1+x^i)

برای هر n ε Z>0 p_d(n) برابر مجموع ضرایب x^n در П_{i=1 to ∞}(1+x^i) است.(تعریف: p_d(0)=1 ) و وقتی n=6 مجموع ضرایب x^6 در

(1+x).(1+x^2)(1+x^3)….(1-x^6) برابر 4 است.

مثال 8 # با ملاحظه مثال 7 می بینیم که تعداد افراز عدد 6 به اعداد فرد نیز برابر 4 است. آیا این دو ارتباطی با هم دارند؟

فرض کنیم که p_o(n) نشانه افراز n به اعداد فرد است(تعریف: p_o(0)=1)تابع مولد برای رشته p_o(0), p_o(1), p_o(2),…. به صورت زیر است:

p_o(x)=(1+x+x^2+…).(1+x^3+x^6+…)(1+x^5+x^10+…)….=[1/(1-x)][1/(1-x^3)][1/(1-x^5)]…..

و نیز با توجه به این که: 1+x=(1-x^2)/(1-x) ,1-x^2=(1-x^4)/(1-x^2) ,…….

داریم: p_o(x)=(1+x)(1+x^2)(1+x^3)… => [(1-x^2)/(1-x)][ (1-x^4)/(1-x^2) ]…..= [1/(1-x)][1/(1-x^3)][1/(1-x^5)]…..=p_d(x) p_o(x)=

از تساوی دو تابع مولد =p_d(x) po_(x) به دست می آید.

گراف فرر

این گراف از ردیف های نقطه ای برای نمایش قسمت بندی و افراز اعداد صحیح استفاده می کند که تعداد نقاط در هر ردیف از بالا به پایین کمتر می شود.در شکل (1) دو افراز برای عدد 14 : الف)4+3+3+2+1+1 و ب)6+4+3+1 وجود دارد. به گراف در شکل 1- ب ترانهاده ی گراف در شکل 1-الف گویند و بالعکس.

oooooo oooo ooo o (ب)

oooo ooo ooo oo o o )الف)

شکل 1

ااین گراف ها نتایجی در مورد افراز ها به ما می دهند. در شکل 1 به عنوان مثال دو افراز برای عدد 14 آمده است. به دلیل مشابهت یک به یک گراف فرر و ترانهاده اش این مثال یک نمونه را از نتیجه کلی نشان می دهد که افراز های n به m قسمت برابر است با تعداد افراز های n به قسمت برابر است با تعداد افراز های n به قسمت هایی که m بزرگ ترین قسمت آن است.

ت – توابع مولد توانی

وقتی که ترتیب اهمیت پیدا می کند به ابزار جدیدی برای یافتن راه حل نیاز است.برای هر n ε Z>0 داریم: (1+x)^n=∑_{i=0 to∞} (n,r)x^r

که (1+x)^nتابع مولد رشته ی (n,0),(n,1),(n,2),…,(n,n),0,0,0,… است.وقتی می نویسیم (n,r)=c_n,r می خواهیم بر این امر تاکید کنیم که (n,r) تعدادترکیبیات n شی در r صورت در یک زمان 0≤r≤n است.

C_n,r=n!/[r!(n-r)!]=(1/r!).p_(n,r)

هم چنین داریم

(1+x)^n : c(n,0) + c(n,1)x + … + c(n,n)x^n= p(n,0) + p(n,1) x + p(n,2)x^2/2! + … + p(n,n) x^n/n!

هم چنین اگر در (1+x)^r ما ضرایب x^r/r! را لحاظ کنیم، به p(n,r) دست می یابیم، بر این اساس به تعریف زیر میرسیم:

تعریف2# برای رشته ی a₀, a₁, a₂, … در اعداد حقیقی

f_(n) = a₀ + a₁x + a₂x^2/2! + … = ∑_{i=0 to ∞} a_i (x^i)/i!

به عنوان تابع مولد توانی رشته مزبور است.

مثال 9 # با بررس بسط e^x می یابیم که

بسط e^x

e^x = 1 + x + (x^2)/2! + …

e^x تابع مولد توانی برای رشته ی 1 و 1 و 1 و ... است.

مثال 10# در چند حالت 4 حرف از کلمه ی "بیابان" قابل چینش هستند؟

در جدول2 گزینه های محتمل در اندازه 4 از حروف واژه "بیابان" نوشته شده اند.

ا ا ب ب 4!/(2!×2!)

ا ی ب ب 4!/2!

ا ن ب ب 4!/2!

ن ی ب ب 4!/2!

ا ا ی ب 4!/2!

ا ا ن ب 4!/2!

ا ا ن ی 4!/2!

ا ی ن ب 4!

جدول 2

حال ما به جواب با استفاده از توابع مولد می رسیم. برای حرف(ب) از [1+x+(x^2)/2!] استفاده می کنیم از آنجایی که 0 1 یا 2 تا( ب) برای چینش می تواند وجود داشته باشد. شایان ذکر است که ضریب x^2/2! ‚1 می باشد. برای (الف) نیز همین حالت [1+x+(x^2)/2!] را داریم و برای (ن) و(ی) هم (1+x) مورد استفاده قرار می گیرد.پس تابع مولد توانی حاصل به صورت زیر می شود:

f(x)= [1+x+(x^2)/2!]^2.[1+x]^2

و جواب همان ضریب x^4 در f(x) است.در احتساب f(x) به ضرایب زیر برای x^4 بر می خوریم:

(x^4/2!2!+x^4/2!+ x^4/2!+ x^4/2!+ x^4/2!+ x^4/2!+ x^4/2!+x^4)

که با ضرب و تقسیم x^4 در همه ضرایب داریم:

[4!/2!2! +4!/2!+ 4!/2!+ 4!/2!+ 4!/2!+ 4!/2!+ 4!/2!+4!].(x^4/4!)

در آخر جواب برابر ضریب x^4/4!(102) می شود.

مثال 11 # کیسه ای حاوی 48 توپ است که به ترتیب 12 توپ از رنگ های سرخ و زرد و آبی و سبز تشکیل می شود.می خواهیم 12 توپ انتخاب کنیم چند نوع انتخاب وجود دارد که تعداد زوج توپ آبی و تعداد فرد توپ سبز برداشته شود؟

تابع مولد توانی به صورت :

f(x)=(1+x+x^2/2!+x^3/3!+…)^2(1+x^2/2!+x^4/4!+…).(x+x^3/3!+x^5/5!)

=> f(x)=(e^x)^2.((e^x+e^(-x))/2) .((e^x-e^(-x))/2)

=>f(x)=(1/4).e^2x.(e^2x – e^(-2x))=(1/4).(e^4x - 1)

=> f(x)=(1/4)[∑_{i=0 to ∞}(4x)^i/i! ] – 1 =(1/4)[∑_{i=0 to ∞}(4x)^i / i! ]

جواب مسِاله ضریب x^12/12! است که برابر با (1/4)(4^12)=4^11 می شود.

مثال 12 # شرکتی 11 کارمند جدید را استخدام کرده است.هر کدام از این ها بایستی در یکی از 4 اداره وابسته به این شرکت به کارگیری شوند و نیز هر یک از این شرکت ها باید حداقل یک کارمند جدید داشته باشند. راه های به کار گیری کارمندان تازه استخدام شده چند حالت دارد؟

فرض می کنیم 4 اداره وابسته A و B و C و D باشند حال می توان از راه حل چینش 4 حرف برای ساخت یک واژه 11 حرفی استفاده کرد. تابع مولد توانی به صورت زیر می شود :

f(x)=(x+x^2/2!+….)^4 =(e^x -1)^4=e^4x – 4e^3x +6e^2x – 4e^x +1

جواب مجموع ضرایب x^11/11! است:

4^11 -4.(3^11) +6.(2^11) – 4.(1^11) = ∑_{i=0 to 4} [(-1)^i].(4 –i)^11]

ث – نشانه عملگر جمع در توابع مولد

برای f(x)=a₀+a₁x+a₂x^2+… تابع f(x)/(1-x) را داریم:

f(x)/(1-x) = [a₀+a₁x+a₂x^2+…].[1+x+x^2+…]=a₀ +(a₀+a₁)x +( a₀+a₁+a₂)x^2+…

پس f(x)/(1-x) رشته مجموع ضرایب a₀ و a₀+a₁ و.... را تولید می کند.

مثال 13 # رابطه ای را برای تولید رشته 0^2+1^2+2^2+3^2+…+n^2 بیابید.

داریم:

g(x)=1/1-x=1+x+x^2+x^3+…

سپس طبق قاعده مشتق گیری داریم:

g′(x)=[1/1-x]′=1/(1-x)^2 =1+2x+3x^2+…

پس h(x)=x/[(1-x)^2] رشته 0 و 1 و 2 و3 و4 و... را تولید می کند.

k(x)=x . h′(x)=x+(2^2)x^2+(3^2)x^3+…

پس تابع k(x) تابع مولد رشته 0^2+1^2+2^2+3^2 است.

k(x)/(1-x)=[x.(1+x)/(1-x)^3 .(1/(1-x)]= x.(1+x)/(1-x)^4

هم چنین x.(1+x)/(1-x)^4 رشته 0^2 و 0^2+1^2 و 0^2+1^2+2^2 و ... را تولید می کند.که همان ضرایب x^n یا _{i=0 to n} i^2 ∑ است.

x.(1+x)/(1 –x)^4 =(x+x^2)(1-x)^(-4)=(x+x^2)[(-4,0)+(-4,1)(-x)+…]

که ضرایب x^n برابر تعداد زیر است:

(-4,n-1)(-1)^n-1 +(-4,n-2)(-1)^n-2 =[(-1)^(n-1)].(4+(n-1)-1,n-1). (-1)^(n-1) +(-1)^(n-2).(4+(n-2)-1,n-2)(-1)^(n-2) =(n+2,n-1)+(n+1,n-2)

=> Sum of coefficients=(n+2)!/3!(n-1)! + (n+1)!/3!(n-2)!=(1/6).[(n+2)(n+1)(n) +(n+1)(n)(n-1)]=(1/6).[n(n+1)(2n+1)]

ح – حل روابط بازگشتی با استفاده از توابع مولد

فرض بر این که رشته ای از اعداد مانند a₀,a₁,…,a_n,… داریم که به وسیله روابط بازگشتی تعریف شدند ولی ما نمی دانیم که رابطه حاصل از جمله n ام به صراحت چیست.

مثال 14 # رابطه بازگشتی زیر را با استفاده از تابع مولد حل کنید.

a_n- 9a_n-1+26a_n-2-24a_n-3=0 a₀=0 ; a₁=1 ;a₂=10

A(x)=∑_{n=0 to ∞} a_n .x^n = x + 10x^2 +∑_{n=3 to ∞} [(9a_n-1 – 26a_n-2 + 24 a_n-3)(x^n)]

=> A(x) =x + 10x^2 +

9x(A(x) – a₀ –a₁x) -26 (x^2).[ A(x) –a₀] +24 (x^3). A(x)

=>A(x)=[1- 9x +26 x^2 – 24 x^3 ] = x + x^2

=>A(x)=(x+x^2)/ [1- 9x +26 x^2 – 24 x^3 ] = a/(1-2x) + b/(1-3x) + c/(1-4x)

با استفاده از تجزیه روابط کسری داریم:a=3/2 و b=-4 و c=5/2

A(x)=(3/2)∑(2x)^n – 4 ∑(3x)^n + (5/2) ∑ (4x)^n

=>A(x)=(1/2).∑_{n=0 to ∞} [ 3×(5/2) - 8×(3^n) + 5 ×4^n ].(x^n)

=>a_(n)=(1/2).[3×(2^n) – 8 ×(3)^n + 5×(4)^n]جمله n ام دنباله

مراجع :

Discrete and combinatorial Mathematics an applied introduction Ralph P Grimaldi

Parallel and sequential algorithms Berman – Paul

ساختمان های گسسته بهروز قلی زاده

Introduction to Discrete Mathematics James Bradly

جلوه هایی از ترکیبیات ویکتور برایانت ترجمه : عبّاس ثروتی – مهدی محمدی

ترکیبیات (جلد 1) علی رضا علی پور

Implementing Desing Patterns in File Handling using C#

نحوه استفاده از الگوهای طرّاحی در مدیریت فایل‌ها

کارکردن با فایل‌ها در زبان

نحوه استفاده از الگوهای طرّاحی در مدیریت فایل‌ها

کارکردن با فایل‌ها در زبان C#

کارکردن با فایل‌ها در زبان C# به دلیل استفاده از اشیای منعطف بسیار آسان است.

شی‌ء File

شی‌ء File یک فایل را نشان می‌دهد و دارای توابع بسیاری برای بررسی وجود یک فایل ، تغییر نامِ و پاک‌کردن یا حذف آن است. تمام توابع موجود در شی File ایستا[1] هستندکه در این‌صورت هرگز قادر به درست کردن یک شی یا نمونه[2] از کلاس File نخواهیم بود:

if (File.Exists ("Foo.txt"))

File.Delete ("foo.txt");

با استفاده از کلاسِ فایل حتی می‌شود از FileStream برای خواندن از یا نوشتن در فایل استفاده نمود:

//open text file for reading

StreamReader ts = File.OpenText ("foo1.txt");

//open any type of file for reading

FileStream fs = File.OpenRead ("foo2.any");

خواندن فایل‌های متنی

برای خواندن از فایل‌های متنی ، از شی File برای بدست‌آوردن یک شی از StreamReader استفاده نمائید:

StreamReader ts = File.OpenText ("foo1.txt");

String s =ts.ReadLine ();

نوشتن در فایل ِمتنی

برای نوشتن در فایلِ متنی از تابع CreateText برای دستیابی به شی‌ای از کلاس StreamWriter استفاده کنید.

//open for writing

StreamWriter sw = File.CreateText ("foo3.txt");

sw.WriteLine ("Hello file");

اگر مایل هستید که متنی را به فایل متنی‌تان بچسبانید می‌توانید مستقیماً یک شی از StreamWriter درست کنید و آرگومان بولی (بولیان)[3] آن را برابر True کنید.

//append to text file

StreamWriter asw = new StreamWriter ("foo1.txt", true);

استثنائات در مدیریت فایل‌ها

بیش‌تر استثنائات در ورودی و خروجی فایل رخ می‌دهد. استثتائاتی از قبیل این‌که فایلی را که وجود ندارد مورد استفاده قرار بگیرد و یا از آرگومان‌های نامناسب برای فایل استفاده شده باشد. بنابراین مطمئن‌ترین راه برای اجتناب از عواقب این استثنائات محصورسازی برنامه در بسته‌های Try و Catch است.

try {

//open text file for reading

StreamReader ts = File.OpenText ("foo1.txt");

String s =ts.ReadLine ();

}

catch(Exception e ) {

Console.WriteLine (e.Message );

}

بررسی پایان یک فایل

دو راه برای اینکه از خواندن اطلاعات بعد از پایان فایل جلوگیری شود ؛ وجود دارد. یکی به دنبال استثنای Null رفتن و دیگری به پایان data stream رسیدن است.

private StreamReader rf;

private bool eof;

//------------

public String readLine () {

String s = rf.ReadLine ();

if(s == null)

eof = true;

return s;

}

//------------

public bool fEof() {

return eof;

}

راه دیگر استفاده از Peek است که مقدار اَسکی[4] حرف بعدی را می‌خواند که مقدار 1- نبودن اطلاعات را می‌رساند.

public String read_Line() {

String s = ""

if (rf.Peek() > 0) {

s = rf.ReadLine ();

}

else

eof=true;

return s;

}

استفاده از کلاس‌های فایلینگ

یک راه مفید از مدیریت فایل‌ها استفاده از کلاس‌هایی با توابعی آسان است :

public class csFile

{

private string fileName;

StreamReader ts;

StreamWriter ws;

private bool opened, writeOpened;

//-----------

public csFile() {

init();

}

//-----------

private void init() {

opened = false;

writeOpened = false;

}

//-----------

public csFile(string file_name) {

fileName = file_name;

init();

}

با این کار می‌توان از یک فایل خواند یا در آن نوشت و اطلاعات موجود را در آن مدیریت کرد. می‌توان با استفاده از مقادیری بولی از باز یا بسته‌بودن یک فایل برای استفاده از آن استفاده کرد :

public bool OpenForRead(string file_name){

fileName = file_name;

try {

ts = new StreamReader (fileName);

opened=true;

}

catch(FileNotFoundException e) {

return false;

}

return true;

}

//-----------

public bool OpenForRead() {

return OpenForRead(fileName);

}

می‌توان اطلاعات را از یک فایل متنی خواند :

public string readLine() {

return ts.ReadLine ();

}

به همین ترتیب می‌توان از توابع زیر برای باز کردن یک فایل و نوشتن در آن استفاده نمود:

public void writeLine(string s) {

ws.WriteLine (s);

}

//-----------

public bool OpenForWrite() {

return OpenForWrite(fileName);

}

//-----------

public bool OpenForWrite(string file_name) {

try{

ws = new StreamWriter (file_name);

fileName = file_name;

writeOpened = true;

return true;

}

catch(FileNotFoundException e) {

return false;

}

}

منابع و مآخذ:

James W. Cooper , Introduction to Design Patterns in C# , IBM T J Watson Research Center , February 1, 2002

---

[1] Static

[2] instance

[3] Boolean

[4] ASCII

Design Patterns

پیشینه الگوهای طرّاحی[1]

الگوهای طراحی از کاری از کریستوفر الکساندر[2] در دهه 1970 میلادی منشأ می‌گیرند. او با نوشتن دو کتاب « زبان الگویی»[3] در سال 1977 و « روش‌ِ بی‌کران ساختن »[4] در سال 1979 الگوهای طراحی را مستند نمود. تا سال 1987 تغییرات زبانی کمی در الگوها به وجود آمد تا این‌که در گردهمایی برنامه‌ها ، زبان‌‌ها و سامانه‌های شی‌گرا [5] مقالات و ارائه مطالب بسیاری در مورد این مبحث منتشر شدند. در سال 1995 اریک گاما[6] ، ریچارد هِلم[7] ، رالف جانسون[8] و جان ولیسیدز[9] کتاب «الگوهای طراحی : عناصر یک نرم‌افزار شی‌گرا با قابلیت استفاده مجدد»[10] را انتشار دادند که به تبع آن کتب‌ها و مقالات بسیاری در این ‌باره به چاپ رسیدند.

چرا الگوهای طرّاحی به وجود آمدند؟

يکي از دلايلي که محققان علوم رايانه اي آغاز به شناخت الگوهاي طرّاحي شدند اين بود که شما اگر یک برنامه‌نویس تنها هستید بتوانید به راحتی مطمئن باشید که برنامه‌ای کارا و خوانا ، امّا در عین حال ساده ، نوشته‌اید. در آغاز ممکن است شما با دیدن اسم الگوی طرّاحی احساس خوبی نسبت به این اسم نداشته باشید امّا در واقع این کار برای نوشتن یک برنامه شی‌گرا[11] با قابلیت استفاده مجدد[12] بسیار مناسب است. به بیانی دیگر الگوهای طراحی این کمک را به ما می‌نمایند که اشیای[13] مختلف را ، بدون اینکه تداخلی یا درگیری پیش آید ، با هم مرتبط نمائیم .

برای اینکه بتوانید از یک الگوی طرّاحی استفاده نمائید باید سه مرحله زیر را قبول کنید:

1- موافقت

2- تشخیص

3- درونی‌سازی

نخست بایستی با اندیشه کلّی حاکم بر الگوهای طرّاحی موافق باشید. پس از آن با تشخیص این‌که در چه جایی صلاح است که از این الگوها استفاده کنید می‌توانید این آن‌ها را وارد برنامه‌تان نمائید

.

---

[1] Design Patterns

[2] Christopher Alexander

[3] A Pattern Language

[4] A Timeless Way of Building

[5] OOPSLA (conference on object-oriented programming systems, languages and applications).

[6] Erich Gamma

[7] Richard Helm

[8] Ralph Johnson

[9] John Vlissides

[10] Design Patterns, Elements of Reusable Object-Oriented Software

[11] Object Oriented (OO)

[12] Reusability

[13] Objects

منابع و مآخذ:

http://www.csc.calpoly.edu/%7Edbutler/tutorials/winter96/patterns/objectives.htmJames W. Cooper , Introduction to Design Patterns in C# , IBM T J Watson Research Center , February 1, 2002

Jimmy Nilsson , Applying Domain-Driven Design and Patterns: With Examples in C# and .NET, 1/e , Addison Wesley Professional , May 08, 2006

Haming Code implementations in Technology

روش پیش‌تشخیص خطا [1] با توانایی تشخیص خطای پیام‌های ارسالی برای تصحیحشان باعث شلوغی محیط عملیاتی داده‌ها می‌شود. پایگاه فرستنده باید اطلاعاتی اضافه بر سازمان را برای تصحیح خطا به داده‌ها بچسباند و این امر می‌تواند باعث طولانی‌شدن زمان انتقال داده‌ها شود. در رمزینه همینگ ساز و کاری به صورت بسته توازن[2] که قابلیت بکارگیری با مخارج کمی داراست. در کل این رمزینه قابلیت تشخیص و تصحیح خطاهای تک‌بیتی و تشخیص خطاهای دوبیتی را دارد. اساس همینگ بر توازن بنا شده است.

در مخابرات و ارتباطات ، رمزینه همینگ یک روش خطی برای خطایابی رمزهای ارسالی است که به خاطر نام مبدع آن این روش به روش همینگ شهرت یافته است. این رمزینه قابلیت تشخیص و نیز تصحیح خطاهای تک بیتی را داراست. امّا برای خطاهای دوبیتی فقط می‌تواند خطا را تشخیص دهد و قابلیت تصحیح خطا را ندارد.

یکی دیگر از کاربردهای رمزینه‌های همینگ استفاده آن‌ها در حافظه‌های فلش NAND است. در این نوع از حافظه در انتقال داده‌‌ها برای تشخیص و تصحیح خطا از الگوریتم موجود در رمزینه‌های همینگ استفاده می‌شود. امّا در این فناوری نیز محدودیت یک یا دوبیتی تشخیص خطا باقی مانده است.[3]

---

[1] FEC : Forward Error Correction

[2] Block Parity

[3] www.micron.com/nand/