مقاله بررسی سيستم اعداد مانده‌اي (باقيمانده)

مقاله بررسی سيستم اعداد مانده‌اي (باقيمانده) در 26 صفحه ورد قابل ویرایش

فهرست

عنوان صفحه
1-1) مقدمه...................................................................................................... 2
2-1) عمليات رياضي........................................................................................ 7
1-2-1) معكوس ضرب................................................................................... 10
3-1) سيستم اعدادمبناي در هم وابسطه......................................................... 12
4-1) تبديل اعداد به سيستم اعداد مانده‌اي و برعكس..................................... 22
1-4-1-) تبديل اعداد از سيستم باينري به سيستم مانده‌اي .......................... 24
5-1) انتخاب پيمانه........................................................................................... 26


سيستم اعداد مانده‌اي (باقيمانده)
سيستم اعداد مانده‌اي يك سيستم اعداد صحيح است، كه مهمترين ويژگي‌اش بطور ذاتي انتقال رقم نقلي مجازي در جمع و ضرب و تفريق‌هاست، همچنين نتجه جمع و تفريق و ضرب اعداد ما در مرحله اول بدون در نظر گرفتن طول اعداد مشخص مي‌شود، متأسفانه در سيستم اعداد مانده‌اي عمليات رياضي ديگري مانند تقسيم و مقايسه و شناسايي علامت خيلي پيچيده و كند هستند از مشكلات ديگر سيستم اعداد مانده‌اي اين است كه چون با سيستم اعداد صحيح كار مي‌كند در نتيجه نمايش اعداد اعشاري در سيستم اعداد مانده‌اي خيلي ناجور است با توجه به خواص سيستم اعداد مانده‌اي نتيجه مي‌گيريم كه در اهداف عمومي كامپيوترها (ماشين حساب‌ها) به صورت كاملاً جدي نمي‌تواند مطرح بشود. بهرحال ، براي بعضي از كاربرها كه اهداف خاصي دارند مثل بسياري از انواع فيلترهاي ديجيتال، تعداد جمع و ضرب‌هايي كه اساساً بزرگتر تعداد و درخواست بزرگي دامنه و شناسايي سرريز، تقسيم و شبيه اين‌ها، سيستم اعداد باقيمانده خيلي جذاب و جالب مي‌تواند باشد.
1-1) مقدمه
سيستم اعدادمانده‌اي اساساً بوسيله يك مبناي چندتائي (N - تائي) و نه يك مبناي واحد مثل از اعداد صحيح مشخص مي‌شود. هر كدام از ها باقيمانده پس از تقسيم يك عدد بر آن‌ها است.عدد صيح X در سيستم اعداد مانده‌اي بوسيلة يك N -تائي مثل نمايش داده مي‌شود كه هر يك عدد غيرمنفي صحيح است كه در رابطة زير صادق است:

X
0
1
0
1
0
1
0
1
0
1
0
1
0 2
0
1
2
0
1
2
0
1
2
0
1
2 -4
-3
-2
-1
0
1
2
3
4
5
6
7
8
جدول 1-1 نمايش اعداد در سيستم اعداد مانده‌اي به پيمانة‌
بزرگترين عدد صحيحي است بطوريكه معروف است به باقيمانده X به پيمانة Mi ، و در روش نوشتن اعداد هر دو و با يك مفهوم استفاده مي‌شوند.
-1 سيستم اعداد مبناي در هم وابسطه
با نمايش سيستم اعداد اعداد مانده‌اي به صورت سيستم اعداد مبناي درهم وابسطه انجام برخي از عمليات ها از جمله شناسايي سرريز، شناسايي علامت و دامنه مقايسه راحت‌تر مي‌شود. سيستم اعداد مبناي درهم وابسطه يك سيستم وزني است، اگر عدد X در سيستم اعداد مانده‌اي با پيمانة به صورت نشان داده شده باشد آنگاه اين عدد در سيستم اعداد مبناي درهم وابسطه به صورت زير نشان داده مي‌شود.

بطوريكه
وجود يك سيستم اعداد وزني نشان دهنده اين مطلب است كه دامنه مقايسه شان خطي است. به عنوان نمونه با توجه به مثال زير:


سيستم اعداد مبناي در هم وابسطه سيستم اعداد مانده‌اي با پيمانة
0
1
0
1
0
1 0
0
1
1
2
2 0
1
0
1
0
1 0
1
2
0
1
2 0
1
2
3
4
5

كه مقدار عدد در اين سيستم مبناي در هم وابسطه بر اساس زوج هست:

مثال 4-1
يك سيستم اعداد ماند‌ه‌اي به پيمانة داريم،حال در سيستم اعداد منباي در هم وابسطه به اين سيستم هر عدد بوسيلة يك چهارتايي به شكل نمايش داده مي‌شود كه مقداري كه برمي‌گرداند عبارت است از
به عنوان مثال:
يك سيستم اعداد مانده‌اي داريم كه در اين سيستم M برابر با 210 مي‌باشد (چون كه دو به دو پيمانه‌ها نسبت به هم اول هستند. حال اگر بخواهيم دو عدد 206 و 7 را در اين سيستم جمع كنيم آنگاه:
2) 3 5 (7
0) 2 1 (3 206
1) 1 2 (0 +
7
1) 3 3 (3 بايد 213 باشد ولي 3 است .
1) 0 3 (3
جمع اين دو عدد در اين سيستم اعداد مانده‌اي عدد 3 را بر مي‌گرداند كه جواب اشتباه است و اين اشتباه به خاطر سرريز است.
حال براي اينكه ما بتوانيم سرريز را شناسايي كنيم اگر كه يك پيمانه اضافه بگيريم اين امكان پذير مي‌باشد مثلاً در سيستم اعداد مانده‌اي قبلي اگر كه ما را اضافه كنيم يعني يك سيستم اعداد مانده‌اي با پيمانة داشته باشيم آنوقت امكان شناسايي سريز را داريم به عنوان مثال جمع دو عدد 206 و 7 در اين سيستم
2) 3 5 7 (11
0) 2 1 3 (8 206
1) 1 2 0 (7 + 7
1) 3 3 3 (15
1) 0 3 3 (4

حال اگر را به سيستم اعداد مبناي در هم رابطه ببريم:


بنابراين ما اهداف زير را دنبال مي كنيم:
1- مجموع تعداد بيت ها تشكيل دهنده پيمانه ها در سيستم اعداد باينري بايد كم باشد.
2- براي سادگي اجراي عمليات رياضي روي آنها، كد باينري راحتي داشته باشند.
كوچكترين تعداد بيتي كه براي نمايش پيمانه در سيستم اعداد دودويي نياز است برابر است با بنابراين ما ماكزيمم استفاده در حافظه را موقعي كه پيمانه ها تواني از 2 باشند مثلا و يا خيلي نزديك به اين مثل .
به روشني مشخص است كه پيمانه هايي كه انتخاب مي كنيم فقط يكي شان مي تواند تواني از دو باشد چونكه طبق تعريف اوليه بايد دو به دو نسبت به هم اول باشند ما پس از اينكه را انتخاب كرديم انتخاب هاي بعدي مان را مي توانيم به صورت انجام داد كه البته باز هم مقدار كمي پيمانه به شكل مي توانيم انتخاب كنيم ، چونكه به عنوان مثال اگر k زوج باشد آنگاه :

و در نتيجه و نسبت به هم اول نيستند و همچنين براي بعضي مقادير فرد k ، ممكن است قابل فاكتور گيري باشند.
پيمانه هاي انتخاب شده بايد در حد امكان نزديك به هم باشند و همچنين از انتخاب
پيمانه هاي خيلي بزرگ خودداري كنيم كه رعايت اين عوامل باعث كم شدن زمان اجرا
مي شود.